Theory and algorithms in semidefinite programming.

During this decade, semidefinite programming has emerged as an important area of optimization due to both the success of interior point methods at solving this problem and the growing number of its application areas such as combinatorial optimization, statistics and optimal control. Most of the interior point methods that solve linear programs in polynomial time were readily extended to solve semidefinite programs. At the same time, semidefinite programming relaxations of many hard-to-solve combinatorial optimization problems were found to yield fairly good solutions. A quadratic program with Boolean variables is generally a difficult problem. We establish a theoretical bound for the semidefinite programming relaxation of such problem with additional simple linear constraints. For the special case of the max-cut problem, a nonrandomized rounding procedure for obtaining a feasible solution from an optimal solution of the semidefinite programming relaxation is presented. This nonrandomized procedure is computationally shown to be superior to the famous randomized rounding method of Goemans and Williamson, which produces randomized solutions that only on the average result in an objective value of at least 0.87856 times the optimal value. Also, an alternate semidefinite programming relaxation approach to the general Boolean quadratic program is taken by relaxing an equivalent problem, which itself is derived through semidefinite programming. This alternate relaxing scheme is shown to produce a strictly tighter feasible region, which can only be matched by the conventional method by adding certain cuts. In this dissertation, two interior point methods, originally developed for linear programming, are extended to semidefinite programming. Straightforward extension of the affine scaling method to semidefinite programming problems has been shown to fail. We present a slightly modified approach. Numerical experiments show that our algorithm works well on various types of problems, including the ones that the straightforward approach has failed on. The projective transformation method of Karmarkar is extended to semidefinite programming in a straightforward manner. Proof of polynomial convergence of the algorithm and strategy for obtaining the starting canonical form are given. We introduce and prove the convergence of a gradient-based primal-dual iterative algorithm that solves semidefinite programming problems by finding a saddle point of the Lagrangian. Speed of convergence is heavily dependent on the choice of the step sizes involved in the iterations as well as appropriate scaling of the problem. Since the method involves no matrix inversion, it is well suited for large problems. An extension to problems in Hilbert space is also presented.Ph.D.Applied SciencesOperations researchUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/130288/2/3000936.pd