On hyperbolicity cones associated with elementary symmetric polynomials

Categories Linear, Cone and Semidefinite Programming

Elementary symmetric polynomials can be thought of as derivative polynomials of $E_n(x)=\prod_{i=1,\ldots,n} x_i$. Their associated hyperbolicity cones give a natural sequence of relaxations for $\Re^n_+$. We establish a recursive structure for these cones, namely, that the coordinate projections of these cones are themselves hyperbolicity cones associated with elementary symmetric polynomials. As a consequence of this … Read more

Convergence Analysis of Inexact Infeasible Interior Point Method for Linear Optimization

Categories Linear Programming Tags , , ,

In this paper we present the convergence analysis of the inexact infeasible path-following(IIPF) interior point algorithm. In this algorithm the preconditioned conjugate gradient method is used to solve the reduced KKT system (the augmented system). The augmented system is preconditioned by using a block triangular matrix. The KKT system is solved approximately. Therefore, it becomes … Read more

Computational experience with general cutting planes for the Set Covering problem

Categories 0-1 Programming Tags ,

In this paper we present a cutting plane algorithm for the Set Covering problem. Cutting planes are generated by a “general” (i.e. not based on the “template paradigm”) separation algorithm based on the following idea: i) identify a suitably small subproblem defined by a subset of the constraints of the formulation; ii) run an exact … Read more

An Active-Set Algorithm for Nonlinear Programming Using Parametric Linear Programming

Categories Constrained Nonlinear Optimization Tags , , ,

This paper describes an active-set algorithm for nonlinear programming that solves a parametric linear programming subproblem at each iteration to generate an estimate of the active set. A step is then computed by solving an equality constrained quadratic program based on this active-set estimate. This approach respresents an extension of the standard sequential linear-quadratic programming … Read more

Regularization and Preconditioning of KKT Systems Arising in Nonnegative Least-Squares Problems

Categories Bound-constrained Optimization Tags , , , ,

A regularized Newton-like method for solving nonnegative least-squares problems is proposed and analysed in this paper. A preconditioner for KKT systems arising in the method is introduced and spectral properties of the preconditioned matrix are analysed. A bound on the condition number of the preconditioned matrix is provided. The bound does not depend on the … Read more

Local convergence for alternating and averaged nonconvex projections

Categories Constrained Nonlinear Optimization, Control Applications, Nonsmooth Optimization Tags , , , , , , , ,

The idea of a finite collection of closed sets having “strongly regular intersection” at a given point is crucial in variational analysis. We show that this central theoretical tool also has striking algorithmic consequences. Specifically, we consider the case of two sets, one of which we assume to be suitably “regular” (special cases being convex … Read more

The Transportation Paradox Revisited

Categories Linear Programming, Transportation

The transportation paradox is related to the classical transportation problem. For certain instances of this problem an increase in the amount of goods to be transported may lead to a decrease in the optimal total transportation cost. Even though the paradox has been known since the early days of linear programming, it has got very … Read more

The Squared Slacks Transformation in Nonlinear Programming

Categories Constrained Nonlinear Optimization Tags , ,

We recall the use of squared slacks used to transform inequality constraints into equalities and several reasons why their introduction may be harmful in many algorithmic frameworks routinely used in nonlinear programming. Numerical examples performed with the sequential quadratic programming method illustrate those reasons. CitationCahier du GERAD G-2007-62, Aug. 2007ArticleDownload View PDF

Optimality and uniqueness of the (4,10,1/6) spherical code

Categories Semi-definite Programming Tags , , , ,

Traditionally, optimality and uniqueness of an (n,N,t) spherical code is proved using linear programming bounds. However, this approach does not apply to the parameter (4,10,1/6). We use semidefinite programming bounds instead to show that the Petersen code (which are the vertices of the 4-dimensional second hypersimplex or the midpoints of the edges of the regular … Read more

Semidefinite Programming for Gradient and Hessian Computation in Maximum Entropy Estimation

Categories Applications - Science and Engineering, Convex Optimization, Semi-definite Programming

We consider the classical problem of estimating a density on $[0,1]$ via some maximum entropy criterion. For solving this convex optimization problem with algorithms using first-order or second-order methods, at each iteration one has to compute (or at least approximate) moments of some measure with a density on $[0,1]$, to obtain gradient and Hessian data. … Read more