Simplified Copositive and Lagrangian Relaxations for Linearly Constrained Quadratic Optimization Problems in Continuous and Binary Variables

For a quadratic optimization problem (QOP) with linear equality constraints in continuous nonnegative variables and binary variables, we propose three relaxations in simplified forms with a parameter $\lambda$: Lagrangian, completely positive, and copositive relaxations. These relaxations are obtained by reducing the QOP to an equivalent QOP with a single quadratic equality constraint in nonnegative variables, … Read more

A Quadratically Constrained Quadratic Optimization Model for Completely Positive Cone Programming

We propose a class of quadratic optimization problems whose exact optimal objective values can be computed by their completely positive cone programming relaxations. The objective function can be any quadratic form. The constraints of each problem are described in terms of quadratic forms with no linear terms, and all constraints are homogeneous equalities, except one … Read more

Enclosing Ellipsoids and Elliptic Cylinders of Semialgebraic Sets and Their Application to Error Bounds in Polynomial Optimization

This paper is concerned with a class of ellipsoidal sets (ellipsoids and elliptic cylinders) in the m-dimensional Euclidean space which are determined by a freely chosen positive semidefinite matrix. All ellipsoidal sets in this class are similar to each other through a parallel transformation and a scaling around their centers by a constant factor. Based … Read more

SFSDP: a Sparse Version of Full SemiDefinite Programming Relaxation for Sensor Network Localization Problems

SFSDP is a Matlab package for solving a sensor network localization problem. These types of problems arise in monitoring and controlling applications using wireless sensor networks. SFSDP implements the semidefinite programming (SDP) relaxation proposed in Kim et al. [2009] for sensor network localization problems, as a sparse version of the full semidefinite programming relaxation (FSDP) … Read more

User’s Manual for SparseCoLO: Conversion Methods for Sparse Conic-form Linear Optimization Problems

SparseCoLO is a Matlab package for implementing the four conversion methods, proposed by Kim, Kojima, Mevissen, and Yamashita, via positive semidefinite matrix completion for an optimization problem with matrix inequalities satisfying a sparse chordal graph structure. It is based on quite a general description of optimization problem including both primal and dual form of linear, … Read more

Exploiting Sparsity in Linear and Nonlinear Matrix Inequalities via Positive Semidefinite Matrix Completion

A basic framework for exploiting sparsity via positive semidefinite matrix completion is presented for an optimization problem with linear and nonlinear matrix inequalities. The sparsity, characterized with a chordal graph structure, can be detected in the variable matrix or in a linear or nonlinear matrix-inequality constraint of the problem. We classify the sparsity in two … Read more

Exploiting Sparsity in SDP Relaxation for Sensor Network Localization

A sensor network localization problem can be formulated as a quadratic optimization problem (QOP). For quadratic optimization problems, semidefinite programming (SDP) relaxation by Lasserre with relaxation order 1 for general polynomial optimization problems (POPs) is known to be equivalent to the sparse SDP relaxation by Waki {¬•it et al.} with relaxation order 1, except the … Read more

A Numerical Algorithm for Block-Diagonal Decomposition of Matrix *-Algebras, Part I: Proposed Approach and Application to Semidefinite Programming

Motivated by recent interest in group-symmetry in semidefinite programming, we propose a numerical method for finding a finest simultaneous block-diagonalization of a finite number of matrices, or equivalently the irreducible decomposition of the generated matrix *-algebra. The method is composed of numerical-linear algebraic computations such as eigenvalue computation, and automatically makes full use of the … Read more

Efficient Evaluation of Polynomials and Their Partial Derivatives in Homotopy Continuation Methods

The aim of this paper is to study how efficiently we evaluate a system of multivariate polynomials and their partial derivatives in homotopy continuation methods. Our major tool is an extension of the Hornor scheme, which is popular in evaluating a univariate polynomial, to a multivariate polynomial. But the extension is not unique, and there … Read more

Correlative sparsity in primal-dual interior-point methods for LP, SDP and SOCP

Exploiting sparsity has been a key issue in solving large-scale optimization problems. The most time-consuming part of primal-dual interior-point methods for linear programs, second-order cone programs, and semidefinite programs is solving the Schur complement equation at each iteration, usually by the Cholesky factorization. The computational efficiency is greatly affected by the sparsity of the coefficient … Read more