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
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
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
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
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
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
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
We correct an error in Algorithms 4.1 and 4.8 from the paper with the same title that was published in Optimization Methods and Software, 20, 1 (2005), 145–168. Citationsubmitted to Optimization Methods and SoftwareArticleDownload View PDF
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
In this paper we develop a technique for constructing self-concordant barriers for convex cones. We start from a simple proof for a variant of standard result on transformation of a $\nu$-self-concordant barrier for a set into a self-concordant barrier for its conic hull with parameter $(3.08 \sqrt{\nu} + 3.57)^2$. Further, we develop a convenient composition … Read more