Xinwei Liu, Professor, Hebei University of Technology

Yuhong Dai, Professor

A primal-dual majorization-minimization method for large-scale linear programs

20:30-22:00 June 28(Tuesday), Tencent Meeting ID: 582-249-834

We present a primal-dual majorization-minimization method for large-scale linear programs. The method is originated from a newly developed augmented Lagrangian method for nonlinear inequality constrained optimization. The majorization-minimization approach is introduced to solve the augmented Lagrangian subproblems. Distinguished from the existing simplex methods and interior-point methods for linear programs, our proposed method only depends on a factorization of the constant matrix independent of iterations and does not need any computation on step sizes, thus can be expected to be particularly appropriate for large-scale linear programs. Under mild conditions, the global convergence is analyzed. Moreover, we prove that our method can be of globally linear convergence, and the iteration complexity of our method is independent of the sizes of the linear programs.