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
In this work we develop a primal-dual short-step interior point method for conic convex optimization problems for which exact evaluation of the gradient and Hessian of the barrier function is either impossible or too expensive. As our main contribution, we show that if approximate gradients and Hessians can be computed, and the relative errors in … Read more
The minimum k-partition (MkP) problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in the same partition. The main contribution of this paper is the design and implementation of a branch-and-cut algorithm based on semidefinite … Read more
Detecting infeasibility in conic optimization and providing certificates for infeasibility pose a bigger challenge than in the linear case due to the lack of strong duality. In this paper we generalize the approximate Farkas lemma of Todd and Ye from the linear to the general conic setting, and use it to propose stopping criteria for … Read more