双层规划的近似方法
本研究关注简单的双层优化问题,提出一种新的双层优化方法,利用切割平面方法局部近似解决方案集合,应用加速梯度更新来减小上层目标函数,以实现子优性和不可行性错误的非渐近收敛保证。
Feb, 2024
该论文从两个方面揭示双层优化的收敛率:提出首个双层加速优化器 AccBiO 并给出无梯度边界假设的复杂度上限,同时得出更紧的下限。此外,论文还证明在某些情况下,双层优化比极大极小问题更具有挑战性。关键词包括双层优化、收敛率、下限复杂度、AccBiO 和二次型条件数。
Feb, 2021
我们研究了一类随机二级优化问题,引入了一种新颖的随机二级优化方法,通过随机切割平面局部逼近下层问题的解集,并运行带有方差减少技术的条件梯度更新来控制由于使用随机梯度引起的误差。在上层函数为凸函数的情况下,我们的方法需要最多 $\tilde {\mathcal {O}}(\max\{1/\epsilon_f^{2},1/\epsilon_g^{2}\})$ 个随机 oracle 查询,得到一个上层函数精度为 $\epsilon_f$、下层函数精度为 $\epsilon_g$ 的解,这一保证改进了之前已知的复杂性 $\mathcal {O}(\max\{1/\epsilon_f^{4},1/\epsilon_g^{4}\})$。此外,在上层函数为非凸函数的情况下,我们的方法需要最多 $\tilde {\mathcal {O}}(\max\{1/\epsilon_f^{3},1/\epsilon_g^{3}\})$ 个随机 oracle 查询,找到一个 $(\epsilon_f, \epsilon_g)$- 稳定点。在有限和问题设置中,对于凸和非凸情况下,我们的方法所需的随机 oracle 调用次数分别为 $\tilde {\mathcal {O}}(\sqrt {n}/\epsilon)$ 和 $\tilde {\mathcal {O}}(\sqrt {n}/\epsilon^{2})$,其中 $\epsilon=\min \{\epsilon_f,\epsilon_g\}$。
Aug, 2023
本文提出了一种基于对偶理论的方法来解决具有凸低层问题的双层规划问题,并且引入了一种优化方法以保证约束条件成立。作者通过提出的构建新对偶函数方法获得技术性结果,并最终通过求解两个实例来演示该算法的有效性。
Aug, 2016
本文研究凸双层优化问题,其中内层最小化平滑函数和非凸函数的和,外层旨在在内层问题的最优解集合上最小化平滑且强凸的函数。我们分析了一个基于现有不动点算法的一阶方法,通过内部目标函数值建立了方法的全局次线性收敛率。
Feb, 2017
本文针对双层 (随机) 优化问题,探讨了梯度下降方法的算法稳定性与泛化误差之间的基本联系,并在一般性情形下给出了稳定性界限的分析,通过实验证明了迭代次数对泛化误差的影响。
Oct, 2022
本文研究使用零阶随机逼近算法解决双层问题,无论是上 / 下目标值还是它们的无偏梯度估计都不可用。通过利用斯坦恩恒等式,首先使用高斯平滑估计具有两个独立块变量的函数的一阶和二阶偏导数。然后,在随机逼近算法框架中使用这些估计来解决双层优化问题,并建立其非渐近收敛分析。据我们所知,这是第一次为完全随机零阶双层优化算法建立样本复杂度界限。
Mar, 2024
提出了一种推广后的交替优化方法(GALET)用于双层优化问题,可以适用于具有非凸下层目标函数的问题,并具有与一阶梯度下降相同的收敛速度。
Jun, 2023
本文关注于无强凸性假设的双层优化问题中局部最优性条件的探讨,提出了两类下层目标的增长条件从而推导出 Goldstein 稳定性条件,并引入了 Inexact Gradient-Free Method 方法进行求解。
Jan, 2023
本研究提出了一种技术,用于近似具有非唯一解的非光滑下层问题的双层优化问题。通过迭代算法代替下层最小化问题的极小化器的表达式,使用适当的非线性近端距离函数,可以使迭代算法的更新映射可微。
Feb, 2016