|
The issue of how to solve generic non-convex QP has been a long standing challenge in optimization. Existing global algorithms usually refer to branch-and-bound or successive relaxation approaches whose running time are typically exponential in term of the number of variables. Moreover, it has been proved that even finding a local optimal solution to LCQP is NP-hard.
In this talk, we introduce a new design paradigm for LCQPs with a few negative eigenvalues that are known to be NP-hard. We first introduce a new class of Lagrangian functions that satisfy the KKT conditions automatically. By using the new Lagrangian function, we present an alternative update scheme to improve the objective function. We then characterize the accumulation point of the sequence. By integrating the new algorithm and other simple optimization techniques such as convex relaxation, line search and partitioning, we present a global algorithm to find the global optimal solution to the underlying LCQP and estimate its complexity. Promising numerical experiments will be reported as well. | 
