conic relaxations

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

    User manual of NewtBracket: “A Newton-Bracketing method for a simple conic optimization problem” with applications to QOPs in binary variables

  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    We describe the Matlab package NewtBracket for solving a simple conic optimization problem that minimizes a linear objective function subject to a single linear equality constraint and a convex cone constraint. The problem is converted into the problem of finding the largest zero $y^*$ of a continuously differentiable (except at $y^*$) convex function $g : … Read more

    A Newton-bracketing method for a simple conic optimization problem

  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    For the Lagrangian-DNN relaxation of quadratic optimization problems (QOPs), we propose a Newton-bracketing method to improve the performance of the bisection-projection method implemented in BBCPOP [to appear in ACM Tran. Softw., 2019]. The relaxation problem is converted into the problem of finding the largest zero $y^*$ of a continuously differentiable (except at $y^*$) convex function … Read more

    CONICOPF: Conic relaxations for AC optimal power flow computations

  • Christian Bingane
  • Miguel F. Anjos
  • Sébastien Le Digabel
    • Categories Semi-definite Programming Tags , , ,

    Computational speed and global optimality are key needs for practical algorithms for the optimal power flow problem. Two convex relaxations offer a favorable trade-off between the standard second-order cone and the standard semidefinite relaxations for large-scale meshed networks in terms of optimality gap and computation time: the tight-and-cheap relaxation (TCR) and the quadratic convex relaxation … Read more

    DC Decomposition of Nonconvex Polynomials with Algebraic Techniques

  • Amir Ali Ahmadi
  • Georgina Hall
    • Categories Global Optimization, Linear, Cone and Semidefinite Programming, Statistics Tags , , ,

    We consider the problem of decomposing a multivariate polynomial as the difference of two convex polynomials. We introduce algebraic techniques which reduce this task to linear, second order cone, and semidefinite programming. This allows us to optimize over subsets of valid difference of convex decompositions (dcds) and find ones that speed up the convex-concave procedure … Read more