期刊
JOURNAL OF SCIENTIFIC COMPUTING
卷 69, 期 1, 页码 52-81出版社
SPRINGER/PLENUM PUBLISHERS
DOI: 10.1007/s10915-016-0182-0
关键词
Alternating direction method of multipliers (ADMM); Convergence rate; Regularization; Kurdyka-Lojasiewicz property; Convex optimization
资金
- Hong Kong Research Grants Council General Research Fund Early Career Scheme [CUHK 439513]
- National Science Foundation [CMMI-1462408]
- Div Of Civil, Mechanical, & Manufact Inn
- Directorate For Engineering [1462408] Funding Source: National Science Foundation
The alternating direction method of multipliers (ADMM) is widely used in solving structured convex optimization problems due to its superior practical performance. On the theoretical side however, a counterexample was shown in Chen et al. (Math Program 155(1):57-79, 2016.) indicating that the multi-block ADMM for minimizing the sum of N convex functions with N block variables linked by linear constraints may diverge. It is therefore of great interest to investigate further sufficient conditions on the input side which can guarantee convergence for the multi-block ADMM. The existing results typically require the strong convexity on parts of the objective. In this paper, we provide two different ways related to multi-block ADMM that can find an -optimal solution and do not require strong convexity of the objective function. Specifically, we prove the following two results: (1) the multi-block ADMM returns an -optimal solution within iterations by solving an associated perturbation to the original problem; this case can be seen as using multi-block ADMM to solve a modified problem; (2) the multi-block ADMM returns an -optimal solution within iterations when it is applied to solve a certain sharing problem, under the condition that the augmented Lagrangian function satisfies the Kurdyka-Aojasiewicz property, which essentially covers most convex optimization models except for some pathological cases; this case can be seen as applying multi-block ADMM to solving a special class of problems.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据