A parametric solution for local and global optimization

Abstract

The goal of this thesis is to present a method which when applied to certain nonconvex quadratic programming problems will locate the global minimum, all isolated local minima and some of the non-isolated local minima. The method proceeds by formulating a (multi) parametric QP or LP in terms of the data of the given non-convex quadratic programming problem. Based on the solution of the parametric QP or LP, a minimization problem is formulated. This problem is unconstrained and piece-wise quadratic. A key result is that the isolated local minimizers (including the global minimizer) of the original non-convex problem are in one to one correspondence with those of the derived unconstrained problem. As an application, the method is applied to the problem of determining if a given symmetric matrix is copositive on a given polyhedral cone. We show that the copositivity problem in which the matrix has exactly one negative value can be solved in polynomial time. The results established for non-convex quadratic programming problems are generalized to the non-convex problems in which the objective function in nonquadratic and the constraints are nonlinear.