Kim-Chuan Toh

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

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

    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

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

  • Naoki Ito
  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
  • Akiko Takeda
    • Categories Convex Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    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

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

  • Naoki Ito
  • Sunyoung Kim
  • Masakazu Kojima
  • Kim-Chuan Toh
  • Akiko Takeda
    • Categories Convex Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , , ,

    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

    Equivalences and Differences in Conic Relaxations of Combinatorial Quadratic Optimization Problems

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

    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

    On efficiently solving the subproblems of a level-set method for fused lasso problems

  • Xudong Li
  • Defeng Sun
  • Kim-Chuan Toh
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    In applying the level-set method developed in [Van den Berg and Friedlander, SIAM J. on Scientific Computing, 31 (2008), pp.~890–912 and SIAM J. on Optimization, 21 (2011), pp.~1201–1229] to solve the fused lasso problems, one needs to solve a sequence of regularized least squares subproblems. In order to make the level-set method practical, we develop … Read more

    A block symmetric Gauss-Seidel decomposition theorem for convex composite quadratic programming and its applications

  • Xudong Li
  • Defeng Sun
  • Kim-Chuan Toh
    • Categories Nonsmooth Optimization, Quadratic Programming Tags , ,

    For a symmetric positive semidefinite linear system of equations $\mathcal{Q} {\bf x} = {\bf b}$, where ${\bf x} = (x_1,\ldots,x_s)$ is partitioned into $s$ blocks, with $s \geq 2$, we show that each cycle of the classical block symmetric Gauss-Seidel (block sGS) method exactly solves the associated quadratic programming (QP) problem but added with an … Read more

    Max-Norm Optimization for Robust Matrix Recovery

  • Ethan Fang
  • Kim-Chuan Toh
  • Han Liu
  • Wen-Xin Zhou
    • Categories Convex Optimization, Semi-definite Programming, Statistics Tags , , ,

    This paper studies the matrix completion problem under arbitrary sampling schemes. We propose a new estimator incorporating both max-norm and nuclear-norm regularization, based on which we can conduct efficient low-rank matrix recovery using a random subset of entries observed with additive noise under general non-uniform and unknown sampling distributions. This method significantly relaxes the uniform … Read more

    A highly efficient semismooth Newton augmented Lagrangian method for solving Lasso problems

  • Xudong Li
  • Defeng Sun
  • Kim-Chuan Toh
    • Categories Nonsmooth Optimization Tags , , , ,

    We develop a fast and robust algorithm for solving large scale convex composite optimization models with an emphasis on the $\ell_1$-regularized least squares regression (Lasso) problems. Despite the fact that there exist a large number of solvers in the literature for the Lasso problems, we found that no solver can efficiently handle difficult large scale … Read more

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

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

    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

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

    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