Computational and Theoretical Perspectives on Complexity for Linear, Conic, and Non-conic Convex Optimization

Robert M. Freund
Sloan School of Management Building
Cambridge, MA

We consider the following quite general convex optimization problem format:

           Gd: minimize cT x
s.t.          A x = b 
              x in P

where P is a closed convex set, not necessarily a cone. Linear optimization is a special case of this format in the case when P is the nonnegative orthant. Complexity theory for linear optimization has evolved from the bit-model based on the encoding length L, and interior-point methods (IPMs) have played a major role in suggesting new ways to think about and to bound the complexity of solving linear optimization. One avenue of research on complexity theory for linear optimization is based on Renegar's condition number C(d) for the data d=(A,b,c) for Gd. We develop some computational experience and test the practical relevance of this condition number theory, as applied to problem instances that one might encounter in practice, using the NETLIB suite of LP problem instances. We present empirical evidence that indicates that 42% of the variation in IPM iterations among the NETLIB suite problem instances is accounted for by log C(d) of the problem instances after pre-processing, and that log C(d) correlates better with IPM iterations than do other dimension-based measures.

On the other hand, there are a number of drawbacks in using the condition number theory to investigate the complexity of convex optimization, including its restriction to conic problems, undue data dependency, and the omission of warm-start information, among others. We develop therefore have tried to develop a theory of complexity for convex optimization using geometry-based measures rather than algebraic or data-based measures for obtaining complexity bounds. We bound the complexity of computing an almost-optimal solution of Gd in terms of natural geometry-based measures of the feasible region and the level-set of almost-optimal solutions, relative to a given reference point xr that might be close to the feasible region and/or the almost-optimal level set.