Linear, Cone and Semidefinite Programming

Large-Scale Semidefinite Programming via Saddle Point Mirror-Prox Algorithm

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

    In this paper, we first develop “economical” representations for positive semidefinitness of well-structured sparse symmetric matrix. Using the representations, we then reformulate well-structured large-scale semidefinite problems into smooth convex-concave saddle point problems, which can be solved by a Prox-method with efficiency ${\cal O}(\epsilon^{-1})$ developed in \cite{Nem}. Some numerical implementations for large-scale Lovasz capacity and MAXCUT … Read more

    Sums of Squares and Semidefinite Programming Relaxations for Polynomial Optimization Problems with Structured Sparsity

  • Sunyoung Kim
  • Masakazu Kojima
  • Masakazu Muramatsu
  • Hayato Waki
    • Categories Constrained Nonlinear Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , ,

    Unconstrained and inequality constrained sparse polynomial optimization problems (POPs) are considered. A correlative sparsity pattern graph is defined to find a certain sparse structure in the objective and constraint polynomials of a POP. Based on this graph, sets of supports for sums of squares (SOS) polynomials that lead to efficient SOS and semidefinite programming (SDP) … Read more

    The Q Method for Second-order Cone Programming

  • Farid Alizadeh
  • Yu Xia
    • Categories Constrained Nonlinear Optimization, Second-Order Cone Programming, Semi-definite Programming Tags , ,

    Based on the Q method for SDP, we develop the Q method for SOCP. A modified Q method is also introduced. Properties of the algorithms are discussed. Convergence proofs are given. Finally, we present numerical results. CitationAdvOl-Report#2004/15 McMaster University, Advanced Optimization LaboratoryArticleDownload View PDF

    An Algorithm for Perturbed Second-order Cone Programs

  • Yu Xia
    • Categories Complementarity and Variational Inequalities, Nonsmooth Optimization, Second-Order Cone Programming Tags , , ,

    The second-order cone programming problem is reformulated into several new systems of nonlinear equations. Assume the perturbation of the data is in a certain neighborhood of zero. Then starting from a solution to the old problem, the semismooth Newton’s iterates converge Q-quadratically to a solution of the perturbed problem. The algorithm is globalized. Numerical examples … Read more

    The Q Method for Symmetric Cone Programming

  • Farid Alizadeh
  • Yu Xia
    • Categories Complementarity and Variational Inequalities, Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We extend the Q method to the symmetric cone programming. An infeasible interior point algorithm and a Newton-type algorithm are given. We give convergence results of the interior point algorithm and prove that the Newton-type algorithm is good for CitationAdvOl-Report#2004/18 McMaster University, Advanced Optimization Laboratory Hamilton, Ontario, Canada October 2004ArticleDownload View PDF

    On the Behavior of the Homogeneous Self-Dual Model for Conic Convex Optimization

  • Robert M. Freund
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , ,

    There is a natural norm associated with a starting point of the homogeneous self-dual (HSD) embedding model for conic convex optimization. In this norm two measures of the HSD model’s behavior are precisely controlled independent of the problem instance: (i) the sizes of epsilon-optimal solutions, and (ii) the maximum distance of epsilon-optimal solutions to the … Read more

    A Stable Iterative Method for Linear Programming

  • Maria Gonzalez-Lima
  • Hua Wei
  • Henry Wolkowicz
    • Categories Linear Programming Tags , ,

    This paper studies a new primal-dual interior/exterior-point method for linear programming. We begin with the usual perturbed primal-dual optimality equations $F_\mu(x,y,z)=0$. Under nondegeneracy assumptions, this nonlinear system is well-posed, i.e. it has a nonsingular Jacobian at optimality and is not necessarily ill-conditioned as the iterates approach optimality. We use a simple preprocessing step to eliminate … Read more

    A New Conjugate Gradient Algorithm Incorporating Adaptive Ellipsoid Preconditioning

  • Renato D.C. Monteiro
  • Arkadi Nemirovski
  • Jerome W. O'Neal
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , , , , ,

    The conjugate gradient (CG) algorithm is well-known to have excellent theoretical properties for solving linear systems of equations $Ax = b$ where the $n\times n$ matrix $A$ is symmetric positive definite. However, for extremely ill-conditioned matrices the CG algorithm performs poorly in practice. In this paper, we discuss an adaptive preconditioning procedure which improves the … Read more

    A New Complexity Result on Solving the Markov Decision Problem

  • Yinyu Ye
    • Categories Linear Programming Tags , ,

    We present a new complexity result on solving the Markov decision problem (MDP) with $n$ states and a number of actions for each state, a special class of real-number linear programs with the Leontief matrix structure. We prove that, when the discount factor $\theta$ is strictly less than $1$, the problem can be solved in … Read more

    A survey of the S-lemma

  • Imre Pólik
  • Tamás Terlaky
    • Categories Control Applications, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , , , , ,

    In this survey we review the many faces of the S-lemma, a result about the correctness of the S-procedure. The basic idea of this widely used method came from control theory but it has important consequences in quadratic and semidefinite optimization, convex geometry and linear algebra as well. These were active research areas, but as … Read more