Alternate Direction Method: A New Recipe for Non-convex Quadratic Programming with Applications

Summary

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.

Sample Publications

  • J. Peng and T. Zhu. A Nonlinear Semidefinite Optimization Relaxation for the Worst-case Linear Optimization under Uncertainties. Mathematical Programming, 152(1), 593-614, 2015.
  • J. Chen, L. Feng, J. Peng and Y. Ye. Analytic results and effective algorithm for optimal portfolio liquidation with market impact. Operations Research, 62(1), 195-206, 2014.
  • J.Q. Hale, E.L. Zhou and J. Peng. A Lagrangian Search Method for the K-Median Problem. J. Global Optimization, 69(1), 137-156, 2017.
  • Hezhi Luo,Xiaodi Bai, Gino Lim and Jiming Peng. Global Algorithms for Quadratic Programming with A Few Negative Eigenvalues Based on Successive Linear Optimization and Convex Relaxation. Forthcoming in Mathematical Programming: Computation. [doi]

    • Participants

    PI: Jiming Peng
    Graduate Student: Aein Khabazian

    Sponsor

    NSF CMMI: 2015-2018.