- | ||||
|
![]()
|
On the Behavior of the Homogeneous Self-Dual Model for Conic Convex Optimization
Robert M. Freund (rfreund Abstract: 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 boundary of the cone of the HSD variables. This norm is also useful in developing a stopping-rule theory for HSD-based interior-point methods such as SeDuMi. Under mild assumptions, we show that a standard stopping rule implicitly involves the sum of the sizes of the epsilon-optimal 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 self-dual model that might improve the resulting solution time in practice. Keywords: conic convex optimization, self-dual embedding, homogeneous self-dual, convex cone, self-scaled cone, level sets Category 1: Linear, Cone and Semidefinite Programming Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Citation: MIT Operations Research Center Working Paper OR 372-04 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 | |
![]() |