TITLE :- Towards a practical simplex method for semidefinite programming SPEAKER :- Kartik Krishnan Advanced Optimization Laboratory, Dept. of Computing & Software, McMaster University, Hamilton, Ontario, Canada kartik@caam.rice.edu http://www.caam.rice.edu/~kartik ABSTRACT :- Conic programming is perhaps 'linear programming (LP)' for the 21st century, and has a variety of applications in science and engineering. Other than LP, the two important subclasses of conic programming include semidefinite programming (SDP) and second order cone programming (SOCP). Interior point methods (IPMs) are currently the 'techniques of choice' for solving SDP and SOCP problems. Although, IPMs can solve large SOCPs, they are fairly limited in size of SDPs they can handle. Moreover, another drawback with these methods is that no warm start techniques are currently available for reoptimization, especially after branching or the addition of cutting planes. In this poster, we present a non-polyhedral primal active set approach for SDP, which is a proper generalization of the primal simplex method for LP. To motivate the approach, we wish (1) To do each iteration of the method more quickly than that of an IPM. (2) Warm start during reoptimization using a dual simplex variant of the method. The algorithm generates a sequence of iterates, with non-increasing objective values, which are extreme points of the primal feasible region. Under a nondegeneracy assumption, we show that the objective values of the iterates are in fact strictly decreasing. We have implemented the method with special attention to doing each iteration of the algorithm quickly. Finally, we present some of our computational experiences with the algorithm. This is based on joint work with Gabor Pataki (UNC-Chapel Hill) and Yin Zhang (Rice University).