求解双层规划问题的光滑化牛顿方法

A Smoothing Newton Method for Bilevel Programming Problems

摘要: 考虑一类具有特殊结构的双层规划问题，其上层问题无约束，而下层问题为凸优化问题。首先，通过引入下层问题的值函数，将原问题转化为单层优化问题(VP)。在部分平稳性条件下，通过将值函数约束惩罚到目标函数，进一步得到问题(VP)的部分精确罚问题。随后，在一定的约束规范条件下，推导出该罚问题的最优性条件，并利用光滑障碍增广拉格朗日函数方法处理其中的互补约束条件，从而将问题转化为超定方程组进行求解。针对该方程组，采用经典的高斯牛顿法进行求解，并理论证明了当障碍参数趋近于零时算法的收敛性。最后，基于BOLIB库中的小规模问题开展数值实验，将所提算法与LM算法、拟牛顿法等方法的计算结果进行对比分析，实验结果表明了该算法的有效性。

Abstract: Consider a class of bilevel programming problems with a special structure, where the upper-level problem is unconstrained and the lower-level problem is a convex optimization problem. First, by introducing the value function of the lower-level problem, the original problem is reformulated into a single-level optimization problem (VP). Under the partial calmness condition, an exact penalty problem for (VP) is further derived by penalizing the value function constraint into the objective function. Subsequently, under certain constraint qualifications, optimality conditions for the penalized problem are established. The complementary constraints in the optimality conditions are handled using a smoothing barrier augmented Lagrangian function method, transforming the problem into an overdetermined system of equations. To solve this system, the classical Gauss-Newton method is employed, and the convergence of the algorithm is theoretically proven as the barrier parameter tends to zero. Finally, numerical experiments are conducted on small-scale problems from the BOLIB library. The proposed algorithm is compared with the LM algorithm, the Quasi-Newton method, and other approaches. The experimental results demonstrate the effectiveness of the proposed algorithm.