Linear, Cone and Semidefinite Programming

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

    Accurate and Warm-Startable Linear Cutting-Plane Relaxations for ACOPF

  • Daniel Bienstock
  • Matias Villagra
    • Categories Convex Optimization, Energy, Linear, Cone and Semidefinite Programming Tags , ,

    We present a linear cutting-plane relaxation approach that rapidly proves tight lower bounds for the Alternating Current Optimal Power Flow Problem (ACOPF). Our method leverages outer-envelope linear cuts for well-known second-order cone relaxations for ACOPF along with modern cut management techniques. These techniques prove effective on a broad family of ACOPF instances, including the largest … Read more

    Cuts and semidefinite liftings for the complex cut polytope

  • Lennart Sinjorgo
  • Renata Sotirov
  • Miguel F. Anjos
    • Categories Polyhedra, Semi-definite Programming, Telecommunications Tags , , , , ,

    \(\) We consider the complex cut polytope: the convex hull of Hermitian rank 1 matrices \(xx^{\mathrm{H}}\), where the elements of \(x \in \mathbb{C}^n\) are \(m\)th unit roots. These polytopes have applications in \({\text{MAX-3-CUT}}\), digital communication technology, angular synchronization and more generally, complex quadratic programming. For \({m=2}\), the complex cut polytope corresponds to the well-known cut … Read more

    Non-facial exposedness of copositive cones over symmetric cones

  • Mitsuhiro Nishijima
  • Bruno F. Lourenço
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    In this paper, we consider copositive cones over symmetric cones and show that they are never facially exposed when the underlying cone has dimension at least 2. We do so by explicitly exhibiting a non-exposed extreme ray. Our result extends the known fact that the cone of copositive matrices over the nonnegative orthant is not … Read more

    Robust support vector machines via conic optimization

  • Shaoning Han
  • Andrés Gómez
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Optimization in Data Science Tags , , , ,

    We consider the problem of learning support vector machines robust to uncertainty. It has been established in the literature that typical loss functions, including the hinge loss, are sensible to data perturbations and outliers, thus performing poorly in the setting considered. In contrast, using the 0-1 loss or a suitable non-convex approximation results in robust … Read more

    Refined TSSOS

  • Daria Shaydurova
  • Volker Kaibel
  • Sebastian Sager
    • Categories Global Optimization Applications, Nonlinear Optimization, Semi-definite Programming Tags , , , ,

    The moment-sum of squares hierarchy by Lasserre has become an established technique for solving polynomial optimization problems. It provides a monotonically increasing series of tight bounds, but has well-known scalability limitations. For structured optimization problems, the term-sparsity SOS (TSSOS) approach scales much better due to block-diagonal matrices, obtained by completing the connected components of adjacency … Read more

    Sparse Polynomial Optimization with Unbounded Sets

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

    This paper considers sparse polynomial optimization with unbounded sets. When the problem possesses correlative sparsity, we propose a sparse homogenized Moment-SOS hierarchy with perturbations to solve it. The new hierarchy introduces one extra auxiliary variable for each variable clique according to the correlative sparsity pattern. Under the running intersection property, we prove that this hierarchy … Read more

    A low-rank augmented Lagrangian method for large-scale semidefinite programming based on a hybrid convex-nonconvex approach

  • Renato D.C. Monteiro
  • Arnesh Sujanani
  • Diego Cifuentes
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , , , , , , ,

    \(\) This paper introduces HALLaR, a new first-order method for solving large-scale semidefinite programs (SDPs) with bounded domain. HALLaR is an inexact augmented Lagrangian (AL) method where the AL subproblems are solved by a novel hybrid low-rank (HLR) method. The recipe behind HLR is based on two key ingredients: 1) an adaptive inexact proximal point … Read more

    Post-Processing with Projection and Rescaling Algorithms for Semidefinite Programming

  • Shin-ichi Kanoh
  • Akiko Yoshise
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming

    We propose the algorithm that solves the symmetric cone programs (SCPs) by iteratively calling the projection and rescaling methods the algorithms for solving exceptional cases of SCP. Although our algorithm can solve SCPs by itself, we propose it intending to use it as a post-processing step for interior point methods since it can solve the … Read more

    Solving moment and polynomial optimization problems on Sobolev spaces

  • Didier Henrion
  • Alessandro Rudi
    • Categories Global Optimization, Infinite Dimensional Optimization, Semi-definite Programming Tags , , ,

    Using standard tools of harmonic analysis, we state and solve the problem of moments for positive measures supported on the unit ball of a Sobolev space of multivariate periodic trigonometric functions. We describe outer and inner semidefinite approximations of the cone of Sobolev moments. They are the basic components of an infinite-dimensional moment-sums of squares … Read more