论文部分内容阅读
在实际生活中,面对很多问题我们往往不能简单的只考虑一种限制情况或只有一个优化目标,而是在多种条件的限制下,综合考虑多个优化目标,寻找一种最理想的解决方案.就像两个人下棋,对手每一次出棋就会增加一种限制条件,选手在此种条件下综合考虑多种出棋方案,寻找一个对自己最有利的方案,这种理论称为博弈论,是运筹学的重要组成部分,也是极大极小问题的萌芽.本文主要研究不等式约束极大极小问题(?)f(x)s.t.c(x)≤0,其中,目标函数∫(x)=max{fi(x),i∈I},约束函数c(x)=max{cl(x),l∈L}.针对此类问题,我们首先将约束优化问题利用改进函数法转化为无约束优化问题,再结合迫近束方法思想构造二次规划子问题进行求解.在这一求解过程中,嵌入了增量法、分量函数选择机制以及束修正策略,之后提出针对该问题的整体算法.最后给出该算法的收敛性分析.本文整体结构如下:第一章主要介绍一些与非光滑优化问题和不等式约束极大极小问题相关的定理、定义,以及几种解决非光滑优化问题常用的方法,为后文的研究奠定理论基础.第二章研究的是目标函数是单一函数,约束函数是最大值函数的优化问题.首先我们针对最大值函数引入增量法的思想,这在很大程度上减小了束方法的计算量过大问题,接着将迫近束方法与改进函数法相结合,构造子问题产生下一个试探点,同时在对偶空间求解子问题,最后给出对应的可行束方法,为第三章的深入研究作铺垫.第三章是本文的主体,研究的是目标函数与约束函数均为最大值函数的优化问题.我们首先延用第二章的解题思路,利用改进函数将约束优化问题转化为无约束优化问题.在定义改进函数的次梯度时,加入分量函数的选择机制,使得所选的分量函数在点yj处与最大值函数的值相同.其次给出针对该问题的束修正策略,由改进函数的次梯度定义可推导出方向yk+1-yi是函数Hxk(.)在点yj处的下降方向,因此可找到比yj“更好”的试探点yj.与此同时,利用两个引理我们证明了用新点yj替代旧点yj,依然可以得到问题的近似最优解.本章最后我们给出原问题的一种带有束修正策略的算法.由于应用束修正策略后得到的是近似最优解,为使此差值尽可能的小,该算法增加了束重置步骤,将束中使上述差值增大的元素删除,之后再进行下一步迭代.第四章,针对第三章提出的算法,分两种情况论证了算法无论产生有限个下降步(后面都是零步),还是产生无限个下降步,所构造算法都具有全局收敛性.