An interesting recent trend in optimization is the application of semidefinite programming techniques to new classes of optimization problems. In particular, this trend has been successful in showing that under suitable circumstances, polynomial optimization problems can be approximated via a sequence of semidefinite programs. Similar ideas apply to conic optimization over the cone of copositive … Read more
In 1958 Lax conjectured that hyperbolic polynomials in three variables are determinants of linear combinations of three symmetric matrices. This conjecture is equivalent to a recent observation of Helton and Vinnikov. CitationDepartment of Mathematics, Simon Fraser University, CanadaArticleDownload View PDF
The facility layout problem is concerned with finding the most efficient arrangement of a given number of departments with unequal area requirements within a facility. The facility layout problem is a hard problem, and therefore, exact solution methods are only feasible for small or greatly restricted problems. In this paper, we propose a spring-embedding approach … Read more
Consider the problem of finding optimal bounds on the expected value of piece-wise polynomials over all measures with a given set of moments. We show that this problem can be studied within the framework of conic programming. Relying on a key approximation result for conic programming, we show that these bounds can be numerically computed … Read more
We study the issue of updating the analytic center after multiple cutting planes have been added through the analytic center of the current polytope in Euclidean n-space. This is an important issue that arises at every `stage’ in a cutting plane algorithm. If q cuts are to be added, with q no larger than n, … Read more
We present a framework for designing and analyzing primal-dual interior-point methods for convex optimization. We assume that a self-concordant barrier for the convex domain of interest and the Legendre transformation of the barrier are both available to us. We directly apply the theory and techniques of interior-point methods to the given good formulation of the … Read more
This paper attempts to extend the notion of duality for convex cones, by basing it on a pre-described conic ordering and a fixed bilinear mapping. This is an extension of the standard definition of dual cones, in the sense that the {\em nonnegativity}\/ of the inner-product is replaced by a pre-specified conic ordering, defined by … Read more
The affine-scaling algorithm was initially developed for linear programming problems. Its extension to problems with a nonlinear objective performs at each iteration a scaling followed by a line search along the steepest descent direction. In this paper we prove that any accumulation point generated by this algorithm when applied to a convex function is an … Read more
The trust region subproblem (the minimization of a quadratic objective subject to one quadratic constraint and denoted TRS) has many applications in diverse areas, e.g. function minimization, sequential quadratic programming, regularization, ridge regression, and discrete optimization. In particular, it determines the step in trust region algorithms for function minimization. Trust region algorithms are popular for … Read more
We present a practical algorithm for computing the minimum volume n-dimensional ellipsoid that must contain m given points a_1, …, a_m \in R^n. This convex constrained problem arises in a variety of applied computational settings, particularly in data mining and robust statistics. Its structure makes it particularly amenable to solution by interior-point methods, and it … Read more