|
|
带有绝对值形式的非线性约束下的交替方向乘子法
|
Abstract:
交替方向乘子法(Alternating Direction Method of Multipliers, ADMM)广泛应用于线性约束优化问题，无论是凸目标函数还是非凸目标函数，其约束一般是线性约束。文章研究了具有绝对值形式的非线性约束的非凸极小化问题的ADMM。在假设相关函数满足Kurdyka-Lojasiewicz (KL)不等式的情况下，证明了由ADMM生成的迭代子序列收敛于问题的一个临界点，并根据一些数值例子说明了ADMM是可行的。
The Alternating Direction Method of Multipliers (ADMM) is widely used for linear constraint optimization problems, whether the objective function is convex or non-convex, with constraints generally being linear. This article studies the ADMM applied to non-convex minimization problems with nonlinear constraints in the form of absolute values. Under the assumption that the relevant functions satisfy the Kurdyka-Lojasiewicz (KL) inequality, it is proved that the iterative subsequence generated by ADMM converges to a critical point of the problem. Additionally, some numerical examples are provided to illustrate the feasibility of ADMM.
| [1] | Gabay, D. and Mercier, B. (1976) A Dual Algorithm for the Solution of Nonlinear Variational Problems via Finite Element Approximation. Computers & Mathematics with Applications, 2, 17-40. https://doi.org/10.1016/0898-1221(76)90003-1 |
| [2] | Yuan, M. and Lin, Y. (2005) Model Selection and Estimation in Regression with Grouped Variables. Journal of the Royal Statistical Society Series B: Statistical Methodology, 68, 49-67. https://doi.org/10.1111/j.1467-9868.2005.00532.x |
| [3] | Han, D. (2022) A Survey on Some Recent Developments of Alternating Direction Method of Multipliers. Journal of the Operations Research Society of China, 10, 1-52. https://doi.org/10.1007/s40305-021-00368-3 |
| [4] | Eckstein, J. and Bertsekas, D.P. (1992) On the Douglas-Rachford Splitting Method and the Proximal Point Algorithm for Maximal Monotone Operators. Mathematical Programming, 55, 293-318. https://doi.org/10.1007/bf01581204 |
| [5] | Boley, D. (2013) Local Linear Convergence of the Alternating Direction Method of Multipliers on Quadratic or Linear Programs. SIAM Journal on Optimization, 23, 2183-2207. https://doi.org/10.1137/120878951 |
| [6] | He, B. and Yuan, X. (2012) On the O(1/n) Convergence Rate of the Douglas-Rachford Alternating Direction Method. SIAM Journal on Numerical Analysis, 50, 700-709. https://doi.org/10.1137/110836936 |
| [7] | Davis, D. and Yin, W. (2016) Convergence Rate Analysis of Several Splitting Schemes. In: Glowinski, R., Osher, S. and Yin, W., Eds., Splitting Methods in Communication, Imaging, Science, and Engineering, Springer, 115-163. https://doi.org/10.1007/978-3-319-41589-5_4 |
| [8] | He, B. and Yuan, X. (2014) On Non-Ergodic Convergence Rate of Douglas-Rachford Alternating Direction Method of Multipliers. Numerische Mathematik, 130, 567-577. https://doi.org/10.1007/s00211-014-0673-6 |
| [9] | He, B., Liao, L., Han, D. and Yang, H. (2002) A New Inexact Alternating Directions Method for Monotone Variational Inequalities. Mathematical Programming, 92, 103-118. https://doi.org/10.1007/s101070100280 |
| [10] | Goldstein, T., O'Donoghue, B., Setzer, S. and Baraniuk, R. (2014) Fast Alternating Direction Optimization Methods. SIAM Journal on Imaging Sciences, 7, 1588-1623. https://doi.org/10.1137/120896219 |
| [11] | Giesen, J. and Laue, S. (2016) Distributed Convex Optimization with Many Convex Constraints. arXiv: 1610.02967 |
| [12] | Wang, F., Cao, W. and Xu, Z. (2018) Convergence of Multi-Block Bregman ADMM for Nonconvex Composite Problems. Science China Information Sciences, 61, Article No. 122101. https://doi.org/10.1007/s11432-017-9367-6 |
| [13] | Zhang, J. and Luo, Z. (2020) A Proximal Alternating Direction Method of Multiplier for Linearly Constrained Nonconvex Minimization. SIAM Journal on Optimization, 30, 2272-2302. https://doi.org/10.1137/19m1242276 |
| [14] | Guo, K., Han, D.R. and Wu, T.T. (2016) Convergence of Alternating Direction Method for Minimizing Sum of Two Nonconvex Functions with Linear Constraints. International Journal of Computer Mathematics, 94, 1653-1669. https://doi.org/10.1080/00207160.2016.1227432 |
| [15] | Mordukhovich, B.S. (2006) Variational Analysis and Generalized Differentiation Vol. I: Basic Theory, Vol. II: Applications. Springer. |
| [16] | Yang, W.H. and Han, D. (2016) Linear Convergence of the Alternating Direction Method of Multipliers for a Class of Convex Optimization Problems. SIAM Journal on Numerical Analysis, 54, 625-640. https://doi.org/10.1137/140974237 |
| [17] | Attouch, H., Bolte, J., Redont, P. and Soubeyran, A. (2010) Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality. Mathematics of Operations Research, 35, 438-457. https://doi.org/10.1287/moor.1100.0449 |
| [18] | Bolte, J., Sabach, S. and Teboulle, M. (2013) Proximal Alternating Linearized Minimization for Nonconvex and Nonsmooth Problems. Mathematical Programming, 146, 459-494. https://doi.org/10.1007/s10107-013-0701-9 |
| [19] | Nesterov, Y. (2013) Introductory Lectures on Convex Optimization: A Basic Course. Springer Science & Business Media. |
| [20] | Liu, H., Hu, J., Li, Y. and Wen, Z. (2020) Computational Methods for Optimization. Higher Education Press. (In Chinese) |
