Target following algorithms for semidefinite programming

We present a target-following framework for semidefinite programming, which generalizes the target-following framework for linear programming. We use this framework to build weighted path-following interior-point algorithms of three distinct flavors: short-step, predictor-corrector, and large-update. These algorithms have worse-case iteration bounds that parallel their counterparts in linear programming. We further consider the problem of finding analytic … Read more

Recognizing Underlying Sparsity in Optimization

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 … Read more

Implementation of Warm-Start Strategies in Interior-Point Methods for Linear Programming in Fixed Dimension

We implement several warm-start strategies in interior-point methods for linear programming (LP). We study the situation in which both the original LP instance and the perturbed one have exactly the same dimensions. We consider different types of perturbations of data components of the original instance and different sizes of each type of perturbation. We modify … Read more

Exploiting Equalities in Polynomial Programming

We propose a novel solution approach for polynomial programming problems with equality constraints. By means of a generic transformation, we show that solution schemes for the (typically simpler) problem without equalities can be used to address the problem with equalities. In particular, we propose new solution schemes for mixed binary programs, pure 0-1 quadratic programs, … Read more

New Korkin-Zolotarev Inequalities

Korkin and Zolotarev showed that if $$\sum_i A_i(x_i-\sum_{j>i} \alpha_{ij}x_j)^2$$ is the Lagrange expansion of a Korkin–Zolotarev reduced positive definite quadratic form, then $A_{i+1}\geq \frac{3}{4} A_i$ and $A_{i+2}\geq \frac{2}{3}A_i$. They showed that the implied bound $A_{5}\geq \frac{4}{9}A_1$ is not attained by any KZ-reduced form. We propose a method to optimize numerically over the set of Lagrange … Read more

Optimization of univariate functions on bounded intervals by interpolation and semidefinite programming

We consider the problem of minimizing a univariate, real-valued function f on an interval [a,b]. When f is a polynomial, we review how this problem may be reformulated as a semidefinite programming (SDP) problem, and review how to extract all global minimizers from the solution of the SDP problem. For general f, we approximate the … Read more

Convergent SDP-relaxations in polynomial optimization with sparsity

We consider a polynomial programming problem P on a compact basic semi-algebraic set K described by m polynomial inequalities $g_j(X)\geq0$, and with polynomial criterion $f$. We propose a hierarchy of semidefinite relaxations in the spirit those of Waki et al. [9]. In particular, the SDP-relaxation of order $r$ has the following two features: (a) The … Read more

Nonsymmetric potential-reduction methods for general cones

In this paper we propose two new nonsymmetric primal-dual potential-reduction methods for conic problems. Both methods are based on {\em primal-dual lifting}. This procedure allows to construct a strictly feasible primal-dual pair linked by an exact {\em scaling} relation even if the cones are not symmetric. It is important that all necessary elements of our … Read more

Erratum: A superlinearly convergent predictor-corrector method for degenerate LCP in a wide neighborhood of the central path with (\sqrt{n}L)hBciteration complexity

We correct an error in Algorithm 2 from the paper with the same name that was published in Mathematical Programming, Ser. A, 100, 2(2004), 317–337. Citationsubmitted to Mathematical ProgrammingArticleDownload View PDF

Corrector-predictor methods for sufficient linear complementarity problems in a wide neighborhood of the central path

Corrector-predictor methods for sufficient linear complementarity problems in a wide neighborhood of the central path CitationTechnical Report UMBC, TR2006-22, January 2005, Revised: March 2006.ArticleDownload View PDF