关于规模化双层规划问题的最优性与算法研究

Bilevel program is an important mathematical programming problem and it has many applications in the fields including transportation, engineering design, and so on. However, bilevel program is much more difficult to solve than standard mathematical programming problems. During the past decades, researchers mainly focused on some simple cases such as bilevel programs with few decision variables or small data size. Nevertheless. for a vast amount of practical cases, the study on bilevel programming, especially the numerical algorithm is far from developed. This project aims to somehow complete painting the picture of study on modelling, optimality theory and algorithmic implement for large-scale bilevel programming with solid background: (1) the bilevel model with sparse-driven upper level and robust/distributionally robust lower level inspires the investigation of optimality conditions as well as associated constraint qualifications, the design of effective algorithm and convincing experimental test with real-world data. In particular, we will use a new step-wise algorithmic technique to design the solution scheme, also the corresponding enhanced optimality will be explored in Banach space due to the distributional robustness concerned. (2) two structural bilevel models arise from the application in imaging science. Avoiding the employment of KKT single-level reformulation reduces a lot of computational loads. The alternating minimization method and alternating direction multipliers method are involved. Specifically, the bilevel hierarchy could be broken temporarily and the objectives would be splitted into blocks, hence that the alternating techniques are able to be recalled repeatingly to solve either the master problem or sub-problems efficiently.

双层规划是数学规划的重要分支，在交通运输、工程设计等领域有广泛应用。 然而，与普通数学规划相比，双层规划的求解要困难得多。目前有关研究主要集中于较少决策变量，较小数据规模等简单情形。对于大量实际问题，受限于计算难度，双层规划的研究，特别是在数值算法方面，还远未成熟。本项目旨在完善具有一定数据规模的实际双层规划问题的建模、理论与算法：(1) 稀疏-(分布式)鲁棒双层模型。我们将研究最优性理论和相应约束规格，并且设计有效算法，使用实际数据进行算法验证。特别的，我们将设计一类新的分步求解方案；同时对于分布式鲁棒问题，我们将在无限维空间中讨论增强的最优性理论。(2) 图像处理中的双层规划模型。我们将采用交替极小化方法和交替方向法，避免使用传统的KKT再定式均衡约束数学规划方法引入多余的互补乘子。具体地，我们将通过暂时破坏等级结构和目标分块等技巧， 多次调用交替求解方法来处理解构后的简单问题。

本项目集中针对双层规划/均衡约束数学规划理论与算法，简单双层规划在计算机视觉中的算法与应用，误差界条件与一阶分裂算法收敛分析三个方面开展研究。采用变分分析、扰动分析等优化工具，深入挖掘机器学习、计算机视觉、统计学习等应用场景下常用模型的内在结构，刻画一阶高效最优化算法的快速收敛率；丰富了机器学习里常用算法和模型的理论可解释性，为机器学习算法和模型的匹配提供了有效的指南。同时，针对计算机视觉问题，提出一类视觉任务驱动的智能优化方法，以及一类模型驱动的双层深度学习方法，在图像去噪，去模糊方面，我们提出的双层规划模型与算法可以达到state of art效果。