Semi-definite Programming

A Subgradient Projection Method with Outer Approximation for Solving Semidefinite Programming Problems

  • Nagisa Sugishita
  • Miguel F. Anjos
    • Categories Convex Optimization, Semi-definite Programming Tags , ,

    We explore the combination of subgradient projection with outer approximation to solve semidefinite programming problems. We compare several ways to construct outer approximations using the problem structure. The resulting approach enjoys the strengths of both subgradient projection and outer approximation methods. Preliminary computational results on the semidefinite programming relaxations of graph partitioning and max-cut show … Read more

    Robust System Identification: Finite-sample Guarantees and Connection to Regularization

  • Hyuk Park
    • Categories Control Applications, Robust Optimization, Semi-definite Programming Tags , ,

    We address the problem of identifying a stable linear time-invariant system from a single sample trajectory. The least squares estimate (LSE) is a commonly used algorithm for this purpose. However, LSE may exhibit poor identification errors when the number of samples is small. To mitigate the issue, we introduce the robust LSE, which integrates robust … Read more

    Tighter yet more tractable relaxations and nontrivial instance generation for sparse standard quadratic optimization

  • Immanuel M. Bomze
  • Bo Peng
  • Yuzhou Qiu
  • E. Alper Yildirim
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Semi-definite Programming Tags , , , ,

    The Standard Quadratic optimization Problem (StQP), arguably the simplest among all classes of NP-hard optimization problems, consists of extremizing a quadratic form (the simplest nonlinear polynomial) over the standard simplex (the simplest polytope/compact feasible set). As a problem class, StQPs may be nonconvex with an exponential number of inefficient local solutions. StQPs arise in a … Read more

    Exploiting Sign Symmetries in Minimizing Sums of Rational Functions

  • Jie Wang
  • Feng Guo
    • Categories Constrained Nonlinear Optimization, Global Optimization Applications, Semi-definite Programming Tags , , , ,

    This paper is devoted to the problem of minimizing a sum of rational functions over a basic semialgebraic set. We provide a hierarchy of sum of squares (SOS) relaxations that is dual to the generalized moment problem approach due to Bugarin, Henrion, and Lasserre. The investigation of the dual SOS aspect offers two benefits: 1) … Read more

    Edge expansion of a graph: SDP-based computational strategies

  • Akshay Gupte
  • Melanie Siebenhofer
  • Angelika Wiegele
    • Categories Combinatorial Optimization, Parallel Algorithms, Semi-definite Programming Tags , , , ,

    Computing the edge expansion of a graph is a famously hard combinatorial problem for which there have been many approximation studies. We present two variants of exact algorithms using semidefinite programming (SDP) to compute this constant for any graph. The first variant uses the SDP relax- ation first to reduce the search space considerably. One … Read more

    Strengthening Lasserre’s Hierarchy in Real and Complex Polynomial Optimization

  • Jie Wang
    • Categories Constrained Nonlinear Optimization, Global Optimization Theory, Semi-definite Programming Tags , , , , ,

    We establish a connection between multiplication operators and shift operators. Moreover, we derive positive semidefinite conditions of finite rank moment sequences and use these conditions to strengthen Lasserre’s hierarchy for real and complex polynomial optimization. Integration of the strengthening technique with sparsity is considered. Extensive numerical experiments show that our strengthening technique can significantly improve … Read more

    On Averaging and Extrapolation for Gradient Descent

  • Alan Luner
  • Benjamin Grimmer
    • Categories Convex Optimization, Semi-definite Programming Tags , , , ,

    \(\) This work considers the effect of averaging, and more generally extrapolation, of the iterates of gradient descent in smooth convex optimization. After running the method, rather than reporting the final iterate, one can report either a convex combination of the iterates (averaging) or a generic combination of the iterates (extrapolation). For several common stepsize … Read more

    T-semidefinite programming relaxation with third-order tensors for constrained polynomial optimization

  • Hiroki Marumo
  • Sunyoung Kim
  • Makoto Yamashita
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , ,

    We study T-semidefinite programming (SDP) relaxation for constrained polynomial optimization problems (POPs). T-SDP relaxation for unconstrained POPs was introduced by Zheng, Huang and Hu in 2022. In this work, we propose a T-SDP relaxation for POPs with polynomial inequality constraints and show that the resulting T-SDP relaxation formulated with third-order tensors can be transformed into … Read more