半向量二层规划问题的算法设计与应用研究

As a typical bilevel programming problem with non-unique lower level optimal solutions for the fixed upper level variable, semivectorial bilevel programming problem(SBPP) has been drawing much attention of the researchers in recent years. It is worth pointing out that the existing theory and method on the SBPP are relatively scattered, particularly the algorithms with numerical experiment results for the “optimistic optimal solution” and “pessimistic optimal solution” . The program would propose more effective algorithms for the “optimistic optimal solution” and “pessimistic optimla solution” of two classes of semivectorial bilevel programming problems(the lower level problems are convex and nonconvex vector optimization problem respectively) and resolve some practical problems based on the semivectorial programming. Particularly, its contents include: (1) For the SBPP with the convex vector optimization problem in the lower level, a penalty function approach for its “optimistic optimal solution” is proposed, and the convergence of the penalty function algotithm is analyzed. (2) For the quadratic-linear SBPP, we construct the neural network model for its “pessimistic optimal solution”. The conditions guaranteed the convergence of the neural network model are obtained. Then, the neural network model is realized by making programs and some computer simulation results are presented to illustrate the neural network approach. (3) For the SBPP with the nonconvex vector optimization problem in the lower level: ① Under the definition of “optimistic optimal solution”, a non-smooth optimization problem is obtained, and the lower bounding problem and the upper bounding problem are constructed respectively. Then, a bounding algorithm is proposed for the “optimistic optimal solution”, and the convergence of the algorithm is analyzed; ② Under the definition of “pessimistic optimal solution”, a non-smooth optimization problem is obtained, furthermore a semi-infinite optimization problem is constructed. Then, a discretization iterative algorithm is proposed for the “pessimistic optimal solution”, and the convergence of the algorithm is analyzed. (4) Based on the hierachical relationships lying in the inter-basin water transfer-supply multi-reservoir joint operation problem, a semivectorial bilevel programming model deciding the optimal water-transfer and water-supply rules is constructed, and an effective algorithm is given based on the character of the model. Furthermore, the feasibility and effectiveness of the model are illustrated with some practical instances.

近年来，半向量二层规划问题（SBPP）正引起越来越多研究者的关注。然而，目前有关SBPP的理论和方法还十分零散，尤其缺乏较为有效的求解算法。本项目拟设计SBPP“乐观最优解”与“悲观最优解”的求解算法并将其应用到实际问题的求解。主要研究内容包括：（1）设计下层为凸向量优化的SBPP“乐观最优解”的罚函数算法并分析其收敛性。（2）构建二次-线性SBPP“悲观最优解”的神经网络模型，研究模型的收敛性条件并给出模拟计算结果。（3）下层为非凸向量优化的SBPP：①在“乐观最优解”的意义下，将其转化为非光滑优化问题，构造出上界问题与下界问题，设计出定界算法并分析其收敛性；②在“悲观最优解”的意义下，将其转化为非光滑优化问题，进而转化为半无限优化问题，设计出离散迭代算法并分析其收敛性。（4）构建跨流域供水水库群联合调度的半向量二层规划模型，给出其求解算法并以相关应用说明模型的可行、有效性。

半向量二层规划问题是一类典型的下层有不唯一最优解的二层规划问题。目前有关半向量二层规划问题的研究大部分局限于诸如最优性条件等方面的理论研究，仅有的可行算法也大部分针对下层具有某种特殊结构（如下层为线性向量优化问题等）的半向量二层规划问题。如何对结构较为一般的半向量二层规划问题的“乐观最优解”与“悲观最优解”设计较为有效的求解算法，成为二层规划领域亟需解决的问题。.本项目主要完成了以下研究工作：（1）对下层为凸向量优化的半向量二层规划问题“乐观最优解”设计了罚函数方法；另外，对线性二层多目标规划问题分别设计了精确罚函数方法和平衡点方法。研究表明，线性二层多目标规划问题的若有效解在其约束域的顶点处取得，同时精确罚函数算法和平衡点算法的最大特点在于只需要求解一系列线性规划问题就可以得到线性二层多目标规划问题的弱有效解。（2）分别设计了二次—线性半向量二层规划问题“悲观最优解”与一类多领导-多追随博弈问题（Multi-leader-follower games，本质上为一类半向量二层规划问题）的神经网络算法，分析了神经网络算法的渐进稳定性，并给出了仿真计算结果。（3）对下层为非凸向量优化的半向量二层规划问题“乐观最优解”与“悲观最优解”，分别设计了定界算法和离散化算法，分析了算法的收敛性，并给出了数值计算结果。（4）构建了跨流域供水水库群联合调度问题的半向量二层规划模型，并给出了改进的粒子群求解算法。对比研究表明，本项目所构建的乐观半向量双层规划模型可以更加有效地得到最优的调水和供水规则。（5）对线性三层规划问题分别设计了松弛以及罚函数求解算法。研究表明，线性三层规划问题的最优解可以在约束域的某顶点处取得。另外，罚函数求解算法的最大特点在于只需要求解一系列线性规划问题，就可以得到线性三层规划问题的最优解，因此具有良好的应用前景。（6）其他与半向量二层规划密切相关优化问题的研究。