UC San Diego

The goal of this thesis is to study a special nonlinear programming, namely, polynomial optimization in which both the objective and constraints are polynomials. This kind of problem is always NP-hard even if the objective is nonconvex quadratic and all constraints are linear. The semidefinite (SDP) relaxations approach, based on sum of squares representations, provides us with strong tools to solve polynomial optimization problems with finitely many constraints globally. We first review two SDP relaxation methods for solving polynomial optimization problems with finitely many constraints: the classic Lasserre's SDP relaxation and Jacobian SDP relaxation. In general, these methods relax the polynomial optimization problem as a sequence of SDPs whose optima are the lower bounds of the global minimum and converge to the global minimum under certain assumptions. We also prove that the assumption of nonsingularity in Jacobian SDP relaxation method can be weakened to have finite singularities. Then, we study the problem of minimizing a rational function. We reformulate the problem by the technique of homogenization, the original problem and the reformulated problem are shown to be equivalent under some generic conditions. The constraint set of the reformulated problem may not be compact, and Lasserre's SDP relaxation may not have finite convergence, so we apply Jacobian SDP relaxation to solve the reformulated polynomial optimization problem. Some numerical examples are presented to show the efficiency of this method. Next, we consider the problem of minimizing semi-infinite polynomial programming (SIPP). We propose an exchange algorithm with SDP relaxations to solve SIPP problems with a compact index set globally. And we extend the proposed method to SIPP problems with noncompact index set via homogenization. The reformulated problem is equivalent to original SIPP problem under some generic conditions. At last, we study the problem of finding best rank-1 approximations for both symmetric and nonsymmetric tensor. For symmetric tensors, this is equivalent to optimizing homogeneous polynomials over unit spheres; for nonsymmetric tensors, this is equivalent to optimizing multi-quadratic forms over multi-spheres. We use semidefinite relaxations approach to solve these polynomial optimization problems. Extensive numerical experiments are presented to show that this approach is practical in getting best rank-1 approximations