Masakazu Kojima – Page 2 – Optimization Online

Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures

Published: 2019/03/18

We study the equivalence among a nonconvex QOP, its CPP and DNN relaxations under the assumption that the aggregated and correlative sparsity of the data matrices of the CPP relaxation is represented by a block-clique graph $G$. By exploiting the correlative sparsity, we decompose the CPP relaxation problem into a clique-tree structured family of smaller … Read more

A Geometrical Analysis of a Class of Nonconvex Conic Programs for Convex Conic Reformulations of Quadratic and Polynomial Optimization Problems

Published: 2019/01/08

Sunyoung Kim

Masakazu Kojima

Kim-Chuan Toh

Linear, Cone and Semidefinite Programming completely positive reformulation of quadratic and polynomial optimization problems, conic optimization problems, faces of the completely positive cone, hierarchies of copositivity

We present a geometrical analysis on the completely positive programming reformulation of quadratic optimization problems and its extension to polynomial optimization problems with a class of geometrically defined nonconvex conic programs and their covexification. The class of nonconvex conic programs is described with a linear objective function in a linear space $V$, and the constraint … Read more

BBCPOP: A Sparse Doubly Nonnegative Relaxation of Polynomial Optimization Problems with Binary, Box and Complementarity Constraints

Published: 2018/04/02, Updated: 2018/04/03

Convex Optimization, Global Optimization, Linear, Cone and Semidefinite Programming bisection and projection methods, box and complementarity constraints, efficiency, hierarchy of doubly nonnegative relaxations, high-degree polynomial optimization problems with binary, matlab software package, sparsity, tight lower bounds

The software package BBCPOP is a MATLAB implementation of a hierarchy of sparse doubly nonnegative (DNN) relaxations of a class of polynomial optimization (minimization) problems (POPs) with binary, box and complementarity (BBC) constraints. Given a POP in the class and a relaxation order, BBCPOP constructs a simple conic optimization problem (COP), which serves as a … Read more

User Manual for BBCPOP: A Sparse Doubly Nonnegative Relaxation of Polynomial Optimization Problems with Binary, Box and Complementarity Constraints

Published: 2018/04/02, Updated: 2018/04/03

Convex Optimization, Global Optimization, Linear, Cone and Semidefinite Programming bisection and projection method, doubly nonnegative relaxation, large-scale optimization, matlab software package, polynomial optimization problems

BBCPOP proposed in [4] is a MATLAB implementation of a hierarchy of sparse doubly nonnegative (DNN) relaxations of a class of polynomial optimization (minimization) problems (POPs) with binary, box and complementarity constraints. Given a POP in the class and a relaxation order (or a hierarchy level), BBCPOP constructs a simple conic optimization problem (COP), which … Read more

Equivalences and Differences in Conic Relaxations of Combinatorial Quadratic Optimization Problems

Published: 2017/07/22

Linear, Cone and Semidefinite Programming binary and complementarity con- dition, completely positive relaxations, doubly nonnegative relaxations, equivalence of feasible regions, nondegeneracy, ombinatorial optimization problems, semidefinite relaxation

Various conic relaxations of quadratic optimization problems in nonnega- tive variables for combinatorial optimization problems, such as the binary integer quadratic problem, quadratic assignment problem (QAP), and maximum stable set problem have been proposed over the years. The binary and complementarity conditions of the combi- natorial optimization problems can be expressed in several ways, each … Read more

Doubly Nonnegative Relaxations for Quadratic and Polynomial Optimization Problems with Binary and Box Constraints

Published: 2016/07/07, Updated: 2017/12/06

Sunyoung Kim

Masakazu Kojima

Kim-Chuan Toh

Linear, Cone and Semidefinite Programming a class of polyhedral cones, doubly nonnegative relaxations, polynomial optimization problems with nonnegative variables, the bisection and projection algorithm

We propose a doubly nonnegative (DNN) relaxation for polynomial optimization problems (POPs) with binary and box constraints. This work is an extension of the work by Kim, Kojima and Toh in 2016 from quadratic optimization problems (QOPs) to POPs. The dense and sparse DNN relaxations are reduced to a simple conic optimization problem (COP) to … Read more

A robust Lagrangian-DNN method for a class of quadratic optimization problems

Published: 2016/02/29

Linear, Cone and Semidefinite Programming, Quadratic Programming improved bisection method, nonconvex quadratic optimization problems with nonnegative variables, the lagrangian-dnn relaxation, the validity of lower bounds

The Lagrangian-doubly nonnegative (DNN) relaxation has recently been shown to provide effective lower bounds for a large class of nonconvex quadratic optimization problems (QOPs) using the bisection method combined with first-order methods by Kim, Kojima and Toh in 2016. While the bisection method has demonstrated the computational efficiency, determining the validity of a computed lower … Read more

Lagrangian-Conic Relaxations, Part II: Applications to Polynomial Optimization Problems

Published: 2014/01/09

Convex Optimization, Semi-definite Programming exploiting sparsity, moment cone relaxation, polynomial optimization problem, semidefinite programming, sos relaxation

We present the moment cone (MC) relaxation and a hierarchy of sparse Lagrangian-SDP relaxations of polynomial optimization problems (POPs) using the unified framework established in Part I. The MC relaxation is derived for a POP of minimizing a polynomial subject to a nonconvex cone constraint and polynomial equality constraints. It is an extension of the … Read more

Lagrangian-Conic Relaxations, Part I: A Unified Framework and Its Applications to Quadratic Optimization Problems

Published: 2014/01/06

Convex Optimization, Linear, Cone and Semidefinite Programming completely positive programming relaxation, convexification, doubly nonnegative relaxation, exploiting sparsity, lagrangian-conic relaxation, quadratic programming

In Part I of a series of study on Lagrangian-conic relaxations, we introduce a unified framework for conic and Lagrangian-conic relaxations of quadratic optimization problems (QOPs) and polynomial optimization problems (POPs). The framework is constructed with a linear conic optimization problem (COP) in a finite dimensional vector space endowed with an inner product, where the … Read more

A Lagrangian-DNN Relaxation: a Fast Method for Computing Tight Lower Bounds for a Class of Quadratic Optimization Problems

Published: 2013/10/08

Sunyoung Kim

Masakazu Kojima

Kim-Chuan Toh

Linear, Cone and Semidefinite Programming, Quadratic Programming bisection method, iterative solver, linearly constrained quadratic optimization problems with complementarity constraints, the lagrangian-conic relaxation

We propose an efficient computational method for linearly constrained quadratic optimization problems (QOPs) with complementarity constraints based on their Lagrangian and doubly nonnegative (DNN) relaxation and first-order algorithms. The simplified Lagrangian-CPP relaxation of such QOPs proposed by Arima, Kim, and Kojima in 2012 takes one of the simplest forms, an unconstrained conic linear optimization problem … Read more