一类非线性二层规划的Frank_Wolfe方法

1、第卷第期年月自然科学版）湖北大学学报（），（）文章编号：一类非线性二层规划的方法张涛，吕一兵（）长江大学信息与数学学院，湖北荆州摘要：利用下层问题的最优性条件将下层为线性规划的一类非线性二层规划转化为相应的单层规划，同时取互补条件为罚项，得到该类问题的单层罚问题；然后利用方法对单层罚问题进行求数值实验表明该方法是可行的解非线性二层规划；最优解；方法关键词：文献标志码：中图分类号：引言二层规划是一种具有递阶结构的系统优化问题，其数学模型可以表示为：，（，（，；），（）（），其中，分别称为上层目标函数以，（，分别为上层决策变量及下层决策变量）（）及下层目标函数对二层规划的求解是比较困难的，即使最简

2、单的情况即所有的函数为线性函数，也是难问题、求解非线性二层规划就更加困难了，目前求解非线性二层规划的方法主要包括分支定界法下降方，以及信赖域方法等事实上，由于非线性二层规划的复杂性质其算法设计一般针对的是具有法某种特殊结构的非线性二层规划问题在本文中，考虑如下形式的二层二次规划问题：（，（，）（），是下面问题的解，（，（）（），（），其中（，均为已知向量，）（）分别为上层和下层的目标函数，（）（）为对称矩阵，下层规划问题的决，分别为上层、策变量），对于二层二次规划问题（考虑以下层问题的最优性条件代替下层问题，同时取互补条件为罚项，从而得到该类非线性二层规划的相应单层规划问题由于相应的单层规划为

3、二次规划问题，因此考虑用在本文接下来的内容中，首先介绍相关的概念以及算法的理论基方法进行求解）然后，设计二层二次规划问题（的并以数值实验验证算法的可行性；最后对本础；方法，文进行小结收稿日期：）基金项目国家自然科学基金项目（资助；教育部重点实验室开放基金项目（资助；湖北省教育厅重点项）目（资助），作者简介：张涛（男硕士湖北大学学报（自然科学版）第卷主要结果令，其中则下层目标函数（即为：，），（）（）（定义称集合为二层二次规划问题的约束域，）定义称集合使得（是上层决策变量的可行域，存在，）为了讨论方便，我们假设是非空紧的假设是负定矩阵因此对每个给定的上层决策变量，下层规划问题存在唯一的解，不妨记

4、为（而且下层问题存在最优解，）（定义称集合为二层二次规划问题的可行域，），）（尽管约束域是一个凸多面体，但二层二次规划问题的可行域因此二层二次一般不再是凸集，规划问题是非凸规划问题下面给出二层二次规划问题的最优性条件，这也是求解二层二次规划算法的理论基础，定理，（为二层二次规划问题最优解的充分必要条件是存在，）使得（是下面规划问题的解，），（，）（）（），）在问题（的约束条件中除互补外，其余均为线性约束，笔者考虑以互补条件为罚项，用精确罚函数的方）法求解即问题（转化为：，（，（）（）（），（）（）其中：为罚因子），对于模型（与（等证明了如下的定理）定理如果问题（的可行域非空，且对于某个，问题（

5、有解，则必存在使得对）问题（与（有相同的非空最优解集于所有的，），从定理可以看出欲求解非线性规划（只需求解相应的单层规划（而模型（的求解方法建），立在如下命题的基础上为叙述方便，不妨记模型（的目标函数为其中：（）（，则相应的约束条件记为：），其中，为如下分块矩阵：，）此时模型（等价的记为：，（），（）（）假设（为问题（的任一可行点，在（处取的一阶则问题（转换为：（）展开，（）（），）对于问题（与（之间的关系有如下的命题），定理设问题（有最优解（则有如下结果：（）（）（）（如果则（是问题（的点（），（）（）（）（）（）如果则（的一个可行下降方向（）不成立，是问题（），定理的证明（因为问题（有最优

6、解（则必存在行向量，使得：（）（），（），第期张涛等：一类非线性二层规划的方法其中：，（）（）（）（）（），（）（）（）（）（）（）（）（）（）（）（）（），（）（）（又因为（），（）（）（）（）（）则（）（）（则有由此，存在使和，（），（）（），（）这就证明了如果则（是问题（的点（）（），（）（）（）（如果则有：（）不成立，（）（）（）（）（）（）（）（）因为（为问题（的最优解，故对于问题（与（的任一可行点（有：（）（）（）（）（），即：（）（）（）（）（）这就证明了（的一个下降方向，同时（的可行方向是显然的为问题（为问题（）（），（从定理中的结论（进一步有，如果（这时可从（出发，沿方向（）

7、，（）即求进行精确线性搜索使得：（）（）（）（），（）（）（并取）（以上就是传统的步骤（）（）（）（）算法及数值实验）基于上述讨论，可形成如下求解问题（的算法，具体的算法步骤如下算法：以及误差限；给定罚因子，）转化为（式；将二层二次规划（）式中的互补松弛条件取为罚项，得到如下单层规划将（，（，），（，（）（），），）的目标函数在可行域的点处线性展开得到：将规划（，）（，（，），（）（），），），）式的最优解为检验是否满足终止条件，如果有（假设（，（）则为（式的点；否则沿方向进行精确线性搜索，即求，满足：，（），同时令转，（：为验证本算法的可行性，我们考虑如下二层二次规划问题，）（，（），）文献

8、中最优解，（）将（式的下层问题用其条件代替同时取互补松弛条件为罚项得到如下单层规划：，（），各变量均大于、等于零，（）湖北大学学报（自然科学版）第卷，对于上式不妨令（取初始可行点罚因子误差限，（，），）在初始可行点对（式的目标函数线性展开，同时求解可得到（，），取方向经检验知不满足终止条件，沿搜索可得到新的展开点（，），在该点展开求解可得到取方向经检验，（，）知不满足终止条件，沿搜索得到新的展开点（，），），）在该点展开求解得到检验可知：则为（，（，）二层二次规划（的最优解即，（从数值实验我们可以看出求解二层二次规划的同时如果误差限取的方法是可行的，更小，则得到的解将更加逼近原最优解小结从算法的收敛性及算例实现的过程可知从非线性