解非线性规划的一个磨光罚函数法

[摘要]针对约束非线性规划问题,引进磨光参数α,构造了包含α的连续可微惩罚函数,提出了磨光惩罚函数法。该方法克服了传统简单罚函数法在处理不等式约束中出现不可微函数的缺陷,并且简单可行,易于实现。最后,证明了当α0时磨光惩罚函数法的收敛性问题。并利用算例验证了方法的有效性。

[关键词]非线性规划 惩罚函数法 磨光法

一、引言

惩罚函数法是求解约束型非线性规划的有效算法之一。但对具有不等式约束的非线性规划问题,常用的简单罚函数法存在缺陷。由于一般的简单罚函数在可行域边界点上不可微,因此给求解无约束优化问题的编程计算带来不方便。近年来,关于处理不可微优化问题的算法很多,但大多数算法是引入次梯度的迭代算法,理论推导复杂,局限性比较大,编程计算仍然不便。受文献[1-2]利用磨光参数处理不可微点技术的启发,提出求解约束型非线性规划的磨光惩罚函数法。文献[1]利用磨光参数获得了非光滑最优控制的差分解,文献求解了具有互补约束条件的优化问题,同样引进了磨光参数将不可微点近似处理为可微函数,逐步逼近真解。磨光惩罚函数法的基本思想是,在简单罚函数法的基础上利用磨光参数将非光滑罚函数近似为光滑函数,进一步采用可微函数的常规算法获得包含磨光参数的近似解,通过逐步细磨获得最优解。该方法避开了罚函数的不可微性,使编程求解更加初等化,简单化。

二、简单罚函数法和磨光参数

考虑具有不等式约束的非线性规划问题:

Min f(x) (1)

(2)

其中f(x),gi(x)是Rn上的连续的可微函数。实现这类约束问题求解的途径是由目标函数和约束函数组成辅助函数,把原来的约束问题转换成为极小化辅助函数的无约束问题。

定义辅助函数为下列形式:

是满足下列条件的连续函数

其中,的典型取法为,其中β≥1均为给定的常数,通常取为2。构造增广目标函数,得到外点罚函数算法[4-5](SUMT)。

算法1:(SUMT)

三、磨光罚函数法及其收敛性

值得说明的是,算法2:(S- SUMT)得到的解对应的目标值与算法1(SUMT)得到的解对应的目标值相同,但最优解不一定相同。然而,如果问题(1)(2)的解唯一,则两算法得到的最优解相同。

四、数值例子

考虑约束型非线性规划问题

五、结束语

由算例可以看出随着磨光参数的减小,在同样的惩罚因子下,其解逐步趋近于精确解。因此本文提出的磨光罚函数法(S- SUMT)是可执行的,有效的。更重要的是该算法避开了简单罚函数不可微的缺陷,使得原问题连续可微,有利于编程实现。

参考文献:

[1]Xiaojun Chen. Finite difference smoothing solutions of nonsmooth constrained optimal control problem[J].Numerical Functional Analysis and Optimization, 2005,26(1):49-68.

[2]Xinmin Hu, Daniel Ralph. Convergence of a penalty method for mathematical programming with complementarity constraints[J].Journal of Optimization and application,2004,123(2):365-390.

[3]Scholtes,S. Convergence Properties of a Regularization scheme for Mathematical Programs with Complementarity Constraints[J].SIAM Journal on Optimization,2001,11(4):918-936.

[4]陈宝林.最优化理论与算法[M].北京:清华大学出版社,2005.

[5]袁亚湘,孙文瑜.最优化理论与方法[M].北京:科学出版社,2001.