Semi-definite Programming

Hidden convexity, optimization, and algorithms on rotation matrices

  • Kevin Shu
  • Alex L. Wang
  • Akshay Ramachandran
    • Categories Constrained Nonlinear Optimization, Other Topics, Semi-definite Programming Tags , ,

    This paper studies hidden convexity properties associated with constrained optimization problems over the set of rotation matrices \(\text{SO}(n)\). Such problems are nonconvex due to the constraint\(X\in\text{SO}(n)\). Nonetheless, we show that certain linear images of \(\text{SO}(n)\) are convex, opening up the possibility for convex optimization algorithms with provable guarantees for these problems. Our main technical contributions … Read more

    Closing Duality Gaps of SDPs through Perturbation

  • Takashi Tsuchiya
  • Bruno F. Lourenço
  • Masakazu Muramatsu
  • Takayuki Okuno
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , ,

    Let \(({\bf P},{\bf D})\) be a primal-dual pair of SDPs with a nonzero finite duality gap. Under such circumstances, \({\bf P}\) and \({\bf D}\) are weakly feasible and if we perturb the problem data to recover strong feasibility, the (common) optimal value function \(v\) as a function of the perturbation is not well-defined at zero … Read more

    Solving low-rank semidefinite programs via manifold optimization

  • Jie Wang
    • Categories Constrained Nonlinear Optimization, Optimization Software Benchmark, Semi-definite Programming Tags , , , , ,

    We propose a manifold optimization approach to solve linear semidefinite programs (SDP) with low-rank solutions. This approach incorporates the augmented Lagrangian method and the Burer-Monteiro factorization, and features the adaptive strategies for updating the factorization size and the penalty parameter. We prove that the present algorithm can solve SDPs to global optimality, despite of the … Read more

    Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator

  • Yu Hin (Gary) Au
  • Levent Tunçel
    • Categories Combinatorial Optimization, Cutting Plane Approaches, Semi-definite Programming Tags , , , ,

    We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lovász-Schrijver SDP operator \( \text{LS}_+\), with a particular focus on a search for relatively small graphs with high \( \text{LS}_+\)-rank (the least number of iterations of the \( \text{LS}_+\) operator on the fractional stable set polytope to compute the … Read more

    Equivalent Sufficient Conditions for Global Optimality of Quadratically Constrained Quadratic Program

  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , ,

    We study the equivalence of several well-known sufficient optimality conditions for a general quadratically constrained quadratic program (QCQP). The conditions are classified in two categories. The first one is for determining an optimal solution and the second one is for finding an optimal value. The first category of conditions includes the existence of a saddle … Read more

    Semidefinite approximations for bicliques and biindependent pairs

  • Monique Laurent
  • Sven Polak
  • Luis Felipe Vargas
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , , , , ,

    We investigate some graph parameters dealing with biindependent pairs $(A,B)$ in a bipartite graph $G=(V_1\cup V_2,E)$, i.e., pairs $(A,B)$ where $A\subseteq V_1$, $B\subseteq V_2$ and $A\cup B$ is independent. These parameters also allow to study bicliques in general graphs. When maximizing the cardinality $|A\cup B|$ one finds the stability number $\alpha(G)$, well-known to be polynomial-time … Read more

    On solving the MAX-SAT using sum of squares

  • Lennart Sinjorgo
  • Renata Sotirov
    • Categories 0-1 Programming, Branch and Cut Algorithms, Semi-definite Programming Tags , , , ,

    We consider semidefinite programming (SDP) approaches for solving the maximum satisfiabilityproblem (MAX-SAT) and the weighted partial MAX-SAT. It is widely known that SDP is well-suitedto approximate the (MAX-)2-SAT. Our work shows the potential of SDP also for other satisfiabilityproblems, by being competitive with some of the best solvers in the yearly MAX-SAT competition.Our solver combines … Read more

    Polynomial argmin for recovery and approximation of multivariate discontinuous functions

  • Didier Henrion
  • Milan Korda
  • Jean-Bernard Lasserre
    • Categories Basic Sciences Applications, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , ,

    We propose to approximate a (possibly discontinuous) multivariate function f(x) on a compact set by the partial minimizer arg min_y p(x,y) of an appropriate polynomial p whose construction can be cast in a univariate sum of squares (SOS) framework, resulting in a highly structured convex semidefinite program. In a number of non-trivial cases (e.g. when … Read more

    Handling Symmetries in Mixed-Integer Semidefinite Programs

  • Christopher Hojny
  • Marc E. Pfetsch
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , ,

    Symmetry handling is a key technique for reducing the running time of branch-and-bound methods for solving mixed-integer linear programs. In this paper, we generalize the notion of (permutation) symmetries to mixed-integer semidefinite programs (MISDPs). We first discuss how symmetries of MISDPs can be automatically detected by finding automorphisms of a suitably colored auxiliary graph. Then … Read more