论文部分内容阅读
双层规划问题(Bilevel programming)在工程设计、经济均衡、交通运输等方面有着广泛的应用.当下层问题是关于变量y的凸规划时,通常的处理方法是将下层问题替换为其KKT条件,从而将这一双层规划问题转化为一个均衡约束数学规划问题(Mathematical programs with equilibrium constraints简称MPEC).然而,当下层问题关于变量y不是凸规划时,求解这样的转化问题无法得到原问题的最优解.大多数求解双层规划问题的算法都假设下层问题关于变量y是凸规划.因此,对于下层问题关于变量y不是凸规划的双层规划问题如何求解,是一个值得研究的课题.在本文中,我们提出一系列算法来求解此类双层规划问题,并将其应用到半无限规划问题上.(1)在第三章,通过定义下层问题的值函数,我们将双层规划问题转化为一个单层的带有非光滑不等式约束和凸约束集合的优化问题.为了处理该问题,我们设计了一个光滑投影梯度法来求解一般的非凸非光滑问题.我们证明了,当乘子序列有界时,算法生成的点列的任意聚点都是原问题的稳定点.进一步,如果生成的序列收敛并且广义的Mangasarian-Fromovitz constraint qualification (MFCQ)在极限点处成立,那么该极限点就是原问题的稳定点.当双层规划问题满足平稳性条件时,我们就可以应用光滑投影梯度法来求解该问题.否则,我们求解一个近似的双层规划问题.(2)在第四章,我们考虑双层规划问题的联合问题,其中一阶条件和带有值函数的约束都包含在该问题的约束条件中.由于在通常情况下,值函数是非光滑的,因此联合问题是一个非凸非光滑问题.我们提出一个光滑投影增广Lagrangian方法来求解这样的优化问题.我们证明了,当乘子序列有界时,算法生成点列的任意聚点都是原问题的稳定点.(3)在第五章,我们考虑一个目标函数和约束函数都是非光滑非凸的优化问题.我们使用满足梯度相容性质的光滑函数族来近似非光滑函数,并提出了一个扰动的序列二次规划算法来求解该问题.我们证明了,当乘子序列和罚因子都有界时,算法生成点列的任意聚点都是原问题的稳定点.进一步,我们提出了一种弱于GMFCQ的约束规格：weakly generalized Mangasarian Fromovitz constraintqualification (WGMFCQ).我们证明了,广义形式的WGMFCQ能够保证罚因子和乘子序列的有界性,因此能保证全局收敛性.通过数值实验可以看出,双层规划问题虽然永远不能满足GMFCQ,却很可能满足WGMFCQ.这说明该算法对求解双层规划问题是有效的.(4)在第六章,我们提出一个增广Lagrangian方法来求解非凸非光滑的优化问题.我们证明了,当乘子序列有界时,算法生成点列的任意聚点都是原问题的稳定点.进一步地,我们证明了,广义形式的WGMFCQ能够保证罚因子和乘子序列的有界性,因此能保证全局收敛性.由于在GMFCQ不成立时,WGMFCQ也可能成立,我们的算法可以求解不满足GMFCQ的问题,包括双层规划问题.(5)在第七章,我们考虑带有凸约束集合的半无限规划问题.通过定义下层问题的值函数,我们将半无限问题转化为一个非光滑的优化问题.由非光滑的Lagrange乘子法则和Danskin定理,可以得到约束规格和必要性条件.我们设计了一个求解该问题的数值方法.该算法主要是用积分熵函数来近似值函数并应用光滑投影梯度法来求解.进一步地,我们研究了近似问题和原问题的关系,得到了积分熵函数与值函数的误差界,给出了原来的半无限规划问题与其光滑问题的局部最优解之间的关系.通过一些二阶条件,我们可以估计出原问题的局部最优值.