函数相对于集合的条件数
本文提出相对平滑性和相对强凸性的概念,并相应地将标准算法扩展到新的设置中,应用于发展新的一阶方法来解决 D - 优化设计问题并进行计算复杂度分析。
Oct, 2016
通过研究在信号处理和机器学习中的应用,本论文讨论了两类具有挑战的凸优化问题,提出了一种解决方案,并给出了条件梯度算法的版本以及相应的效率估计和应用。
Feb, 2013
本文研究了立方正则化牛顿法在解决具有一致凸性目标的复合最小化问题时的迭代复杂度。在引入某种程度的二阶条件数的概念后,我们证明了在非退化情况下具有自适应正则化参数估计的方法具有线性收敛率。我们的算法自动实现了具有 H"older 连续的目标平滑部分的不同问题类别中均匀凸目标函数的全局最佳复杂度界限。作为我们发展的副产品,我们证明了牛顿法在具有一致有界二阶导数的强凸函数类上的全局迭代复杂度始终优于梯度法。
May, 2019
研究表明,当在具有 Lipschitz 梯度的强凸函数上应用梯度下降算法时,其收敛速度由函数的条件数决定且算法收敛速度类似于一个带有离开步骤的 Frank-Wolfe 算法。在对无约束情况的良好扩展中,算法的收敛速度由函数的条件数及多面体的某个特定条件数的乘积决定。本研究为这种类型多面体调整提出了新的方法,并且认为之前的相关方法是等价的,并可通过多面体的参数进行统一,从而实现算法的线性收敛。此外,对于凸二次目标,研究表明收敛速度取决于相应缩放多面体的条件数。
Dec, 2015
该论文提出了相对连续性的概念,并使用用户指定的参考函数确定了相对连续性,展示了许多不可导凸函数相对于相应简单的参考函数是相对连续的,并分别分析了在确定这两个设置中解决优化问题的两种标准算法 -- 镜子下降算法和随机镜像下降算法,并首次为目标函数不一致的情况开发了计算保证。
Oct, 2017
本文介绍了一个使用计算代数和黎曼几何工具来分析多视角几何中最小问题的数值条件的通用框架。我们从标准的 5 点或 7 点随机采样一致性(RANSAC)算法在相对姿态估计时的失败情况出发,即使在没有离群值和足够数据支持假说的情况下。我们认为这些情况是由于 5 点和 7 点最小问题的固有不稳定性引起的。我们将我们的框架应用于表征造成条件数无穷大的世界场景,以及直接在图像数据中表征病态。该方法产生了在求解最小问题之前评估条件数的计算测试。最后,合成和真实数据的实验证明,RANSAC 不仅可以去除离群值,还可选择具有良好条件的图像数据,如我们的理论所预测。
Oct, 2023
提出一种用于优化框架、鞍点问题和变分不等式的一般算法框架,通过构建主要问题组成部分即优化目标函数或者变分不等式运算符的不精确模型,不但可以产生许多已知的算法方法,同时可以构造新的算法方法,如具有复合结构的变分不等式的通用条件梯度法和相对光滑度算子的变分不等式算法。
Jan, 2020
该研究证明了在平滑 d 元函数,数值积分的最坏情况下发生维数灾难,证明了无限可微函数的后继导数越大,则维数灾难越明显,利用体积估计方法证明了 n 个点所构成凸包的邻域衰减速度指数级相关于维数和点的数量关系,对无限可微函数的拟多项式、弱可处理性和统一弱可处理性进行了研究。
Apr, 2013