One of the most challenging issues in optimization is how to solve large scale non-convex and mixed integer optimization problems from various applications. Thanks to the effort of many excellent optimization experts, numerous effective algorithms such as interior-point methods and alternate direction methods (ADMs) have been developed for convex optimization. However, it has been observed that, while algorithms like ADMs may work well for subclasses of convex optimization problems, they converge only to a stationary point of the underlying problem when applied to non-convex optimization and can not provide a qualitative solution.
In this project, we introduce a new mechanism in the design of global algorithms for non-convex quadratic optimization. The new mechanism integrates several existing simple effective optimization techniques such as ADMs, simple convex relaxation, initialization and line search to develop global algorithms that can effectively locate a global optimal solution in non-convex optimization. We establish the convergence of the new algorithm and estimate its complexity.
PI: Jiming Peng
Graduate Student: Aein Khabazian
NSF CMMI: 2015-2018.