Robert M. Freund We study four measures of problem instance behavior that might account for the observed differences in interior-point method (IPM) iterations when these methods are used to solve semidefinite programming (SDP) problem instances: (i) an aggregate geometry measure related to the primal and dual feasible regions (aspect ratios) and norms of the optimal solutions, (ii) the … Read more
There is a natural norm associated with a starting point of the homogeneous self-dual (HSD) embedding model for conic convex optimization. In this norm two measures of the HSD model’s behavior are precisely controlled independent of the problem instance: (i) the sizes of epsilon-optimal solutions, and (ii) the maximum distance of epsilon-optimal solutions to the … Read more
Given a convex body S and a point x \in S, let sym(x,S) denote the symmetry value of x in S: sym(x,S):= max{t : x + t(x – y) \in S for every y \in S}, which essentially measures how symmetric S is about the point x, and define sym(S):=\max{sym(x,S) : x \in S }. … Read more
The purpose of this paper is to extend, as much as possible, the modern theory of condition numbers for conic convex optimization: z_* := min_x {c’x | Ax-b \in C_Y, x \in C_X }, to the more general non-conic format: (GP_d): z_* := min_x {c’x | Ax-b \in C_Y, x \in P}, where P is … 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
The goal of this paper is to develop some computational experience and test the practical relevance of the theory of condition numbers C(d) for linear optimization, as applied to problem instances that one might encounter in practice. We used the NETLIB suite of linear optimization problems as a test bed for condition number computation and … Read more
Our concern lies in solving the following convex optimization problem: minimize cx subject to Ax=b, x \in P, where P is a closed convex set, not necessarily a cone. We bound the complexity of computing an almost-optimal solution of this problem in terms of natural geometry-based measures of the feasible region and the level-set of … Read more
For a conic optimization problem: minimize cx subject to Ax=b, x \in C, we present a geometric relationship between the maximum norms of the level sets of the primal and the inscribed sizes of the level sets of the dual (or the other way around). Citation MIT Operations Research Center Working Paper Article Download View … Read more