双层规划问题的二阶最优性条件与光滑函数方法

The bilevel program is a class of important optimization problems which has numerous applications in engineering and economics. Since the usual constraint qualifications are never satisfied for the bilevel program, the classical theory and numerical methods for nonlinear programs are not suitable to deal the bilevel program. At present, most of researches on bilevel program impose special structures or strong hypothesis on the lower level program. For general bilevel program, there are no complete theoretical analysis or efficient numerical methods. Therefore it is of great importance to study theories and numerical methods for the bilevel program. Based on the variational analysis and nonsmooth analysis, the project is devoted to the study of second order optimality theories and numerical methods for the bilevel program. It contains the semi-smooth property of the value function of the lower level problem and its subdifferential computation, the computation or estimation of the coderivative of the subdifferential; improvement of the first order optimality conditions, construction of the second order optimality conditions, in particular, the second order sufficient optimality conditions which can be used for the analysis of the numerical methods; developing the smoothing theory of the value function so that it can be used to construct numerical methods for the bilevel program; including the penalty method, the augmented Lagrangian method, the sequential quadratic programming (SQP) method. We hope that this project will make an important contribution to the theory and numerical methods of the bilevel program.

双层规划问题是一类在工程和经济领域有着广泛应用的重要的最优化问题。由于双层规划问题不满足通常的约束规范，经典的非线性规划理论和算法不适合处理这类问题。目前关于双层规划问题的研究通常是针对下层问题具有特殊结构的情形，对于一般的双层规划问题，并没有完善的理论分析和有效的求解方法。因此，深入地研究双层规划问题的理论与算法有着重要的意义。本项目以变分分析和非光滑分析为基础，研究双层规划问题的二阶最优性理论和数值算法。内容包括研究下层问题最优值函数的半光滑性和次微分的计算，次微分伴同导数的计算或估计；完善双层规划问题的一阶最优性条件，建立双层规划问题的二阶最优性理论，尤其建立适合算法分析的二阶充分性最优条件；发展最优值函数的光滑化理论，用于构造双层规划问题的数值方法，包括罚方法、增广拉格朗日方法、序列二次规划方法等。期望本项目的研究成果对双层规划问题的理论与算法研究做出重要的贡献。

双层规划问题是一类具有上、下两层结构的数学规划问题，该问题在工程和经济方面有着重要的应用。本项目首先对不同的约束规范进行深入的对比研究，然后为了求解下层问题的目标函数关于下层变量y是非凸的情况，提出了一种新的增广拉格朗日方法。在满足一定约束规范的前提下，进一步证明了新的增广拉格朗日方法可以得到双层规划问题的可行的稳定点，最后通过数值实验成功地求解了双层规划问题。.另外，本项目分别从定性和定量两个角度给出了一类随机两阶段问题（线性二阶锥两阶段随机规划问题）的稳定性分析结果。两阶段问题的上层目标函数中包含了下层问题的最优值函数，所以其在模型结构、求解方法上都与双层规划问题十分相似。由于实际生活中往往存在许多无法确定的随机因素，因此本项目利用统计推断和渐近分析等方法研究线性二阶锥两阶段随机规划问题。一方面，在两阶段随机规划问题的Slater条件成立的前提下，证明了原问题及其对偶问题的解集映射的上半连续性，以及最优值函数的Hadamard方向可微性，从而得到定性的稳定性分析结果。另一方面，当随机变量的分布无法确定时，本项目通过求解一系列有确定分布的近似问题求解原问题，可以得到原问题的最优值和最优解集映射的渐近性结果。