We introduce a computer program PENNON for the solution of problems of convex Nonlinear and Semidefinite Programming (NLP-SDP). The algorithm used in PENNON is a generalized version of the Augmented Lagrangian method, originally introduced by Ben-Tal and Zibulevsky for convex NLP problems. We present generalization of this algorithm to convex NLP-SDP problems, as implemented in … Read more
We show that SDP (semidefinite programming) and SOCP (second order cone programming) relaxations provide exact optimal solutions for a class of nonconvex quadratic optimization problems. It is a generalization of the results by S.~Zhang for a subclass of quadratic maximization problems that have nonnegative off-diagonal coefficient matrices of objective quadratic functions and diagonal coefficient matrices … Read more
DSDP4 is an implementation of the dual-scaling algorithm for semidefinite program ming. New features in this version include a Lanczos procedure for determining the step size, more precise primal solutions, a parallel solver, and improved performance on the standard test suites. Citation ANL/MCS-TM-255; Mathematics and Computer Science Division; Argonne National Laboratory; Argonne, IL; March 2002 … Read more
This paper demonstrates how interior-point methods can use multiple processors efficiently to solve large semidefinite programs that arise in VLSI design, control theory, and graph coloring. Previous implementations of these methods have been restricted to a single processor. By computing and solving the Schur complement matrix in parallel, multiple processors enable the faster solution of … Read more
We present a $.73$-approximation algorithm for a disjoint $2$-Catalog Segmentation and $.63$-approximation algorithm for the joint version of the problem. Previously best known results are $.65$ and $.56$, respectively. The results are based on semidefinite programming and a subtle rounding method. Citation Working Paper, Department of Management Sciences, Henry, B. Tippie College of Business, The … Read more
The convex feasibility problem asks to find a point in the intersection of finitely many closed convex sets in Euclidean space. This problem is of fundamental importance in mathematics and physical sciences, and it can be solved algorithmically by the classical method of cyclic projections. In this paper, the case where one of the constraints … Read more
GloptiPoly is a Matlab/SeDuMi add-on to build and solve convex linear matrix inequality relaxations of the (generally non-convex) global optimization problem of minimizing a multivariable polynomial function subject to polynomial inequality, equality or integer constraints. It generates a series of lower bounds monotonically converging to the global optimum. Numerical experiments show that for most of … Read more
We present large-scale optimization techniques to model the energy function that underlies the folding process of proteins. Linear Programming is used to identify parameters in the energy function model, the objective being that the model predict the structure of known proteins correctly. Such trained functions can then be used either for {\em ab-initio} prediction or … Read more
Recently,Tseng extended a class of merit functions for the nonlinear complementarity problem to semidefinite complementarity problem (SDCP), showing some properties under suitable assumptions. Yamashita and Fukushima also presented other properties. In this paper, we propose a new class of merit functions for the SDCP, and prove some of those properties, under weaker hypothesis. Particularly, we … Read more
The goal of this paper is to develop some computational experience and test the practical relevance of the theory of condition numbers C(d) for linear optimization, as applied to problem instances that one might encounter in practice. We used the NETLIB suite of linear optimization problems as a test bed for condition number computation and … Read more