semidefinite programming

A barrier Lagrangian dual method for multi-stage stochastic convex semidefinite optimization

  • Baha Alzalg
  • Asma Gafour
    • Categories Nonlinear Optimization, Semi-definite Programming, Stochastic Programming Tags , , , ,

    In this paper, we present a polynomial-time barrier algorithm for solving multi-stage stochastic convex semidefinite optimization based on the Lagrangian dual method which relaxes the nonanticipativity constraints. We show that the barrier Lagrangian dual functions for our setting form self-concordant families with respect to barrier parameters. We also use the barrier function method to improve … Read more

    An effective version of Schmüdgen’s Positivstellensatz for the hypercube

  • Monique Laurent
  • Lucas Slot
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    Let S be a compact semialgebraic set and let f be a polynomial nonnegative on S. Schmüdgen’s Positivstellensatz then states that for any \eta>0, the nonnegativity of f+\eta on S can be certified by expressing f+\eta as a conic combination of products of the polynomials that occur in the inequalities defining S, where the coefficients … Read more

    Revisiting semidefinite programming approaches to options pricing: complexity and computational perspectives

  • Didier Henrion
  • Felix Kirschner
  • Etienne de Klerk
  • Jean-Bernard Lasserre
  • Victor Magron
    • Categories Finance and Economics, Semi-definite Programming Tags , ,

    In this paper we consider the problem of finding bounds on the prices of options depending on multiple assets without assuming any underlying model on the price dynamics, but only the absence of arbitrage opportunities. We formulate this as a generalized moment problem and utilize the well-known Moment-Sum-of-Squares (SOS) hierarchy of Lasserre to obtain bounds … Read more

    Ellipsoidal Classification via Semidefinite Programming

  • Annabella Astorino
  • Antonio Frangioni
  • Enrico Gorgone
  • Benedetto Manca
    • Categories Applications - OR and Management Sciences, Semi-definite Programming Tags , ,

    Separating two finite sets of points in a Euclidean space is a fundamental problem in classification. Customarily linear separation is used, but nonlinear separators such as spheres have been shown to have better performances in some tasks, such as edge detection in images. We exploit the relationships between the more general version of the spherical … Read more

    A Sum of Squares Characterization of Perfect Graphs

  • Amir Ali Ahmadi
  • Cemil Dibek
    • Categories Combinatorial Optimization, Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We present an algebraic characterization of perfect graphs, i.e., graphs for which the clique number and the chromatic number coincide for every induced subgraph. We show that a graph is perfect if and only if certain nonnegative polynomials associated with the graph are sums of squares. As a byproduct, we obtain several infinite families of … Read more

    Exactness of Parrilo’s conic approximations for copositive matrices and associated low order bounds for the stability number of a graph

  • Monique Laurent
  • Luis Felipe Vargas
    • Categories Approximation Algorithms, Semi-definite Programming Tags , , , , ,

    De Klerk and Pasechnik (2002) introduced the bounds $\vartheta^{(r)}(G)$ ($r\in \mathbb{N}$) for the stability number $\alpha(G)$ of a graph $G$ and conjectured exactness at order $\alpha(G)-1$: $\vartheta^{(\alpha(G)-1)}(G)=\alpha(G)$. These bounds rely on the conic approximations $\mathcal{K}_n^{(r)}$ by Parrilo (2000) for the copositive cone $\text{COP}_n$. A difficulty in the convergence analysis of $\vartheta^{(r)}$ is the bad behaviour … Read more

    Pareto Robust Optimization on Euclidean Vector Spaces

  • Dennis Adelhütte
  • Christian Biefel
  • Martina Kuchlbauer
  • Jan Hendrik Rolfes
    • Categories Robust Optimization Tags , ,

    Pareto efficiency for robust linear programs was introduced by Iancu and Trichakis. We generalize their approach and theoretical results to robust optimization problems in Euclidean spaces with affine uncertainty. Additionally, we demonstrate the value of this approach in an exemplary manner in the area of robust semidefinite programming (SDP). In particular, we prove that computing … Read more

    SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs

  • Carlos Nohra
  • Arvind U. Raghunathan
  • Nikolaos Sahinidis
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Tags , , , ,

    We consider the global optimization of nonconvex mixed-integer quadratic programs with linear equality constraints. In particular, we present a new class of convex quadratic relaxations which are derived via quadratic cuts. To construct these quadratic cuts, we solve a separation problem involving a linear matrix inequality with a special structure that allows the use of … Read more

    Dealing with inequality constraints in large-scale semidefinite relaxations for graph coloring and maximum clique problems

  • Federico Battista
  • Marianna De Santis
    • Categories Combinatorial Optimization, Convex Optimization, Semi-definite Programming Tags , ,

    Semidefinite programs (SDPs) can be solved in polynomial time by interior point methods. However, when the dimension of the problem gets large, interior point methods become impractical in terms of both computational time and memory requirements. Certain first-order methods, such as Alternating Direction Methods of Multipliers (ADMMs), established as suitable algorithms to deal with large-scale … Read more

    Sequential constant rank constraint qualifications for nonlinear semidefinite programming with applications

  • Roberto Andreani
  • Gabriel Haeser
  • Héctor Ramírez
  • Leonardo M. Mito
    • Categories Constrained Nonlinear Optimization, Second-Order Cone Programming, Semi-definite Programming Tags , , ,

    We present new constraint qualification conditions for nonlinear semidefinite programming that extend some of the constant rank-type conditions from nonlinear programming. As an application of these conditions, we provide a unified global convergence proof of a class of algorithms to stationary points without assuming neither uniqueness of the Lagrange multiplier nor boundedness of the Lagrange … Read more