A new method for the efficient solution of free material optimization problems is introduced. The method extends the sequential convex programming (SCP) concept to a class of optimization problems with matrix variables. The basic idea of the new method is to approximate the original optimization problem by a sequence of subproblems, in which nonlinear functions … Read more
Abstract: After developing necessary background theory, the original primal and dual are specified, and the invariant primal and dual LP’s are defined. Pairs of linear mappings are defined which establish an effectively one-to-one correspondences between solutions to the original and invariant problems. The invariant problems are recast as a fixed-point problem and precise solution conditions … Read more
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
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
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
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
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
We present a strong duality theory for optimization problems over symmetric cones without assuming any constraint qualification. We show important complexity implications of the result to semidefinite and second order conic optimization. The result is an application of Borwein and Wolkowicz’s facial reduction procedure to express the minimal cone. We use Pataki’s simplified analysis and … Read more
Let L_n be the n-dimensional second order cone. A linear map from R^m to R^n is called positive if the image of L_m under this map is contained in L_n. For any pair (n,m) of dimensions, the set of positive maps forms a convex cone. We construct a linear matrix inequality of size (n-1)(m-1) that … Read more
Consider linear programs in dual standard form with n constraints and m variables. When typical interior-point algorithms are used for the solution of such problems, updating the iterates, using direct methods for solving the linear systems and assuming a dense constraint matrix A, requires O(nm^2) operations. When n>>m it is often the case that at … Read more