Random algorithms for convex minimization problems
Random algorithms for convex minimization problems
复制标题
DOI：
10.1007/s10107-011-0468-9
复制
发表时间：
2011-10
影响因子：
2.7
通讯作者：
A. Nedić
中科院分区：
文献类型：
--
作者：
A. Nedić
本文研究具有随机可行性步骤的迭代梯度法和次梯度法求解约束凸极小化问题，其中约束集被指定为可能无穷多个约束集的交集。每个约束集被假定为一个凸但不一定可微函数的水平集。提出的算法适用于问题的整个约束集事先不知道，但通过观察可以及时了解的情况。此外，这些算法对于约束条件已知但约束条件数量很大或有限的约束优化问题也很有意义。针对目标函数在Lipschitz梯度下可微和目标函数不一定可微的情况，分析了本文提出的算法。研究了该算法在步长递减和非递减情况下的性能。对于步长递减，建立了趋近于最优解的确定性。对于步长不递减的情况，为约束集的迭代加权平均值的期望距离以及函数值沿加权平均值的期望次优性建立了误差界限。
This paper deals with iterative gradient and subgradient methods with random feasibility steps for solving constrained convex minimization problems, where the constraint set is specified as the intersection of possibly infinitely many constraint sets. Each constraint set is assumed to be given as a level set of a convex but not necessarily differentiable function. The proposed algorithms are applicable to the situation where the whole constraint set of the problem is not known in advance, but it is rather learned in time through observations. Also, the algorithms are of interest for constrained optimization problems where the constraints are known but the number of constraints is either large or not finite. We analyze the proposed algorithm for the case when the objective function is differentiable with Lipschitz gradients and the case when the objective function is not necessarily differentiable. The behavior of the algorithm is investigated both for diminishing and non-diminishing stepsize values. The almost sure convergence to an optimal solution is established for diminishing stepsize. For non-diminishing stepsize, the error bounds are established for the expected distances of the weighted averages of the iterates from the constraint set, as well as for the expected sub-optimality of the function values along the weighted averages.