Semi-definite Programming

Superlinear convergence of an interior point algorithm on linear semi-definite feasibility problems

  • Chee-Khian Sim
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , ,

    In the literature, besides the assumption of strict complementarity, superlinear convergence of implementable polynomial-time interior point algorithms using known search directions, namely, the HKM direction, its dual or the NT direction, to solve semi-definite programs (SDPs) is shown by (i) assuming that the given SDP is nondegenerate and making modifications to these algorithms [10], or … Read more

    Evolving Scientific Discovery by Unifying Data and Background Knowledge with AI Hilbert

  • Ryan Cory-Wright
  • Cristina Cornelio
  • Sanjeeb Dash
  • Bachir El Khadir
  • Lior Horesh
    • Categories Basic Sciences Applications, Global Optimization Applications, Semi-definite Programming Tags , , ,

    The discovery of scientific formulae that parsimoniously explain natural phenomena and align with existing background theory is a key goal in science. Historically, scientists have derived natural laws by manipulating equations based on existing knowledge, forming new equations, and verifying them experimentally. In recent years, data-driven scientific discovery has emerged as a viable competitor in … Read more

    Further Development in Convex Conic Reformulation of Geometric Nonconvex Conic Optimization Problems

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

    A geometric nonconvex conic optimization problem (COP) was recently proposed by Kim, Kojima and Toh asa unified framework for convex conic reformulation of a class of quadratic optimization problems and polynomial optimization problems. The nonconvex COP minimizes a linear function over the intersection of a nonconvex cone K, a convex subcone J of the convex … Read more

    Dual Conflict Analysis for Mixed-Integer Semidefinite Programs

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

    Conflict analysis originally tried to exploit the knowledge that certain nodes in a relaxation-based branch-and-bound are infeasible. It has been extended to derive valid constraints also from feasible nodes. This paper adapts this approach to mixed-integer semidefinite programs. Using dual solutions, the primal constraints are aggregated and the resulting inequalities can be used at different … 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

    Provably Faster Gradient Descent via Long Steps

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

    This work establishes provably faster convergence rates for gradient descent in smooth convex optimization via a computer-assisted analysis technique. Our theory allows nonconstant stepsize policies with frequent long steps potentially violating descent by analyzing the overall effect of many iterations at once rather than the typical one-iteration inductions used in most first-order method analyses. We … Read more

    On Integrality in Semidefinite Programming for Discrete Optimization

  • Frank de Meijer
  • Renata Sotirov
    • Categories Combinatorial Optimization, Quadratic Programming, Semi-definite Programming Tags , , , ,

    It is well-known that by adding integrality constraints to the semidefinite programming (SDP) relaxation of the max-cut problem, the resulting integer semidefinite program is an exact formulation of the problem. In this paper we show similar results for a wide variety of discrete optimization problems for which SDP relaxations have been derived. Based on a … 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

    Optimal Low-Rank Matrix Completion: Semidefinite Relaxations and Eigenvector Disjunctions

  • Dimitris Bertsimas
  • Ryan Cory-Wright
  • Sean Lo
  • Jean Pauphilet
    • Categories Data-Mining, Global Optimization Theory, Semi-definite Programming

    Low-rank matrix completion consists of computing a matrix of minimal complexity that recovers a given set of observations as accurately as possible. Unfortunately, existing methods for matrix completion are heuristics that, while highly scalable and often identifying high-quality solutions, do not possess any optimality guarantees. We reexamine matrix completion with an optimality-oriented eye. We reformulate … 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