解极大极小问题的积极集策略分析及其在算法中的应用.pdfVIP

解极大极小问题的积极集策略分析及其在算法中的应用

中文摘要

有限维无约束极大极小问题是一类典型的非光滑化优化问题，在工程设计，数据拟

合等领域广泛应用．光滑化积极集两阶段算法是求解该类问题的一类有效算法，该类算

法通过光滑化算法得到一个稳定点处满足一定精度的近似解，基于该近似解及积极集策

略求得该类问题的稳定点，但该类算法存在以下两类问题．首先，光滑化算法大多是基于

凝聚函数构造的，而凝聚函数的梯度及Hessian阵与全部分量函数的梯度及Hessian阵相

关，对分量函数较多的问题，每步迭代中凝聚函数的梯度及Hessian阵的计算量较大．其

次，理论上，对任意的稳定点，存在相应的扰动半径及扰动参数，对该稳定点处以扰动半

径为半径的邻域内任意的点，通过求解含扰动参数的线性规划问题得到稳定点处积极指

标集的一个满足一定条件的子集，称为线性独立积极指标集，但在具体的数值实验中，扰

动半径及扰动参数的选取缺乏数值经验．

针对以上两类问题，本文给出对应的策略．首先，利用一种含积极集策略的光滑

化最大值函数代替凝聚函数构造光滑化算法，降低光滑化算法中每步迭代的分量函数

及Hessian阵的计算量，基于对积极集策略的数值分析、该类问题的特点及含积极集策略

的光滑化算法，给出一种改进的光滑化积极集两阶段算法，初步数值实验表明该两阶段

算法具有更高的计算效率．其次，将利用参数线性规划的思想对扰动半径及扰动参数进

行数值分析，在给定扰动半径处，通过求解线性规划问题，求解出线性独立积极指标集对

应的扰动参数的下界，继续增大扰动参数，求解出线性独立积极指标集对应的扰动参数

的上界，得到线性独立积极指标集对应的扰动参数的区间，并且通过具体算例进行说明．

关键词：光滑化算法；积极集策略；稳定点；一阶最优性条件

I

II

AnalysisofanActiveSetStrategyforSolvingMinimaxProblemsand

itsApplicationinAlgorithms

Abstract

Thefinite-dimensionalunconstrainedminimaxproblemisatypicalnon-smoothingopti-

mizationproblem,whichiswidelyusedinengineeringdesign,datafittingandotherfields.The

smoothingactivesettwo-stagealgorithmisaclassofeffectivealgorithmsforsolvingthiskindof

problems,thistypeofalgorithmobtainsanapproximatesolutionthatmeetsacertainaccuracy

atastablepointthroughthesmoothingalgorithm,basedontheapproximatesolutionandthe

activesetstrategy,thestabilitypointofthistypeofproblemisobtained,butthealgorithm

hasthefollowingtwotypesofproblems.Firstofall,thesmoothingalgorithmismostlybased

oncohesionfunctionconstructed,thegradientofthecondensationfunctionandtheHessian

arrayarerelatedtothegradientHessianarrayofthewholepartialfunc