1996 | ReviewPaper | Buchkapitel
Cone-LP's and semidefinite programs: Geometry and a simplex-type method
verfasst von : Gábor Pataki
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.