Kim-Chuan Toh

On the implementation and usage of SDPT3 — a Matlab software package for semidefinite-quadratic-linear programming, version 4.0

  • Michael J. Todd
  • Kim-Chuan Toh
  • Reha H. Tütüncü
    • Categories Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems

    This software is designed to solve primal and dual semidefinite-quadratic-linear conic programming problems (known as SQLP problems) whose constraint cone is a product of semidefinite cones, second-order cones, nonnegative orthants and Euclidean spaces, and whose objective function is the sum of linear functions and log-barrier terms associated with the constraint cones. This includes the special … Read more

    An inexact interior point method for L1-regularized sparse covariance selection

  • Lu Li
  • Kim-Chuan Toh
    • Categories Convex Optimization, Semi-definite Programming, Statistics Tags , , , ,

    Sparse covariance selection problems can be formulated as log-determinant (log-det) semidefinite programming (SDP) problems with large numbers of linear constraints. Standard primal-dual interior-point methods that are based on solving the Schur complement equation would encounter severe computational bottlenecks if they are applied to solve these SDPs. In this paper, we consider a customized inexact primal-dual … Read more

    Solving log-determinant optimization problems by a Newton-CG primal proximal point algorithm

  • Defeng Sun
  • Kim-Chuan Toh
  • Chengjing Wang
    • Categories Convex Optimization, Semi-definite Programming, Statistics Tags , ,

    We propose a Newton-CG primal proximal point algorithm for solving large scale log-determinant optimization problems. Our algorithm employs the essential ideas of the proximal point algorithm, the Newton method and the preconditioned conjugate gradient solver. When applying the Newton method to solve the inner sub-problem, we find that the log-determinant term plays the role of … Read more

    An Implementable Proximal Point Algorithmic Framework for Nuclear Norm Minimization

  • Yong-Jin Liu
  • Defeng Sun
  • Kim-Chuan Toh
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    The nuclear norm minimization problem is to find a matrix with the minimum nuclear norm subject to linear and second order cone constraints. Such a problem often arises from the convex relaxation of a rank minimization problem with noisy data, and arises in many fields of engineering and science. In this paper, we study inexact … Read more

    An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems

  • Kim-Chuan Toh
  • Sangwoon Yun
    • Categories Convex Optimization, Data-Mining, Semi-definite Programming Tags , , ,

    The affine rank minimization problem, which consists of finding a matrix of minimum rank subject to linear equality constraints, has been proposed in many areas of engineering and science. A specific rank minimization problem is the matrix completion problem, in which we wish to recover a (low-rank) data matrix from incomplete samples of its entries. … Read more

    An SDP-based divide-and-conquer algorithm for large scale noisy anchor-free graph realization

  • Ngai-Hang Z. Leung
  • Kim-Chuan Toh
    • Categories Basic Sciences Applications, Global Optimization Applications, Semi-definite Programming Tags , , ,

    We propose the DISCO algorithm for graph realization in $\real^d$, given sparse and noisy short-range inter-vertex distances as inputs. Our divide-and-conquer algorithm works as follows. When a group has a sufficiently small number of vertices, the basis step is to form a graph realization by solving a semidefinite program. The recursive step is to break … Read more

    A Coordinate Gradient Descent Method for L_1-regularized Convex Minimization

  • Kim-Chuan Toh
  • Sangwoon Yun
    • Categories Convex and Nonsmooth Optimization Tags , , , , , , ,

    In applications such as signal processing and statistics, many problems involve finding sparse solutions to under-determined linear systems of equations. These problems can be formulated as a structured nonsmooth optimization problems, i.e., the problem of minimizing L_1-regularized linear least squares problems. In this paper, we propose a block coordinate gradient descent method (abbreviated as CGD) … Read more

    A Newton-CG Augmented Lagrangian Method for Semidefinite Programming

  • Defeng Sun
  • Kim-Chuan Toh
  • Xinyuan Zhao
    • Categories Nonsmooth Optimization, Semi-definite Programming Tags , , ,

    We consider a Newton-CG augmented Lagrangian method for solving semidefinite programming (SDP) problems from the perspective of approximate semismooth Newton methods. In order to analyze the rate of convergence of our proposed method, we characterize the Lipschitz continuity of the corresponding solution mapping at the origin. For the inner problems, we show that the positive … Read more

    An inexact primal-dual path following algorithm for convex quadratic SDP

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

    We propose primal-dual path-following Mehrotra-type predictor-corrector methods for solving convex quadratic semidefinite programming (QSDP) problems of the form: $\min_{X} \{ \frac{1}{2} X\bullet {\cal Q}(X) + C\bullet X : {\cal A} (X) = b, X\succeq 0\}$, where ${\cal Q}$ is a self-adjoint positive semidefinite linear operator on ${\cal S}^n$, $b\in R^m$, and ${\cal A}$ is a … Read more

    Inexact primal-dual path-following algorithms for a special class of convex quadratic SDP and related problems

  • Michael J. Todd
  • Kim-Chuan Toh
  • Reha H. Tütüncü
    • Categories Semi-definite Programming Tags , , , ,

    We propose a primal-dual path-following Mehrotra-type predictor-corrector method for solving convex quadratic semidefinite programming (QSDP) problems. For the special case when the quadratic term has the form $\frac{1}{2} X \bul (UXU)$, we compute the search direction at each iteration from the Schur complement equation. We are able to solve the Schur complement equation efficiently via … Read more