Selective Gram-Schmidt orthonormalization for conic cutting surface
algorithms
Download the paper,
in pdf.
Authors:
John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
mitchj at rpi.edu
Vasile L. Basescu
basesv at verizon.net
November 29, 2006. Revised July 16, 2007.
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.
Download the paper,
in pdf.
Optimization Online listing
Return to my list of papers.