论文标题
呈现不变的凸出优化的合同点方法
Affine-invariant contracting-point methods for Convex Optimization
论文作者
论文摘要
在本文中，我们开发了用于解决有界域的复合凸最小化问题的新仿射算法。我们提出了一个合同点方法的一般框架，该框架在每次迭代中求解一个辅助子问题，将目标函数的平滑部分限制在初始域的收缩中。该框架为我们提供了一种系统的方式来开发不同顺序的优化方法，并具有全球复杂性界限。我们表明，使用适当的仿射流平滑度条件，可以通过纯度$ p \ geq 1 $的纯张量方法的一步来实现收缩点方法的一种迭代。功能残差中产生的全局收敛速率为$ {\ cal o}（1 / k^p）$，其中$ k $是迭代计数器。重要的是，我们范围中的所有常数都是仿射不变的。对于$ P = 1 $，我们的计划恢复了著名的Frank-Wolfe算法，从张量方法的一般角度为其提供了新的解释。最后，在我们的框架内，我们提出了不精确的二阶方案$（p = 2）$的有效实施和总复杂性分析，称为牛顿合同。它可以看作是信任区域思想的正确实施。初步的数值结果证实了其在迭代次数和计算时间中的良好实践表现。
In this paper, we develop new affine-invariant algorithms for solving composite convex minimization problems with bounded domain. We present a general framework of Contracting-Point methods, which solve at each iteration an auxiliary subproblem restricting the smooth part of the objective function onto contraction of the initial domain. This framework provides us with a systematic way for developing optimization methods of different order, endowed with the global complexity bounds. We show that using an appropriate affine-invariant smoothness condition, it is possible to implement one iteration of the Contracting-Point method by one step of the pure tensor method of degree $p \geq 1$. The resulting global rate of convergence in functional residual is then ${\cal O}(1 / k^p)$, where $k$ is the iteration counter. It is important that all constants in our bounds are affine-invariant. For $p = 1$, our scheme recovers well-known Frank-Wolfe algorithm, providing it with a new interpretation by a general perspective of tensor methods. Finally, within our framework, we present efficient implementation and total complexity analysis of the inexact second-order scheme $(p = 2)$, called Contracting Newton method. It can be seen as a proper implementation of the trust-region idea. Preliminary numerical results confirm its good practical performance both in the number of iterations, and in computational time.
