Linear, Cone and Semidefinite Programming

The Rate of Convergence of the Augmented Lagrangian Method for Nonlinear Semidefinite Programming

  • Jie Sun
  • Defeng Sun
  • Liwei Zhang
    • Categories Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , ,

    We analyze the rate of local convergence of the augmented Lagrangian method for nonlinear semidefinite optimization. The presence of the positive semidefinite cone constraint requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and certain variational analysis on the projection operator in the symmetric-matrix space. Without … Read more

    Generating and Measuring Instances of Hard Semidefinite Programs, SDP

  • Hua Wei
  • Henry Wolkowicz
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , ,

    Linear Programming, LP, problems with finite optimal value have a zero duality gap and a primal-dual strictly complementary optimal solution pair. On the other hand, there exists Semidefinite Programming, SDP, problems which have a nonzero duality gap (different primal and dual optimal values; not both infinite). The duality gap is assured to be zero if … Read more

    A Note on Sparse SOS and SDP Relaxations for Polynomial Optimization Problems over Symmetric Cones

  • Masakazu Kojima
  • Masakazu Muramatsu
    • Categories Constrained Nonlinear Optimization, Global Optimization, Semi-definite Programming Tags , , , , , ,

    This short note extends the sparse SOS (sum of squares) and SDP (semidefinite programming) relaxation proposed by Waki, Kim, Kojima and Muramatsu for normal POPs (polynomial optimization problems) to POPs over symmetric cones, and establishes its theoretical convergence based on the recent convergence result by Lasserre on the sparse SOS and SDP relaxation for normal … Read more

    Existence of Equilibrium for Integer Allocation Problems

  • Somdeb Lahiri
    • Categories Game Theory, Linear Programming Tags , , , ,

    In this paper we show that if all agents are equipped with discrete concave production functions, then a feasible price allocation pair is a market equilibrium if and only if it solves a linear programming problem, similar to, but perhaps simpler than the one invoked in Yang (2001). Using this result, but assuming discrete concave … Read more

    Approximating the Chromatic Number of a Graph by Semidefinite Programming

  • N. Gvozdenovic
  • Monique Laurent
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , ,

    We investigate hierarchies of semidefinite approximations for the chromatic number $\chi(G)$ of a graph $G$. We introduce an operator $\Psi$ mapping any graph parameter $\beta(G)$, nested between the stability number $\alpha(G)$ and $\chi(\bar G)$, to a new graph parameter $\Psi_\beta(G)$, nested between $\omega(G)$ and $\chi(G)$; $\Psi_\beta(G)$ is polynomial time computable if $\beta(G)$ is. As an … Read more

    An LMI description for the cone of Lorentz-positive maps

  • Roland Hildebrand
    • Categories Semi-definite Programming Tags , ,

    Let $L_n$ be the $n$-dimensional second order cone. A linear map from $\mathbb R^m$ to $\mathbb R^n$ is called positive if the image of $L_m$ under this map is contained in $L_n$. For any pair $(n,m)$ of dimensions, the set of positive maps forms a convex cone. We construct a linear matrix inequality (LMI) that … Read more

    A conic interior point decomposition approach for large scale semidefinite programming

  • Gema Plaza
  • Kartik Krishnan Sivaramakrishnan
  • Tamás Terlaky
    • Categories Nonsmooth Optimization, Semi-definite Programming Tags , , ,

    We describe a conic interior point decomposition approach for solving a large scale semidefinite programs (SDP) whose primal feasible set is bounded. The idea is to solve such an SDP using existing primal-dual interior point methods, in an iterative fashion between a {\em master problem} and a {\em subproblem}. In our case, the master problem … Read more

    On the Implementation of Interior Point Decomposition Algorithms for Two-Stage Stochastic Conic

  • Sanjay Mehrotra
  • M. Gokhan Ozevin
    • Categories Finance and Economics, Linear, Cone and Semidefinite Programming, Stochastic Programming Tags , , , , ,

    In this paper we develop a practical primal interior decomposition algorithm for two-stage stochastic programming problems. The framework of this algorithm is similar to the framework in Mehrotra and \”{Ozevin} \cite{MO04a,MO04b} and Zhao \cite{GZ01}, however their algorithm is altered in a simple yet fundamental way to achieve practical performance. In particular, this new algorithm weighs … Read more

    Further Development of Multiple Centrality Correctors for Interior Point Methods

  • Marco Colombo
  • Jacek Gondzio
    • Categories Linear Programming Tags , , ,

    This paper addresses the role of centrality in the implementation of interior point methods. Theoretical arguments are provided to justify the use of a symmetric neighbourhood. These are translated into computational practice leading to a new insight into the role of re-centering in the implementation of interior point methods. Arguments are provided to show that … Read more

    On Time-Invariant Purified-Output-Based Discrete Time Control

  • Aharon Ben-Tal
  • Stephen Boyd
  • Arkadi Nemirovski
    • Categories Control Applications, Convex Optimization, Semi-definite Programming Tags , ,

    In http://www.optimizationonline.org/DB_HTML/2005/05/1136.html 05/25/05, we have demonstrated that the family of all affine non-anticipative output-based control laws in a discrete time linear dynamical system affected by uncertain disturbances is equivalent, as far as state-control trajectories are concerned, to the family of all affine non-anticipative “purified-output-based” control laws. The advantage of the latter representation of affine controls … Read more