[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

semidefinite programming

Performance Estimation for Smooth and Strongly Convex Sets

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

    We extend recent computer-assisted design and analysis techniques for first-order optimization over structured functions–known as performance estimation–to apply to structured sets. We prove “interpolation theorems” for smooth and strongly convex sets with Slater points and bounded diameter, showing a wide range of extremal questions amount to structured mathematical programs. Prior function interpolation theorems are recovered … Read more

    Application of the Lovász-Schrijver Operator to Compact Stable Set Integer Programs

  • Federico Battista
  • Fabrizio Rossi
  • Stefano Smriglio
    • Categories 0-1 Programming, Combinatorial Optimization, Semi-definite Programming Tags , ,

    The Lov\’asz theta function $\theta(G)$ provides a very good upper bound on the stability number of a graph $G$. It can be computed in polynomial time by solving a semidefinite program (SDP), which also turns out to be fairly tractable in practice. Consequently, $\theta(G)$ achieves a hard-to-beat trade-off between computational effort and strength of the … Read more

    A combinatorial approach to Ramana’s exact dual for semidefinite programming

  • Gabor Pataki
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , ,

    Thirty years ago, in a seminal paper Ramana derived an exact dual for Semidefinite Programming (SDP). Ramana’s dual has the following remarkable features: i) it assumes feasibility of the primal, but it does not make any regularity assumptions, such as strict feasibility ii) its optimal value is the same as the optimal value of the … Read more

    Granularity for mixed-integer polynomial optimization problems

  • Carl Eggen
  • Oliver Stein
  • Stefan Volkwein
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , , , ,

    Finding good feasible points is crucial in mixed-integer programming. For this purpose we combine a sufficient condition for consistency, called granularity, with the moment-/sos-hierarchy from polynomial optimization. If the mixed-integer problem is granular, we obtain feasible points by solving continuous polynomial problems and rounding their optimal points. The moment-/sos-hierarchy is hereby used to solve those … Read more

    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

    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 polytope. … Read more

    Higher-Order Newton Methods with Polynomial Work per Iteration

  • Amir Ali Ahmadi
  • Abraar Chaudhry
  • Jeffrey Zhang
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , ,

    We present generalizations of Newton’s method that incorporate derivatives of an arbitrary order \(d\) but maintain a polynomial dependence on dimension in their cost per iteration. At each step, our \(d^{\text{th}}\)-order method uses semidefinite programming to construct and minimize a sum of squares-convex approximation to the \(d^{\text{th}}\)-order Taylor expansion of the function we wish to … Read more

    A more efficient reformulation of complex SDP as real SDP

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

    This note proposes a new reformulation of complex semidefinite programs (SDPs) as real SDPs. As an application, we present an economical reformulation of complex SDP relaxations of complex polynomial optimization problems as real SDPs and derive some further reductions by exploiting inner structure of the complex SDP relaxations. Various numerical examples demonstrate that our new … Read more

    A Moment-SOS Hierarchy for Robust Polynomial Matrix Inequality Optimization with SOS-Convexity

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

    We study a class of polynomial optimization problems with a robust polynomial matrix inequality constraint for which the uncertainty set is defined also by a polynomial matrix inequality (including robust polynomial semidefinite programs as a special case). Under certain SOS-convexity assumptions, we construct a hierarchy of moment-SOS relaxations for this problem to obtain convergent upper … Read more

    Optimized Dimensionality Reduction for Moment-based Distributionally Robust Optimization

  • ShiyiJiang
  • Jianqiang Cheng
  • Kai Pan
  • Z.J. Max Shen
    • Categories Optimization in Data Science, Robust Optimization, Semi-definite Programming Tags , , , ,

    Moment-based distributionally robust optimization (DRO) provides an optimization framework to integrate statistical information with traditional optimization approaches. Under this framework, one assumes that the underlying joint distribution of random parameters runs in a distributional ambiguity set constructed by moment information and makes decisions against the worst-case distribution within the set. Although most moment-based DRO problems … Read more