Selective Gram-Schmidt orthonormalization for conic cutting surface algorithms
John E. Mitchell(mitchjrpi.edu)
Abstract: It is not straightforward to find a new feasible solution when several conic constraints are added to a conic optimization problem. Examples of conic constraints include semidefinite constraints and second order cone constraints. In this paper, a method to slightly modify the constraints is proposed. Because of this modification, a simple procedure to generate strictly feasible points in both the primal and dual spaces can be defined. A second benefit of the modification is an improvement in the complexity analysis of conic cutting surface algorithms. Complexity results for conic cutting surface algorithms proved to date have depended on a condition number of the added constraints. The proposed modification of the constraints leads to a stronger result, with the convergence of the resulting algorithm not dependent on the condition number.
Keywords: Semidefinite programming, conic programming, column generation, cutting plane methods.
Category 1: Linear, Cone and Semidefinite Programming (Other )
Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )
Citation: Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180, November 2006. http://www.rpi.edu/~mitchj/papers/coneGS.html
Entry Submitted: 11/29/2006
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|