Alternating direction method of multipliers for the extended trust region subproblem

Document Type : Research Article

Authors

• M. Salahi
• A. Taati

Department of Applied Mathematics, Faculty of Mathematical Sciences, University of Guilan, Rasht, Iran.

10.22067/ijnao.v7i1.52283

Abstract

The extended trust region subproblem has been the focus of several research recently. Under various assumptions, strong duality and certain SOCP/SDP relaxations have been proposed for several classes of it. Due to its importance, in this paper, without any assumption on the problem, we apply the widely used alternating direction method of multipliers (ADMM) to solve it. The convergence of ADMM iterations to the first order stationary conditions is established. On several classes of test problems, the quality of the solution obtained by the ADMM for medium scale problems is compared with the SOCP/SDP relaxation. Moreover, the applicability of the method for solving large scale problems is shown by solving several large instances.

Keywords

• Extended trust region subporblem
• Alternating method
• Nonconvex optimization
• Semidefinite program
• Second order cone program

20.1001.1.24236977.2017.7.1.7.6

---

References

1. Adachi, S., Iwata, S., Nakatsukasa, Y. and Takeda, A. Solving the trustregion subproblem by a generalized eigenvalue problem, Mathematical Engineering Technical Report(METR 2015-14), Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo.

2. Bai, X. and Scheinberg, K. Alternating direction methods for non convex optimization with applications to second-order least-squares and risk parity portfolio selection, Optimization-Online, 2015.

3. Bai, X., Sun, J., Sun, S. and Zheng, X. An alternating direction method for chance-constrained optimization problems with discrete distributions, Optimization-Online, 2012.

4. Beck, A. and Eldar, Y.C. Strong duality in nonconvex quadratic optimization with two quadratic constraints, SIAM Journal on Optimization, 17(3), 844-860, 2006.

5. Boyd, S., Parikh, N., Chu, E., Peleato, B. and Eckstein, J. Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3(1), 1-122, 2011.

6. Burer,S. and Anstreicher, K.M. Second-order-cone constraints for extended trust-region subproblems, SIAM Journal on Optimization, 23(1), 432-451, 2013.

7. Burer,S. and Yang, B. The trust region subproblem with non-intersecting linear constraints, Mathematical Programming, 149, 253-264, 2015.

8. Conn, A.R., Gould, N.I. and Toint, P.L. Trust Region Methods, SIAM, Philadelphia, PA, 2000.

9. Grant, M. and Boyd, S. CVX: Matlab software for disciplined convex programming, version 2.0 beta. http://cvxr.com/cvx, September 2013.

10. Fortin, C. and Wolkowicz, H. The trust region subproblem and semidefinite programming, Optimization Methods and Software, 19(1), 41-67, 2004.

11. Hsia, Y. and Sheu, R.L. Trust region subproblem with a fixed number of additional linear inequality constraints has polynomial complexity, arXiv preprint arXiv, 1312.1398, 2013.

12. Hong, M. , Luo, Z.Q. and Razaviyan, M. Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems, SIAM Journal on Optimization, 26(1), 337-364, 2016.

13. Jeyakumar, V. and Li, G.Y. Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization, Mathematical Programming, 147, 171-206, 2014.

14. Luo, H., Sun, X. and Wu, H. Convergence properties of augmented Lagrangian methods for constrained global optimization, Optimization Methods and Software, 23(5), 763-778, 2008.

15. Martinez, J.M. Local minimizers of quadratic functions on Euclidean balls and spheres, SIAM Journal on Optimization, 4(1), 159-176, 1994.

16. Rendl, F. and Wolkowicz, H. A semidefinite framework for trust region subproblems with applications to large scale minimization, Mathematical Programming, 77(1), 273-299, 1997.

17. Salahi, M. and Fallahi, S. Trust region subproblem with an additional linear inequality constraint, Optimization Letters, 10(4), 821-832, 2016.

18. Salahi, M. and Taati, A. A fast eigenvalue approach for solving the trust region subproblem with an additional linear inequality, Compuational and Applied Mathematics, DOI: 10.1007/s40314-016-0347-3, 2016.

19. Shen, Y., Wen, Z. and Zhang, Y. Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization, Op timization Methods and Software, 29(2), 239-263, 2014.

20. Sturm, J.F. and Zhang, S. On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28(2), 246-267, 2003.

21. Xu, Y., Yin, W., Wen, Z. and Zhang, Y. An alternating direction algo rithm for matrix completion with nonnegative factors, Journal of Frontiers of Mathematics in China, Special Issues on Computational Mathematics, 365-384, 2011.

22. Xu, L., Yu, B. and Zhang, Y. An alternating direction and projection algorithm for structure-enforced matrix factorization, Technical Reports, Department of Computational and Applied Mathematics, Rice University, 2013.