This paper presents a new approach and algorithm for solving a class of
constrained Bi-Level Optimization (BLO) problems in which the lower-level
problem involves constraints coupling both upper-level and lower-level
variables. Such problems have recently gained significant attention due to
their broad applicability in machine learning. However, conventional
gradient-based methods unavoidably rely on computationally intensive
calculations related to the Hessian matrix. To address this challenge, we begin
by devising a smooth proximal Lagrangian value function to handle the
constrained lower-level problem. Utilizing this construct, we introduce a
single-level reformulation for constrained BLOs that transforms the original
BLO problem into an equivalent optimization problem with smooth constraints.
Enabled by this reformulation, we develop a Hessian-free gradient-based
algorithm-termed proximal Lagrangian Value function-based Hessian-free Bi-level
Algorithm (LV-HBA)-that is straightforward to implement in a single loop
manner. Consequently, LV-HBA is especially well-suited for machine learning
applications. Furthermore, we offer non-asymptotic convergence analysis for
LV-HBA, eliminating the need for traditional strong convexity assumptions for
the lower-level problem while also being capable of accommodating non-singleton
scenarios. Empirical results substantiate the algorithm's superior practical
performance.

针对一类具有上下级变量耦合的约束双层优化问题，本研究提出了一种新的方法和算法。通过设计平滑的近端 Lagrangian 值函数来处理约束的下层问题，并将原始问题转化为具有平滑约束的等价优化问题，从而实现了一种适用于机器学习应用的基于近端 Lagrangian 值函数的非 Hessian 梯度算法。此外，还针对 LV-HBA 进行了收敛性分析，不需要对下层问题进行传统的强凸性假设，并且能够处理非单例情况。实证结果验证了该算法在实际性能上的优越性。