Recognizing Underlying Sparsity in Optimization

Sunyoung Kim (skimewha.ac.kr)
Masakazu Kojima (kojimais.titech.ac.jp)
Philippe Toint (philippe.tointfundp.ac.be)

Abstract: Exploiting sparsity is essential to improve the efficiency of solving large optimization problems. We present a method for recognizing the underlying sparsity structure of a nonlinear partially separable problem, and show how the sparsity of the Hessian matrices of the problem's functions can be improved by performing a nonsingular linear transformation in the space corresponding to the vector of variables. A combinatorial optimization problem is then formulated to increase the number of zeros of the Hessian matrices in the resulting transformed space, and a heuristic greedy algorithm is applied to this formulation. The resulting method can thus be viewed as a preprocessor for converting a problem with hidden sparsity into one in which sparsity is explicit. When it is combined with the sparse semidefinite programming (SDP) relaxation by Waki et al. for polynomial optimization problems (POPs), the proposed method is shown to extend the performance and applicability of this relaxation technique. Preliminary numerical results are presented to illustrate this claim.

Keywords: Sparsity, Partial Separability, Semidefinite Programming Relaxation, Polynomial Optimization, Combinatorial Optimization

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Combinatorial Optimization

Citation: Research Report B-428, Department of Mathematical Sciences, Tokyo Institute of Technology, Tokyo 152-8552, Japan, May 2006. Also Report 06/02, Department of Mathematics, University of Namur, Namur, Belgium, May 2006.

Download: [PDF]

Entry Submitted: 05/12/2006
Entry Accepted: 05/12/2006
Entry Last Modified: 05/12/2006

Modify/Update this entry