We consider optimization problems expressed as a linear program with a cone constraint. Cone-LP's subsume ordinary linear programs, and semidefinite programs. We study the notions of basic solutions, nondegeneracy, and feasible directions, and propose a generalization of the simplex method for a large class including LP's and SDP's. One key feature of our approach is considering feasible directions as a sum of two directions. In LP, these correspond to variables leaving and entering the basis, respectively. The resulting algorithm for SDP inherits several important properties of the LP-simplex method, in particular, the linesearch can be done in the current face of the cone, similarly to LP, where the linesearch must determine only the variable leaving the basis.
Weitere Kapitel dieses Buchs durch Wischen aufrufen
- Cone-LP's and semidefinite programs: Geometry and a simplex-type method
- Springer Berlin Heidelberg