求解约束优化问题的增广拉格朗日函数法

约束优化问题广泛见于工程、国防、经济、金融和社会科学等许多重要领域.求解约束优化问题的重要途径之一是把它们转化成无约束优化问题进行求解.罚函数方法是将约束优化问题无约束化的一类主要方法,它们通过求解一个或一系列罚问题来得到约束优化问题的解.我们称罚问题的目标函数为一个罚函数.罚函数一般与某个罚参数有关.如果当罚参数取大于某个较大正数的值(或者取大于零且小于某个小正数的值)时,对应的罚问题的极小点与原约束问题的极小点之间存在某种精确的对应关系,则称对应的罚函数为精确罚函数;反之,如果对于罚参数的任何正的有限值,对应的罚问题的极小点与原约束问题的极小点之间都不存在精确的对应关系,而当罚参数趋于它的极限值(无穷大或者零)时,对应罚问题的极小点的极限值与原约束问题的极小点之间存在某种精确的对应关系,则称对应的罚函数为序列罚函数.序列罚函数方法在理论上需要求解无穷多个罚问题来获得约束优化问题的解.这种方法的主要缺点是,当罚参数的值很大(或者很小)时,罚问题成为坏条件问题,从而使这种方法产生数值不稳定和收敛慢等缺点.精确罚函数方法在理论上只需要求解一个(或有限多个)罚问题来获得约束优化问题的解,从而避免了序列罚函数方法产生坏条件的缺点.精确罚函数包括不可微精确罚函数和连续可微精确罚函数.在实际计算时,不可微精确罚函数法由于罚函数的不可微性而使算法产生所谓的“Maratos效应”,从而产生阻止快速局部收敛的现象.连续可微精确罚函数大体上又包括两类:一类是定义在原约束问题变量空间上的连续可微精确罚函数;另一类是定义在原约束问题变量空间和KKT乘子变量空间的积空间上的连续可微精确罚函数.第一类连续可微精确罚函数通过使用乘子函数实现对不满足KKT条件情形的“惩罚”.乘子函数是原问题变量的函数,它产生KKT乘子的估计.从计算的角度来看,当约束的个数较多时,确定乘子函数值的代价是相当大的,因为它需要求出与约束个数同阶的一个矩阵的逆,而每一次计算罚函数值都需计算出乘子函数值.正是由于这一原因,使得这种连续可微精确罚函数的应用在某种程度上受到了限制.第二类连续可微精确罚函数又可以分为两个子类:第一个子类是把考虑KKT条件的项加到约束问题的目标函数上;第二个子类是把考虑KKT条件的项加到通常的拉格朗日函数上,因此称之为增广拉格朗日函数.大量的理论结果和数值试验均表明,增广拉格朗日函数法(亦即使用增广拉格朗日函数作为罚函数的连续可微精确罚函数法)比序列罚函数法和不可微精确罚函数法具有明显的优点,它们克服了序列罚函数法产生坏条件和不可微精确罚函数法产生“Maratos效应”的