摘要
极大极小问题是一类特殊的非光滑优化问题，它是在“最糟糕”的情况下寻找“最优”的决策方案.该问题在实际生活中有很广泛的应用，且许多数学问题在一定条件下可以转化成极大极小问题进行求解.求解分量函数具有凸性的极大极小化问题方法已经比较成熟了，但对非凸极大极小化问题的求解方法还有待深入研究.在本文中我们主要研究的是求解一类非凸无约束极大极小问题的可行下降束方法，我们首先采用重分配束方法的思想对目标函数的所有分量函数进行局部凸化，再利用迫近束方法思想构造相应的割平面模型，将原子问题转化成一系列二次规划子问题.接着结合对偶理论和原始子问题与对偶子问题最优解之间的关系求解，从而获得下一个新的迭代点.然后用增量型束方法的思想对束集进行重置、扩充、更新并扩充，进而设计出一类非凸无约束极大极小问题的可行下降束算法.最后对设计的算法进行收敛性分析. 本文共有四部分，主要内容如下： 第一章，首先给出了一些与非凸无约束极大极小化问题相关的基本概念和理论等相关知识；接着介绍了一般束方法的主要思想和具体算法，最后阐述了增量型束方法的基本原理，为之后几章开展研究奠定理论基础. 第二章，着重研究一类非凸无约束极大极小问题的求解，首先采用重分配思想对分量函数进行局部凸化，利用切平面模型构建技术对凸化后函数进行模型构造，之后借助迫近束方法的思想构建产生下一个试探点的二次规划子问题，再对子问题近似解的表达式和相关性质展开研究，接着阐述为保证目标函数值下降且迭代可行的策略，最后介绍对束集采用的更新策略，为算法的进一步构造奠定基础. 第三章，综合前一章中的理论框架，这一章针对所研究的这类非凸极大极小问题提出一种可行下降束算法，首先给出算法的基本框架和参数设置，接着给出算法的具体步骤，最后对算法中需要注意的地方给出几点说明. 第四章，侧重证明上一章中给出的求解非凸无约束极大极小问题的可行下降束算法的收敛性.首先证明了算法的主迭代会有限次终止，接下来证明了在有限次迭代后得到的迭代点满足某种近似最优性条件，且该点就是原问题的近似最优解，因而证明了算法具有一定的收敛性.
NETL