一种新的求解带等式约束的极大极小问题的罚函数

王福胜,张 瑞,高 娟,姜合峰

（太原师范学院数学系,山西晋中030619）

一种新的求解带等式约束的极大极小问题的罚函数

王福胜,张 瑞,高 娟,姜合峰

（太原师范学院数学系,山西晋中030619）

通过对经典的一类简单精确非光滑罚函数进行局部光滑化处理,及相应调整罚参数和光滑参数,构造出一种新的简单的光滑罚函数,将带等式约束的极大极小问题转化为对罚函数的无约束优化问题.初步的数值实验表明该罚函数算法是可行有效的.

带等式约束的极大极小问题；光滑化；罚函数

0 引言

许多工程设计以及金融经济问题都可以转化为极大极小问题的模型来解决,在本文中,我们考虑下面的带等式约束的极大极小问题：

其中,fj：Rn→R,j＝1,…,q和Fj：Rn→R,j＝q＋1,…,m是连续可微的函数.

一般来讲,即便fj（x）,j＝1,…,q都是连续可微的,但极大值函数一般不可微,因而问题（p）不能直接利用标准无约束算法求解.对这类问题已有的一些算法包括次梯度方法、捆绑法、切平面法以及利用光滑函数逼近极大函数的方法等等,其中,由于具有良好计算效率与数值结果,用光滑逼近手段处理极大极小问题是近年来较流行的做法.同样,将问题（p）转化为下面等价问题：

然后利用罚函数的方法求解这个一般约束优化问题也十分可行.

本文就是结合了求解约束优化问题重要方法之一的罚函数法与光滑逼近的思想,对传统的一类简单精确非光滑罚函数进行局部的光滑化处理,以及相应调整罚参数和光滑参数,构造出一种新的简单的光滑罚函数来求解问题（¯p）,也即等价地求解问题（p）,最后通过初等算例证明该方法的实效性.

1 新的罚函数的构造

对于传统的约束优化问题,如：

其中,f：Rn→R,Fj：Rn→R,∀j∈E和gl：Rn→R,∀l∈I是连续可微的,E,I分别为等式约束和不等式约束的指标集,求解该问题经常使用的传统罚函数gl（x）））是简单精确却非光滑的罚函数.而对于问题（¯p）,类似的罚函数即可表示为：

由于（1）式中存在｜z｜和max（0,z）形式的函数,故它是非光滑的,所以即便这个罚函数是既简单又精确的,我们也通常不能直接使用.下面先构造｜z｜和max（0,z）的光滑逼近函数：

首先,构造函数｜z｜的光滑逼近函数φ（z；u）和函数max（0,z）的光滑逼近函数φ（z；u）.

其中0＜u＜1为光滑参数,函数φ（z；u）和φ（z；u）只在小区间－u≤z≤u上对函数｜z｜和max（0,z）进行光滑化处理,依然保留了原函数整体性质,φ（z；u）和φ（z；u）的一阶和二阶导数分别为：

显然函数φ（z；u）具有下列性质：

1）对∀z∈R有,且0≤φ（z；u）－｜z｜≤u；3

2）－1≤φ′（z；u）≤1,φ（z；u）在（－∞,0）上是减函数,在（0,＋∞）上为增函数；

3）对∀z∈R,0＜u1＜u2,有φ（z；u1）≤φ（z；u2）.

同样,函数φ（z；u）也有相应性质（参见文献［3］）.

再令罚参数取δ＝u－0.5（1＜δ＜u－1）,对（1）式修正后产生新的光滑化的罚函数：

参数u既可以控制（＊）式对（1）式的逼近程度,也同样很好地协调了罚参数的大小,使新的罚函数具有较强的程序操作性.

由引理1可知,参数u越小,新构造的罚函数逼近传统经典的简单精确罚函数的程度越高,并且对于违反约束的自变量取值（x,t）,惩罚项会越大,也符合罚函数的本质特性；罚函数依旧保持了原问题凸性和可微性,并由其构造原理可知其最优点（x,t）分别逼近原问题的最小值点与最小值.一般对参数u的选取构造数列｛uk｝满足u1＞

2 算法

步1选择任意小正数,选定初值（x1,t1）∈Rn＋1,设置k：＝1取.

步2取uk＝10－k,建立罚函数,利用无约束优化求解其解记为（xk,tk）.

3 数值实验

为了检验算法的可操作性及有效性,利用Matlab R2013a,进行如下数据实验,取定为10－4.

例1

最优解和最优值分别为x＊＝（1,1）,f（x＊）＝2.初始点为（x1,t1）＝（1,5,1）.

kukxktkfuk1 0.1（1.000 0,1.000 0）2.020 4 2.257 8 2 0.01（1.000 0,1.000 0）2.005 5 2.073 7 3 0.001（1.000 0,1.000 0）2.016 5 2.037 6 4 0.000 1（1.000 0,1.000 0）2.000 1 2.006 8 5 0.000 01（1.000 0,1.000 0）2.010 1 2.012 3

4 总结

在本文中,针对带等式约束的极大极小问题,我们通过对简单精确罚函数的局部光滑处理,设计了一种新的既简单光滑而又精确度较高的罚函数.数值结果表明新的罚函数对解决带等式约束的极大极小问题是可行有效的.

［1］ZANG I.A smoothing out technique for minimax optimization［J］.Math Prog,1980,19：61－77

［2］李兴斯.一类不可微优化问题的有效解法［J］.中国科学,1994（4）：371－337

［3］FENG Ye.A smoothing trust－region Newton－CG method for minimax problem［J］.Applied Mathematics and Computation,2008,199：581－589

［4］ZHU S S,Fukushima M.Worst－case conditional value－at－risk With application to robust portfolio management［J］.Operations Research,2009,57（5）：1155－1168

［5］Gigola C,Gomez S.A regularization method for solving the finite convex min－max problems［J］.SIAM Journal on Numerical Analysis,1990,27：1621－1634［6］LI X S,PAN S.Solving the finite min－max problem via an exponential penalty method［J］.Comput Technol,2003,8：3－5

［7］POLAK E.ROYSET J O,WOMERSLEY R.S.Algorithms with adaptive smoothing for minimax problems［J］.Journal of Optimization Theory and Applications,2003,119（3）：459－484

A New Penalty Function for Solving Minimax Problem with Equality Constraints

WANG Fusheng,ZHANG Rui,GAO Juan,JIANG Hefeng
（Taiyuan Normal University,Jinzhong 030619,China）

By smoothing a classic simple and exact non smooth penalty function locally,and adjusting the penalty parameter and smooth parameter,a new simple smooth penalty function was introduced,which can transform a min－max problem with equality constraints into a unconstrained optimization problem.Preliminary numerical experiments showed that this penalty function method is feasible and effective.

min－max problem with equality constraints；smoothing；penalty function

1672－2027（2016）04－0023－03

O221.2

A

2016－06－08

王福胜（1963－）,男,山东荣成人,博士,太原师范学院数学系教授,主要从事最优化理论、算法及其应用.