双层优化问题（Bilevel Optimization, BLO）在大数据和人工智能时代引起了广泛关注。它在强化学习、超参数优化和元学习等实际应用中具有重要作用。双层优化问题可以表示为两个序贯的优化问题，其中上层问题的目标函数值依赖于下层优化问题的解。然而，大部分已有的求解双层优化问题的高效方法均需假设目标函数的光滑性。因此，如何为非光滑的双层优化问题设计高效的，具有全局收敛性的优化算法具有重要的理论意义以及应用价值。本文研究了非凸-强凸双层优化问题(BLO)，其中上层问题的目标函数是非凸的，可能是非光滑的，而下层问题的目标函数是光滑的，对于底层变量是强凸的。我们证明在合适的条件下，BLO的可行域为嵌入在欧氏空间中的流形，并利用约束消解方法为这一流形优化问题构造相应的无约束优化问题(CDB)。我们证明了双层优化问题BLO与无约束优化问题CDB具有相同的一阶稳定点。因此，众多已有的求解无约束优化问题的高效算法，以及其相应的收敛性分析理论，均可通过CDB这一无约束优化问题直接应用于求解双层优化问题BLO。此外，我们为应用次梯度方法求解BLO提出了一个统一的框架。该框架能够兼容多种现有的高效算法，并将其解释为求解CDB这一无约束优化问题的非精确梯度下降算法。这一框架不仅简化了求解双层优化问题的算法设计，还提升了无约束优化算法的通用性和适应性。我们展示了几种现有的求解非凸-强凸双层优化问题的高效算法可以被统一在这一框架中，并被视为求解CDB这一无约束优化问题的非精确次梯度下降算法。基于这一视角，我们首次建立了这些高效算法在求解非光滑双层优化问题上的全局收敛性分析。这些例子进一步展示了我们所提出的方法的巨大潜力。

Publication:

SIAM Journal on Optimization (Volume: 33, Issue: 4, 2023)

https://doi.org/10.1137/22M1513034

Author:

Xiaoyin Hu

School of Computer and Computing Science, Hangzhou City University, Hangzhou, China.

Nachuan Xiao

The Institute of Operations Research and Analytics, National University of Singapore, Singapore.

Xin Liu

State Key Laboratory of Scientific and Engineering Computing, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, and University of Chinese Academy of Sciences, China.

Email: liuxin@lsec.cc.ac.cn

Kim-Chuan Toh

Department of Mathematics, and Institute of Operations Research and Analytics, National University of Singapore, Singapore