Linear, Cone and Semidefinite Programming

Algebraic Tail Decay of Condition Numbers for Random Conic Systems under a General Family of Input Distributions

  • Raphael Hauser
  • Tobias Muller
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    We consider the conic feasibility problem associated with linear homogeneous systems of inequalities. The complexity of iterative algorithms for solving this problem depends on a condition number. When studying the typical behaviour of algorithms under stochastic input one is therefore naturally led to investigate the fatness of the distribution tails of the random condition number … Read more

    A Tractable Approximation of Stochastic Programming via Robust Optimization

  • Xin Chen
  • Peng Sun
  • Jiawei Zhang
  • Melvyn Sim
    • Categories Robust Optimization, Second-Order Cone Programming, Stochastic Programming Tags , , ,

    Stochastic programming, despite its immense modeling capabilities, is well known to be computationally excruciating. In this paper, we introduce a unified framework of approximating multiperiod stochastic programming from the perspective of robust optimization. Specifically, we propose a framework that integrates multistage modeling with safeguarding constraints. The framework is computationally tractable in the form of second … Read more

    An extension of the standard polynomial-time primal-dual path-following algorithm to the weighted determinant maximization problem with semidefinite constraints

  • Takashi Tsuchiya
  • Yu Xia
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    The problem of maximizing the sum of linear functional and several weighted logarithmic determinant (logdet) functions under semidefinite constraints is a generalization of the semidefinite programming (SDP) and has a number of applications in statistics and datamining, and other areas of informatics and mathematical sciences. In this paper, we extend the framework of standard primal-dual … Read more

    Central Paths in Semidefinite Programming, Generalized Proximal Point Method and Cauchy Trajectories in Riemannian Manifolds

  • João Xavier da Cruz Neto
  • Orizon Pereira Ferreira
  • Paulo Roberto Oliveira
  • R. C. M. Silva
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    The relationships among central path in the context of semidefinite programming, generalized proximal point method and Cauchy trajectory in Riemannian manifolds is studied in this paper. First it is proved that the central path associated to the general function is well defined. The convergence and characterization of its limit point is established for functions satisfying … Read more

    On the complexity of optimization over the standard simplex

  • Etienne de Klerk
  • Dick den Hertog
  • Gamal Elabwabi
    • Categories Global Optimization Theory, Linear, Cone and Semidefinite Programming Tags , , , ,

    We review complexity results for minimizing polynomials over the standard simplex and unit hypercube. In addition, we show that there exists a polynomial time approximation scheme (PTAS) for minimizing some classes of functions (including Lipschitz continuous functions) over the standard simplex. The main tools used in the analysis are Bernstein approximation and Lagrange interpolation on … Read more

    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