论文标题
通过线路搜索一类约束范围差异优化问题的顺序凸编程方法的收敛率分析
Convergence rate analysis of a sequential convex programming method with line search for a class of constrained difference-of-convex optimization problems
论文作者
论文摘要
在本文中，我们研究了[46]中使用单调线路搜索（SCP $ _ {ls} $）的顺序凸编程方法，用于具有多个平滑不平等约束的一类差异（DC）优化问题。 SCP $ _ {ls} $是移动式 - 标记型算法的代表性变体[6,10,13,54]，用于约束优化问题。我们通过施加合适的kurdyka-lojasiewicz（kl）假设来分析scp $ _ {ls} $生成的序列的收敛率。具体而言，在非convex设置中，我们假设与目标和约束相关的特殊潜在函数是KL函数，而在凸设置中，我们将KL假设直接强加于扩展的目标函数（即，限制集集的目标和指示函数）。这两个不同的KL假设之间的关系是在凸面设置中建立的，该假设在其他可区分性假设下。我们还讨论了如何在约束函数的其他假设下从凸面设置中的拉格朗日中推断出扩展目标函数的KL指数。借助此结果，发现某些受约束优化模型的扩展目标，例如最小化$ \ ell_1 $受到逻辑/泊松损失的约束，这是在温和假设下具有指数$ \ frac12 $的KL函数。为了说明如何应用结果，我们考虑SCP $ _ {ls} $，用于最小化$ \ ell_ {1-2} $ [60]，但要遵守由$ \ ell_2 $ norm/lorentzian Norm [21]所测量的残余错误。我们首先讨论如何验证分析中所需的各种条件，然后执行数值实验以说明SCP $ _ {LS} $的收敛行为。
In this paper, we study the sequential convex programming method with monotone line search (SCP$_{ls}$) in [46] for a class of difference-of-convex (DC) optimization problems with multiple smooth inequality constraints. The SCP$_{ls}$ is a representative variant of moving-ball-approximation-type algorithms [6,10,13,54] for constrained optimization problems. We analyze the convergence rate of the sequence generated by SCP$_{ls}$ in both nonconvex and convex settings by imposing suitable Kurdyka-Lojasiewicz (KL) assumptions. Specifically, in the nonconvex settings, we assume that a special potential function related to the objective and the constraints is a KL function, while in the convex settings we impose KL assumptions directly on the extended objective function (i.e., sum of the objective and the indicator function of the constraint set). A relationship between these two different KL assumptions is established in the convex settings under additional differentiability assumptions. We also discuss how to deduce the KL exponent of the extended objective function from its Lagrangian in the convex settings, under additional assumptions on the constraint functions. Thanks to this result, the extended objectives of some constrained optimization models such as minimizing $\ell_1$ subject to logistic/Poisson loss are found to be KL functions with exponent $\frac12$ under mild assumptions. To illustrate how our results can be applied, we consider SCP$_{ls}$ for minimizing $\ell_{1-2}$ [60] subject to residual error measured by $\ell_2$ norm/Lorentzian norm [21]. We first discuss how the various conditions required in our analysis can be verified, and then perform numerical experiments to illustrate the convergence behaviors of SCP$_{ls}$.
