基本半代数凸集上循环投影算法收敛速度分析

MMApr, 2013

基本半代数凸集上循环投影算法收敛速度分析

Analysis of the convergence rate for the cyclic projection algorithm applied to basic semi-algebraic convex sets

Jonathan M. Borwein, Guoyin Li, Liangjin Yao

TL;DR研究基本的半代数凸集生成的多项式的最高次数和底层空间的维度对循环投影算法应用于有限个基本半代数凸集的收敛速度的影响，通过利用基本半代数凸体的代数结构，建立了一个明确的收敛速率估计。

Abstract

In this paper, we study the rate of convergence of the cyclic projection algorithm applied to finitely many basic semi-algebraic convex sets. We establish an explicit convergence rate estimate which relies on the

rate of convergence cyclic projection algorithm semi-algebraic convex sets polynomials algebraic structure

发现论文，激发创造

非凸集合的交替投影方法的收敛分析

通过研究属性和几何性质，本文提出了新的收敛分析框架，证明使用交替投影法将收敛于临界点，并提供了收敛速度上限，并证明在一些具体应用中的收敛结果，如设计结构紧框架。

Feb, 2018

凸可行性问题的随机投影方法：条件数和收敛速率

本研究分析了凸可行性问题的随机重构，提出了一种通用的随机投影算法框架，并基于调节参数得到了渐近收敛结果和显式下降速率。

Jan, 2018

交替和平均非凸投影的局部收敛性

本文探讨了在可分析变差意义下，有限个闭集的强正则交集在构造效率算法时的应用和其中的正则性和收敛性质。

Sep, 2007

线性约束的随机方法：收敛速度和条件数

研究随机算法和线性代数条件数，以提高坐标下降和迭代投影算法，在一些概率分布下，提高收敛速度。此外，进一步讨论以度量正则性假设下凸系统的推广及其与 ill-posedness 的距离的关系。

Jun, 2008

结构多面体的线性内存和分解不变线性收敛条件梯度算法

提出了一种改进的条件梯度方法来解决约束凸优化问题，针对多面体进行了相应的分析及优化，降低了每次迭代时的计算及内存开销，并在实际中通过对图路径、二分图完全匹配、结构预测任务中的边际分布等多样化问题进行测试并呈现出其卓越表现。

May, 2016

半定最优化问题的多面体和二阶圆锥分解

研究了一种用于半定规划问题（SDOs）的切平面方法，证明了该方法基于有界性假设的收敛性。通过将该方法的收敛速度与初始外近似的直径联系起来，我们证明了当使用二阶锥逼近而不是线性逼近时该方法的表现更好。我们将该方法用于提供数千个协变量的稀疏 PCA 问题的边界间隙，并解决了 500x500 矩阵上的核范数问题。

Oct, 2019

非凸集的横截性和交替投影

本文研究了交替投影法用于求解两个闭集交集中点的方法，证明了在标准横截性条件（及其弱化形式）下的局部线性收敛性，当两个集合是半代数的和有界的时，即使不满足横截性条件，也证明了子序列的收敛性。

Jan, 2014

凸复合二次和半定规划的交替方向乘子法的线性收敛率

本文提供了一种更加通用的半迭代交替方向乘子法，以解决线性约束下的凸组合优化问题，并证明该方法具有线性收敛性。同时，文章还说明了该方法在解决多个块的凸优化问题时非常有效，其中凸组合二次规划和二次半定规划是重要的应用之一。

Aug, 2015

循环坐标下降法的有限时间收敛性

本文研究了循环坐标下降（cyclic coordinate descent）这个经典的优化方法在机器学习中的应用，证明了在满足单调性假设条件下，该方法在有限时间内具有 $O (1/k)$ 收敛速度，对于设定的二次优化问题产生了理论分析。

May, 2010

利用矩锥和非负多项式进行线性优化

本文研究了实多项式环和截断矩序列在半代数集以及线性优化中的应用，提出了一种半定式算法来解决多项式锥的线性优化问题，并证明了其渐进和有限收敛性。

May, 2013