  


On the Behavior of the Homogeneous SelfDual Model for Conic Convex Optimization
Robert M. Freund (rfreundmit.edu) Abstract: There is a natural norm associated with a starting point of the homogeneous selfdual (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 epsilonoptimal solutions, and (ii) the maximum distance of epsilonoptimal solutions to the boundary of the cone of the HSD variables. This norm is also useful in developing a stoppingrule theory for HSDbased interiorpoint methods such as SeDuMi. Under mild assumptions, we show that a standard stopping rule implicitly involves the sum of the sizes of the epsilonoptimal primal and dual solutions, as well as the size of the initial primal and dual infeasibility residuals. This theory suggests possible criteria for developing starting points for the homogeneous selfdual model that might improve the resulting solution time in practice. Keywords: conic convex optimization, selfdual embedding, homogeneous selfdual, convex cone, selfscaled cone, level sets Category 1: Linear, Cone and Semidefinite Programming Category 2: Linear, Cone and Semidefinite Programming (Semidefinite Programming ) Citation: MIT Operations Research Center Working Paper OR 37204 Download: [Postscript] Entry Submitted: 10/15/2004 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  