semidefinite programming

Chance-Constrained Linear Matrix Inequalities with Dependent Perturbations: A Safe Tractable Approximation Approach

  • Sin-Shuen Cheung
  • Anthony Man-Cho So
  • Kuncheng Wang
    • Categories Robust Optimization Tags , ,

    The wide applicability of chance-constrained programming, together with advances in convex optimization and probability theory, has created a surge of interest in finding efficient methods for processing chance constraints in recent years. One of the successes is the development of so-called safe tractable approximations of chance-constrained programs, where a chance constraint is replaced by a … Read more

    Inexact Dynamic Bundle Methods

  • Krzysztof C. Kiwiel
    • Categories Convex Optimization, Nonsmooth Optimization Tags , , ,

    We give a proximal bundle method for minimizing a convex function $f$ over $\mathbb{R}_+^n$. It requires evaluating $f$ and its subgradients with a possibly unknown accuracy $\epsilon\ge0$, and maintains a set of free variables $I$ to simplify its prox subproblems. The method asymptotically finds points that are $\epsilon$-optimal. In Lagrangian relaxation of convex programs, it … Read more

    On Duality Theory for Non-Convex Semidefinite Programming

  • Chengjin Li
  • Wenyu Sun
  • Raimundo Sampaio
    • Categories Constrained Nonlinear Optimization, Semi-definite Programming Tags , , , ,

    In this paper, with the help of convex-like function, we discuss the duality theory for nonconvex semidefinite programming. Our contributions are: duality theory for the general nonconvex semidefinite programming when Slater’s condition holds; perfect duality for a special case of the nonconvex semidefinite programming for which Slater’s condition fails. We point out that the results … Read more

    A Robust Algorithm for Semidefinite Programming

  • Xuan Vinh Doan
  • Henry Wolkowicz
  • Serge Kruk
    • Categories Optimization Software Benchmark, Semi-definite Programming Tags , ,

    Current successful methods for solving semidefinite programs, SDP, are based on primal-dual interior-point approaches. These usually involve a symmetrization step to allow for application of Newton’s method followed by block elimination to reduce the size of the Newton equation. Both these steps create ill-conditioning in the Newton equation and singularity of the Jacobian of the … Read more

    On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems

  • Etienne de Klerk
  • Monique Laurent
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    The Lasserre hierarchy of semidefinite programming approximations to convex polynomial optimization problems is known to converge finitely under some assumptions. [J.B. Lasserre. Convexity in semialgebraic geometry and polynomial optimization. SIAM J. Optim. 19, 1995-2014, 2009.] We give a new proof of the finite convergence property, that does not require the assumption that the Hessian of … Read more

    Convex envelopes for quadratic and polynomial functions over polytopes

  • Marco Locatelli
    • Categories Global Optimization Theory Tags , , , ,

    In this paper we consider the problem of computing the value and a supporting hyperplane of the convex envelope for quadratic and polynomial functions over polytopes with known vertex set. We show that for general quadratic functions the computation can be carried on through a copositive problem, but in some cases (including all the two-dimensional … Read more

    The Inexact Spectral Bundle Method for Convex Quadratic Semidefinite Programming

  • Huiling Lin
    • Categories Convex and Nonsmooth Optimization, Semi-definite Programming, Unconstrained Optimization Tags , ,

    We present an inexact spectral bundle method for solving convex quadratic semidefinite optimization problems. This method is a first-order method, hence requires much less computational cost each iteration than second-order approaches such as interior-point methods. In each iteration of our method, we solve an eigenvalue minimization problem inexactly, and solve a small convex quadratic semidefinite … Read more

    Min-Max Theorems Related to Geometric Representations of Graphs and their SDPs

  • Marcel K. de Carli Silva
  • Levent Tunçel
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , ,

    Lovasz proved a nonlinear identity relating the theta number of a graph to its smallest radius hypersphere embedding where each edge has unit length. We use this identity and its generalizations to establish min-max theorems and to translate results related to one of the graph invariants above to the other. Classical concepts in tensegrity theory … Read more

    SpeeDP: A new algorithm to compute the SDP relaxations of Max-Cut for very large graphs

  • Luigi Grippo
  • Veronica Piccialli
  • Laura Palagi
  • Mauro Piacentini
  • Giovanni Rinaldi
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , , ,

    We consider low-rank semidefinite programming (LRSDP) relaxations of unconstrained {-1,1} quadratic problems (or, equivalently, of Max-Cut problems) that can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function subject to separable quadratic equality constraints. We prove the equivalence of the LRSDP problem with the unconstrained minimization of a new merit function … Read more

    Semidefinite Relaxations for Non-Convex Quadratic Mixed-Integer Programming

  • Christoph Buchheim
  • Angelika Wiegele
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , ,

    We present semidefinite relaxations for unconstrained non-convex quadratic mixed-integer optimization problems. These relaxations yield tight bounds and are computationally easy to solve for medium-sized instances, even if some of the variables are integer and unbounded. In this case, the problem contains an infinite number of linear constraints; these constraints are separated dynamically. We use this … Read more