Linear, Cone and Semidefinite Programming

A strong bound on the integral of the central path curvature and its relationship with the iteration complexity of primal-dual path-following LP algorithms

  • Renato D.C. Monteiro
  • Takashi Tsuchiya
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , , , , , , , , , , , ,

    The main goals of this paper are to: i) relate two iteration-complexity bounds associated with the Mizuno-Todd-Ye predictor-corrector algorithm for linear programming (LP), and; ii) study the geometrical structure of the central path in the context of LP. The first forementioned iteration-complexity bound is expressed in terms of an integral introduced by Sonnevend, Stoer and … Read more

    A Homogeneous Model for Mixed Complementarity Problems over Symmetric Cones

  • Yedong Lin
  • Akiko Yoshise
    • Categories Complementarity and Variational Inequalities, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , , , ,

    In this paper, we propose a homogeneous model for solving monotone mixed complementarity problems over symmetric cones, by extending the results in \cite{YOSHISE04} for standard form of the problems. We show that the extended model inherits the following desirable features: (a) A path exists, is bounded and has a trivial starting point without any regularity … Read more

    Variational Two-electron Reduced Density Matrix Theory for Many-electron Atoms and Molecules: Implementation of the Spin- and Symmetry-adapted T2 Condition through First-order Semidefinite Programming

  • David A. Mazziotti
    • Categories Constrained Nonlinear Optimization, Semi-definite Programming Tags , ,

    The energy and properties of a many-electron atom or molecule may be directly computed from a variational optimization of a two-electron reduced density matrix (2-RDM) that is constrained to represent many-electron quantum systems. In this paper we implement a variational 2-RDM method with a representability constraint, known as the $T_2$ condition. The optimization of the … Read more

    Computational NETLIB experience with a dense projected gradient sagitta method

  • Pablo Guerrero-García
  • Ángel Santos-Palomo
    • Categories Linear Programming, Optimization Software and Modeling Systems

    Computational results obtained when solving a subset of NETLIB problems by using a dense projected gradient implementation of the non-simplex active-set sagitta method presented in [12] are summarized. Two different addition rules for its initial phase are considered and, for each problem solved, two corresponding graphs are reported to illustrate the variations of the objective … Read more

    Semidefinite Optimization Approaches for Satisfiability and Maximum-Satisfiability Problems

  • Miguel F. Anjos
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    Semidefinite optimization, commonly referred to as semidefinite programming, has been a remarkably active area of research in optimization during the last decade. For combinatorial problems in particular, semidefinite programming has had a truly significant impact. This paper surveys some of the results obtained in the application of semidefinite programming to satisfiability and maximum-satisfiability problems. The … Read more

    Anstreicher-Terlaky type monotonic simplex algorithms for linear feasibility problems

  • Zsolt Csizmadia
  • Tibor Illés
  • Bilen Filiz
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    We define a variant of Anstreicher and Terlaky’s (1994) monotonic build-up (MBU) simplex algorithm for linear feasibility problems. Under a nondegeneracy assumption weaker than the normal one, the complexity of the algorithm can be given by $m\Delta$, where $\Delta$ is a constant determined by the input data of the problem and $m$ is the number … Read more

    Embedded in the Shadow of the Separator

  • Frank Göring
  • Christoph Helmberg
  • Markus Wappler
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , , , ,

    We study the problem of maximizing the second smallest eigenvalue of the Laplace matrix of a graph over all nonnegative edge weightings with bounded total weight. The optimal value is the \emph{absolute algebraic connectivity} introduced by Fiedler, who proved tight connections of this value to the connectivity of the graph. Using semidefinite programming techniques and … Read more

    An Exact Primal-Dual Penalty Method Approach to Warmstarting Interior-Point Methods for Linear Programming

  • Hande Benson
  • David F. Shanno
    • Categories Linear Programming Tags , , ,

    One perceived deficiency of interior-point methods in comparison to active set methods is their inability to efficiently re-optimize by solving closely related problems after a warmstart. In this paper, we investigate the use of a primal-dual penalty approach to overcome this problem. We prove exactness and convergence and show encouraging numerical results on a set … Read more

    Postponing the Choice of the Barrier Parameter in Mehrotra-Type Predictor-Corrector Algorithms

  • Maziar Salahi
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    In \cite{SPT} the authors considered a variant of Mehrotra’s predictor-corrector algorithm that has been widely used in several IPMs based optimization packages. By an example they showed that this variant might make very small steps in order to keep the iterate in a certain neighborhood of the central path, that itself implies the inefficiency of … Read more

    A copositive programming approach to graph partitioning

  • Janez Povh
  • Franz Rendl
    • Categories Approximation Algorithms, Semi-definite Programming Tags , , , ,

    We consider 3-partitioning the vertices of a graph into sets $S_1, S_2$ and $S_3$ of specified cardinalities, such that the total weight of all edges joining $S_1$ and $S_2$ is minimized. This problem is closely related to several NP-hard problems like determining the bandwidth or finding a vertex separator in a graph. We show that … Read more