روش جهت متناوب ضرایب برای زیر مساله ناحیه اطمینان توسیع یافته

Iranian Journal of Numerical Analysis and Optimization

Article 5, Volume 7, Issue 1 - Serial Number 11, January 0, Pages 107-117   

Document Type: Research Article

DOI: 10.22067/ijnao.v7i1.52283

Abstract

اخیراً زیرمساله ناحیه اطمینان توسیع یافته در تحقیقات متعددی مورد توجه قرار گرفته است. تحت مفروضات گوناگون، دوگانی قوی و آزاد سازی مخروطی درجه دو-نیمه معین برای کلاس های مختلف آن ارایه شده است. با توجه به اهمیت زیر مساله ناحیه اطمینان توسیع یافته، در این مقاله بدون در نظر گرفتن هیچ فرضی روی مساله، روش جهت متناوب ضرایب را که بسیار مورد استفاده قرار گرفته است، برای حل آن بکار می بریم. همگرایی روش به شرایط ایستایی مرتبه اول ثابت می شود. همچنین روی کلاس های مختلفی از مسایل آزمون، کیفیت جواب محاسبه شده توسط این روش در ابعاد متوسط با آزاد سازی مخروطی درجه دو-نیمه معین مقایسه می شود. علاوه بر این، کاربرد روش در حل مسایل در ابعاد بزرگ با حل چندین مثال مقیاس بزرگ نشان داده می شود.

Keywords

زیر مساله ناحیه اطمینان توسیع یافته; روش متناوب; بهینه سازی نامحدب; برنامه ریزی نیمه معین; برنامه ریزی مخروطی درجه دو

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.