Linear, Cone and Semidefinite Programming

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

    Global optimization of rational functions: a semidefinite programming approach

  • Etienne de Klerk
  • Dorina Jibetean
    • Categories Global Optimization Theory, Nonlinear Optimization, Semi-definite Programming Tags , , ,

    We consider the problem of global minimization of rational functions on $\LR^n$ (unconstrained case), and on an open, connected, semi-algebraic subset of $\LR^n$, or the (partial) closure of such a set (constrained case). We show that in the univariate case ($n=1$), these problems have exact reformulations as semidefinite programming (SDP) problems, by using reformulations introduced … Read more

    The mathematics of eigenvalue optimization

  • Adrian Lewis
    • Categories Control Applications, Nonsmooth Optimization, Semi-definite Programming Tags , , , , , , , , , , , , , , , ,

    Optimization problems involving the eigenvalues of symmetric and nonsymmetric matrices present a fascinating mathematical challenge. Such problems arise often in theory and practice, particularly in engineering design, and are amenable to a rich blend of classical mathematical techniques and contemporary optimization theory. This essay presents a personal choice of some central mathematical ideas, outlined for … Read more