有限维极大极小问题的算法研究

有限维极大极小问题的算法研究

1直接法算法与设计有限维的大致小问题通常被定义为。不失一般性,本文假设g由于极大极小问题在许多科学与工程中有着重要应用,特别是形如max的函数频繁地出现在各类数值分析和优化问题中,因此对于求解该类问题的算法研究长久不衰.这些算法一般分为两大类:一类是直接法,其算法设计仅以有效地求解原问题(P)为目的;另一类是间接法,其算法以找一个能够替代不可微max函数φ(x)的光滑函数为目的,故这类算法被称为光滑化方法.文在文其中为正则化参数.通过直接求解上述问题,作者导出了一个具有一致逼近φ(x)性质的光滑函数(又称凝聚函数)从而将不可微优化问题(P)的求解转化为解一个光滑函数的无约束优化问题:基于同样思想,这里的μ鉴于光滑化方法不仅可以用于原问题(P)的求解,而且可用光滑函数代替某些问题中的max函数,将不可微问题转化为可微问题求解,故通过熵正则化方法得到的光滑函数φ2极大极限问题的指数乘子罚函数考虑如下一般不等式约束的非线性规划问题:利用指数罚函数Φ(t):=exp(t-1),可将其转化为如下无约束优化问题:其中的参数p为惩罚因子.若利用指数乘子罚函数,则需在惩罚项外引进一组对应各约束的拉格朗日乘子μ下面,我们将原来的极大极小问题(P)改写成为其等价的非线性规划问题:然后将(6)中的指数罚函数和(7)中的指数乘子罚函数分别应用到这个问题上,通过简单的运算即可导出用熵正则化方法得到的光滑函数φ由于:对巾此可以求得把这个关系式代入到(9)式的Φ当用(7)式的指数乘子罚函数时,我们则得到如下的无约束优化问题通过类似的推导,即可得到由叉熵正则化方法导出的光滑函数φp(x,μ).虽然该函数以前曾由Bertsekas在3对偶对偶问题在上一节里,我们用指数(乘子)罚函数方法求解与极大极小问题(P)等价的非线性规划问题(PE),得到了用熵正则化方法导出的两个光滑函数φ定理1熵正则化方法与指数(乘子)罚函数法是互为对偶等价的.证明根据凸分析[10]中指示函数的定义,带单纯形约束λ∈Δ的熵优化问题(1)可改写为因此,熵正则化方法可以解释为:先解一个对偶空间的极大化问题(12)后,再回到原空间解极小化问题,即相当于解如下极大极小问题对任意固定的x∈R其中函数和凹函数,且满足Fenchel对偶定理的条件(b).再考虑到极大化问题(12)存在唯一解且可达到有限最优值,故由Fenchel定理可知,熵正则化问题(12)的对偶问题为其中下面,我们分别来求出,其中Δ1={λ∈R其中和其中ω∈R为一变量.综合上述三个式子,我们得到另外,由共轭函数定义,容易求得由(15)-(17)三式,即可得到熵正则化问题(12)的对偶问题为因此,问题(13)最后归结为这与(9)式给出的一般指数罚函数问题完全相同.因此,极大熵方法和一般指数罚函数法是互为对偶等价的.如果将(12)式中的Shannon熵函数替换为叉熵函数中E明,叉熵正则化方法和指数乘子罚函数方法是互为对偶等价的.上述定理充分揭示了熵正则化方法的本质,即它们与指数(乘子)罚函数方法对偶等价,两种方法可说是殊途同归,最终都归结为解相同的光滑无约束优化问题.4原问题的分量函数根据光滑函数φ(1)误差界限:φ(:r)≤φ(2)单调性质:φ(3)逼近性质:(4)凸性:若原问题的所有分量函数是凸的,则φ另外,从本文导出这两个光滑函数的过程中知道,它们分别是简单的指数罚函数和指数乘子罚函数,因此它们也有着相应罚函数的优缺点.函数φ从公式中看出,若在第k次迭代中,某个乘子分量5个充分大的固定常数根据前面的讨论,无论是采用熵正则化方法还是指数(乘子)罚函数方法,最终都将问题(P)的求解简化为解以光滑函数φ由于φ其中φ(x)代表当前迭代点x处所有分量函数在下面的计算中,我们故意将p置为一个充分大的固定常数In(m)(1.0e+5),这样做有如下几个目的:第一,说明在实际计算中,因参数p过大而导致的病态问题并非如想象的那么严重;第二,说明通过取一个适当大的参数p,仅需进行一次无约束极小化,即可得到原问题的一个高度精确的解;第三,澄清对函数φp(x)及其梯度计算中会产生指数计算溢出的误解.对参数p按上述方式取值后,我们以x从上述计算结果可以看到,只要根据问题的精度要求,取一个适当大的参数p,仅通过一次无约束优化,得到的解已非常接近精确解.而且,在上述例题中,有的问题里出现分量函数为非凸函数的情形,该方法仍然给出了可以与其它方法[12,13]相匹敌的满意结果6指数乘子罚函数方法与传统监管方法的互补作用本文的重点在于,通过对熵正则化方法与指数(乘子)罚函数方法间对偶等价关系的揭示和论证,在相对较新的熵优化方法与传统的指数(乘子)罚函数方法间建立一