凸半定规划的混合算法
我们研究了涉及具有凸目标函数(平滑或非平滑)和额外的线性或非线性平滑凸约束的几类非常重要的半定优化问题,这些问题在统计学、机器学习、组合优化和其他领域中非常普遍。我们关注高维和合理设置的情况,在这种情况下,问题具有满足低秩互补条件的低秩解。我们提供了几个理论结果,证明在这些情况下,众所周知的 Extragradient 方法,在在接近最优原始 - 对偶解的位置初始化时,使用低秩奇异值分解(SVD)将收敛到约束优化问题的解,并具有标准收敛速度保证,而不需要在最坏情况下需要计算成本高昂的全秩 SVD。我们的方法得到了使用 Max-Cut 实例数据集进行的数值实验的支持。
Feb, 2024
我们提出了一种随机梯度框架,用于解决具有(可能)无限数量的线性包含约束条件的随机复合凸优化问题,而这些约束条件需要几乎确定。我们使用平滑和同伦技术处理约束条件,无需矩阵投影,并且通过数值实验表明,我们的算法实现了最先进的实用性能。
Jan, 2019
本文提出了一种基于最小最大优化问题的 SVD-QCQP 原始 - 对偶算法来优化半可分离核函数,极大地降低了计算复杂度,并且在分类和回归中提供了有效的实现。当应用于基准数据时,该算法表现出了显著的精度改进潜力,而计算时间与神经网络和随机森林等典型方法相似甚至更好。
Apr, 2023
研究了一种用于半定规划问题(SDOs)的切平面方法,证明了该方法基于有界性假设的收敛性。通过将该方法的收敛速度与初始外近似的直径联系起来,我们证明了当使用二阶锥逼近而不是线性逼近时该方法的表现更好。我们将该方法用于提供数千个协变量的稀疏 PCA 问题的边界间隙,并解决了 500x500 矩阵上的核范数问题。
Oct, 2019
本文探讨了解决基本的机器学习问题 —— 矩阵补全的方法,并证明了普遍使用的非凸优化问题在正半定矩阵补全中没有局部极小值,可用于任意初始化的优化算法,并可在多项式时间内证明其正确性。
May, 2016
本文提出了一种新的两阶段方法来解决在高密度无线合作网络中解决大规模凸最优化问题,其中原始的凸问题通过矩阵填充转化为标准锥编程形式,并采用交替方向乘子法(ADMM)求解。与二阶方法相比,ADMM 能够在合理的时间内并行地解决大规模问题。
Jun, 2015
提出了一种基于对称半正定矩阵变量 X 进行定义的非线性凸程序的求解算法,该算法基于因数分解 X=YY^T,其中 Y 的列数确定 X 的秩。该因式分解唤起了将原问题重新表述为特定商流形上的优化的几何,并得出了二阶优化方法。此外,文章提供了一些关于分解秩的条件以确保与原始问题的等价性。该算法的效率在图的最大切割和稀疏主成分分析问题上得到了说明。
Jul, 2008
本文介绍了解决半定规划在机器学习、控制和机器人领域中可扩展性问题的最近方法,包括利用问题结构(如稀疏性和对称性)、生成低秩近似解决方案、更可扩展算法、以及将可扩展性与保守性相妥协的方法,并提供相应文献入口和实例,最后列出了实现本文所讨论的方法的软件包清单。
Aug, 2019
提出了一种新的算法来解决优化问题,该算法针对平滑函数和受限 X 的正半定和对角块小标识矩阵的约束。该算法利用该问题的低秩解和黎曼流形上的光滑优化问题的秩约束版本的事实,并比较该算法与成熟软件的优势。
Jun, 2015
本文研究了正半定规划的近似算法,提出了一种简单的 NC 并行算法,其迭代次数为 O (1/ϵ³ log³ n),总工作量近似为因子分解中非零条目数的线性级别。
Jan, 2012