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
In this paper we propose a new interior-point method, which is based on an extension of the ideas of self-scaled optimization to the general cones. We suggest using the primal correction process to find a {\em scaling point}. This point is used to compute a strictly feasible primal-dual pair by simple projection. Then, we define … Read more
Two corrector-predictor interior point algorithms are proposed for solving mono\-tone linear complementarity problems. The algorithms produce a sequence of iterates in the $\caln_{\infty}^{-}$ neighborhood of the central path. The first algorithm uses line search schemes requiring the solution of higher order polynomial equations in one variable, while the line search procedures of the second algorithm … Read more
We examine the problem of approximating a positive, semidefinite matrix $\Sigma$ by a dyad $xx^T$, with a penalty on the cardinality of the vector $x$. This problem arises in sparse principal component analysis, where a decomposition of $\Sigma$ involving sparse factors is sought. We express this hard, combinatorial problem as a maximum eigenvalue problem, in … Read more