Selective Gram-Schmidt orthonormalization for conic cutting surface algorithms

John E. Mitchell(mitchjrpi.edu)
Vasile L. Basescu(basesvverizon.net)

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

Download: [PDF]

Entry Submitted: 11/29/2006
Entry Accepted: 11/29/2006
Entry Last Modified: 11/29/2006

Modify/Update this entry