论文部分内容阅读
本文着重研究了求解最优化问题的两种网格型算法.一类是求解局部最优化问题的直接搜索算法,另一类是求解有界约束的全局最优化问题的DIRECT(DIvidingRECTangle)算法.在第2章,我们在Coope-Price直接搜索算法框架下,提出了一种混合非单调下降条件,并针对该条件提出一种网格步长的分区域更新策略.在此基础上提出Mix-DSCG算法,该算法在数值表现上比原始的DSCG算法更可靠(reliable),在收敛理论上需要的条件更简洁.具体来说, Mix-DSCG算法使用混合非单调下降条件,不允许网格步长增加,从而不需要假设网格步长的极限为0就能保证收敛性,在第3章,我们以最小正基为基础,引进单纯形梯度和下降型无导数共轭梯度方向,在Coope-Price直接搜索框架内构建了MDSCG算法.在通常的条件下可以证明MDSCG算法的收敛性.数值结果表明, MDSCG算法对使用最大正基的DSCG算法以及著名的Nelder-Mead单纯形法等算法具有优势.在第4章,我们将多重网格思想应用到求解全局最优化问题的DIRECT算法中,提出了一种基于多重网格搜索的全局优化算法,称为MGGO算法.迄今为止,我们尚未见到有关的研究工作,我们所做的工作是将多重网格思想应用到全局最优化问题中的首次尝试.在仅假设目标函数Lipschitz连续的条件下,我们证明了MGGO算法的全局收敛性.与原始DIRECT算法和其他一些相关算法的数值比较表明, MGGO算法是一种很有效的确定性全局最优化算法.同时,数值实验结果也表明, MGGO算法对参数比较敏感,这一点非常类似于求解线性方程组的几何多重网格法.在第5章,本文还研究了带残差校正的多重网格法的收敛性.我们把多重网格方法看成是一种扰动的两重网格方法,得到了一个描述多重网格方法的收敛因子与两重网格的收敛因子的不等式.该不等式表明,对于带残差校正的多重网格法W-循环,存在收敛因子的一个与网格层数无关的一致上界/(1 ),其中< 0.5是两重网格法的收敛因子的上界.我们证明无论残差校正发生在哪些层上, /(1 )始终是带残差校正的多重网格W-循环的收敛因子的一致上界.同时我们还证明,当0.5 < < 1时,只要适当选取循环系数,带残差校正的多重网格法的收敛因子总存在一个与层数无关的一致上界,且该上界总小于W循环的上界/(1 ).这一结果表明,即使两重网格法收敛得不是很好,只要适当选取循环次数,多重网格的总体收敛因子仍存在较小的与层数无关的一致上界.所做的数值实验验证了适当的残差校正对多重网格法的收敛加速,并验证了两重网格法收敛得更快时多重网格法也收敛得更快.此博士论文得到了国家自然科学基金(10971058, 11071087)的资助.此博士论文用软件打印.