【MIT博士论文】具有非标准结构的凸优化的新理论和算法,141页pdf

优化模型和算法在科学和工程的发展中长期扮演着核心和不可或缺的角色。近年来，一阶方法在处理机器学习和数据科学中出现的应用时起到了重要的作用，这归因于它们的简单性、合理的快速收敛速度和每次迭代的低计算成本。然而，还存在许多重要的应用违反了现有一阶方法基于的基本假设 —— 具体来说，尽管目标函数是凸的，但在可行域上既不是Lipschitz也没有Lipschitz梯度。这篇论文的目的是为这些“非标准”问题提出新的优化模型，开发新的一阶方法来解决这些模型，并分析这些方法的收敛速度。在第一章中，我们为组合凸优化问题min𝑥∈R𝑛 𝑓(A𝑥) + ℎ(𝑥)提出并分析了一个新的广义Frank-Wolfe方法，其中𝑓是一个𝜃-对数同态自调和障碍，A是一个线性算子，而函数ℎ在其域上有界，但可能是非光滑的。我们证明了我们的广义Frank-Wolfe方法需要𝑂((𝛿0 + 𝜃 + 𝑅ℎ) ln(𝛿0) + (𝜃 + 𝑅ℎ) 2/𝜀) 次迭代产生一个𝜀-近似解，其中𝛿0表示初始最优性差距，而𝑅ℎ是ℎ在其域上的变化。这一结果建立了𝜃-对数同态障碍和Frank-Wolfe方法之间的某种固有联系。当专门用于𝐷-最优设计问题时，我们实际上恢复了Khachiyan (1996)使用带有精确线搜索的Frank-Wolfe方法获得的复杂性。

在第二章中，我们为凸优化问题min𝑥∈𝒳 𝑓(A𝑥) + ⟨𝑐, 𝑥⟩提出并分析了一个新的远步Frank-Wolfe方法，其中𝑓是一个𝜃-对数同态自调和障碍，A是一个线性算子，⟨𝑐, ·⟩是一个线性函数，而𝒳是一个非空多面体。我们建立了我们的Frank-Wolfe方法在目标差和Frank-Wolfe差两方面的全局线性收敛率。特别地，这解决了Ahipasaoglu、Sun和Todd (2008)中关于专门用于D-最优设计问题的远步Frank-Wolfe方法的全球线性收敛问题。

在第三章中，我们为一类凸优化问题提出了一个广义乘法梯度(MG)方法，大致来说，它涉及在对称锥的“切片”上最小化一个1-对数同态函数。这类问题包括了几个重要的应用，包括正电子发射断层扫描、D-最优设计、量子态断层扫描和Nesterov关于布尔二次优化的松弛。我们通过欧几里德Jordan代数的工具展示，这个广义的MG方法以𝑂(ln(𝑛)/𝑘)的速率收敛，其中𝑛表示对称锥的秩。