Linear, Cone and Semidefinite Programming

Generating Cutting Inequalities Successively for Quadratic Optimization Problems in Binary Variables

  • Sunyoung Kim
  • Masakazu Kojima
    • Categories 0-1 Programming, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , , , , , , ,

    We propose a successive generation of cutting inequalities for binary quadratic optimization problems. Multiple cutting inequalities are successively generated for the convex hull of the set of the optimal solutions $\subset \{0, 1\}^n$, while the standard cutting inequalities are used for the convex hull of the feasible region. An arbitrary linear inequality with integer coefficients … Read more

    Exactness in SDP relaxations of QCQPs: Theory and applications

  • Fatma Kılınç-Karzan
  • Alex L. Wang
    • Categories Global Optimization Theory, Semi-definite Programming

    Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems. In a QCQP, we are asked to minimize a (possibly nonconvex) quadratic function subject to a number of (possibly nonconvex) quadratic constraints. Such problems arise naturally in many areas of operations research, computer science, and engineering. Although QCQPs are NP-hard to solve in … Read more

    First- and second-order optimality conditions for second-order cone and semidefinite programming under a constant rank condition

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

    The well known constant rank constraint qualification [Math. Program. Study 21:110–126, 1984] introduced by Janin for nonlinear programming has been recently extended to a conic context by exploiting the eigenvector structure of the problem. In this paper we propose a more general and geometric approach for defining a new extension of this condition to the … Read more

    The Promise of EV-Aware Multi-Period OPF Problem: Cost and Emission Benefits

  • Sezen Ece Kayacık
  • Burak Kocuk
  • Tuğçe Yüksel
    • Categories Applications - OR and Management Sciences, Global Optimization, Second-Order Cone Programming Tags , ,

    In this paper, we study the Multi-Period Optimal Power Flow problem (MOPF) with electric vehicles (EV) under emission considerations. We integrate three different real-world datasets: household electricity consumption, marginal emission factors, and EV driving profiles. We present a systematic solution approach based on second-order cone programming to find globally optimal solutions for the resulting nonconvex … Read more

    Completely Positive Factorization by a Riemannian Smoothing Method

  • Zhijian Lai
  • Akiko Yoshise
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    Copositive optimization is a special case of convex conic programming, and it optimizes a linear function over the cone of all completely positive matrices under linear constraints. Copositive optimization provides powerful relaxations of NP-hard quadratic problems or combinatorial problems, but there are still many open problems regarding copositive or completely positive matrices. In this paper, … Read more

    Rank computation in Euclidean Jordan algebras

  • Michael Orlitzky
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    Euclidean Jordan algebras are the abstract foundation for symmetriccone optimization. Every element in a Euclidean Jordan algebra has a complete spectral decomposition analogous to the spectral decomposition of a real symmetric matrix into rank-one projections. The spectral decomposition in a Euclidean Jordan algebra stems from the likewise-analogous characteristic polynomial of its elements, whose degree is … Read more

    Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems

  • Mirjam Dür
  • Franz Rendl
    • Categories Linear, Cone and Semidefinite Programming

    A conic optimization problem is a problem involving a constraint that the optimization variable be in some closed convex cone. Prominent examples are second order cone programs (SOCP), semidefinite problems (SDP), and copositive problems. We survey recent progress made in this area. In particular, we highlight the connections between nonconvex quadratic problems, binary quadratic problems, … 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

    A Homogeneous Predictor-Corrector Algorithm for Stochastic Nonsymmetric Convex Conic Optimization With Discrete Support

  • Baha Alzalg
  • Mohammad Alabedalhadi
    • Categories Linear, Cone and Semidefinite Programming, Stochastic Programming Tags , , , ,

    We consider a stochastic convex optimization problem over nonsymmetric cones with discrete support. This class of optimization problems has not been studied yet. By using a logarithmically homogeneous self-concordant barrier function, we present a homogeneous predictor-corrector interior-point algorithm for solving stochastic nonsymmetric conic optimization problems. We also derive an iteration bound for the proposed algorithm. … Read more

    Barrier Methods Based on Jordan-Hilbert Algebras for Stochastic Optimization in Spin Factors

  • Baha Alzalg
    • Categories Infinite Dimensional Optimization, Linear, Cone and Semidefinite Programming, Stochastic Programming Tags , , , , ,

    We present decomposition logarithmic-barrier interior-point methods based on unital Jordan-Hilbert algebras for infinite-dimensional stochastic second-order cone programming problems in spin factors. The results show that the iteration complexity of the proposed algorithms is independent on the choice of Hilbert spaces from which the underlying spin factors are formed, and so it coincides with the best … Read more