Linear, Cone and Semidefinite Programming

Strengthened Existence and Uniqueness Conditions for Search Directions in Semidefinite Programming

  • Levent Tunçel
  • Henry Wolkowicz
    • Categories Convex Optimization, Semi-definite Programming Tags , , , , ,

    Primal-dual interior-point (p-d i-p) methods for Semidefinite Programming (SDP) are generally based on solving a system of matrix equations for a Newton type search direction for a symmetrization of the optimality conditions. These search directions followed the derivation of similar p-d i-p methods for linear programming (LP). Among these, a computationally interesting search direction is … Read more

    Limiting behavior of the Alizadeh-Haeberly-Overton weighted paths in semidefinite programming

  • Zhaosong Lu
  • Renato D.C. Monteiro
    • Categories Semi-definite Programming Tags , , ,

    This paper studies the limiting behavior of weighted infeasible central paths for semidefinite programming obtained from centrality equations of the form $X S + SX = 2 \nu W$, where $W$ is a fixed positive definite matrix and $\nu>0$ is a parameter, under the assumption that the problem has a strictly complementary primal-dual optimal solution. … Read more

    Asymptotic behavior of the central path for a special class of degenerate SDP problems

  • João Xavier da Cruz Neto
  • Orizon Pereira Ferreira
  • Renato D.C. Monteiro
    • Categories Semi-definite Programming Tags , , , ,

    This paper studies the asymptotic behavior of the central path $(X(\nu),S(\nu),y(\nu))$ as $\nu \downarrow 0$ for a class of degenerate semidefinite programming (SDP) problems, namely those that do not have strictly complementary primal-dual optimal solutions and whose “degenerate diagonal blocks” $X_{\cT}(\nu)$ and $S_{\cT}(\nu)$ of the central path are assumed to satisfy $\max\{ \|X_{\cT}(\nu)\|, \|S_{\cT}(\nu)\| \} … Read more

    On Semidefinite Programming Relaxations for the Satisfiability Problem

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

    This paper is concerned with the analysis and comparison of semidefinite programming (SDP) relaxations for the satisfiability (SAT) problem. Our presentation is focussed on the special case of 3-SAT, but the ideas presented can in principle be extended to any instance of SAT specified by a set of boolean variables and a propositional formula in … Read more

    Error bounds and limiting behavior of weighted paths associated with the SDP map ^{1/2}SX^{1/2}$

  • Zhaosong Lu
  • Renato D.C. Monteiro
    • Categories Semi-definite Programming Tags , , , ,

    This paper studies the limiting behavior of weighted infeasible central paths for semidefinite programming obtained from centrality equations of the form $X^{1/2}S X^{1/2} = \nu W$, where $W$ is a fixed positive definite matrix and $\nu>0$ is a parameter, under the assumption that the problem has a strictly complementary primal-dual optimal solution. It is shown … Read more

    Calculation of universal barrier functions for cones generated by Chebyshev systems over finite sets

  • Leonid Faybusovich
  • Michael Gekhtman
    • Categories Linear, Cone and Semidefinite Programming, Semi-infinite Programming Tags , ,

    We explicitly calculate universal barrier functions for cones generated by (weakly) Chebyshev systems over finite sets. We show that universal barrier functions corresponding to Chebyshev systems on intervals are obtained as limits of universal barrier functions of their discretizations. The results are heavily rely upon classical work of M. Krein, A. Nudelman and I.J. Schoenberg … Read more

    D.C. Versus Copositive Bounds for Standard QP

  • Kurt M. Anstreicher
  • Samuel Burer
    • Categories Global Optimization Theory, Semi-definite Programming Tags , , ,

    The standard quadratic program (QPS) is $\min_{x\in\Delta} x’Qx$, where $\Delta\subset\Re^n$ is the simplex $\Delta=\{ x\ge 0 : \sum_{i=1}^n x_i=1 \}$. QPS can be used to formulate combinatorial problems such as the maximum stable set problem, and also arises in global optimization algorithms for general quadratic programming when the search space is partitioned using simplices. One … Read more

    On Conically Ordered Convex Programs

  • Shuzhong Zhang
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    In this paper we study a special class of convex optimization problems called {\em conically ordered convex programs}\/ (COCP), where the feasible region is given as the level set of a vector-valued nonlinear mapping, expressed as a nonnegative combination of convex functions. The nonnegativity of the vectors is defined using a pre-described conic ordering. The … Read more

    The Complexity of Self-Regular Proximity Based Infeasible IPMs

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

    Primal-Dual Interior-Point Methods (IPMs) have shown their power in solving large classes of optimization problems. In this paper a self-regular proximity based Infeasible Interior Point Method (IIPM) is proposed for linear optimization problems. First we mention some interesting perties of a specific self-regular proximity function, studied recently by Peng and Terlaky, and use it to … Read more

    A predictor-corrector algorithm for linear optimization based on a specific self-regular proximity function

  • Jiming Peng
  • Tamás Terlaky
  • Yun-Bin Zhao
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    It is well known that the so-called first-order predictor-corrector methods working in a large neighborhood of the central path are among the most efficient interior-point methods (IPMs) for linear optimization (LO) problems. However, the best known iteration complexity of this type of methods is $O\br{n \log\frac{(x^0)^Ts^0}{\varepsilon}}$. It is of interests to investigate whether the complexity … Read more