浅谈常用约束优化问题的几种算法及数学实验

摘要:约束优化问题是生产实际中的常见问题,本文列举了常用约束优化问题的几种算法,同时对它们的特点进行了总结,并通过MATLAB软件对算法进行实现。

关键词:最优化 约束 算法

1 数学模型

一般的约束最优化问题,其数学模型为

中,找到一个可行点X*,使目标函数f(X)取得最小值。此时称X*,f(X*)为问题(1)的最优解。

2 常用约束优化算法简介

2.1 外点罚函数法

基本思想:对违反约束条件的点在目标函数中加入相应的“惩罚”,而对可行域内的点不予惩罚。其迭代点一般在可行域外部移动,随着一个无约束问题的求解转移到另一个无约束问题的求解,惩罚次数逐渐加大,从而迫使迭代点向可行域靠近。具体过程如下:

对问题(1),构造一个函数为

Mk>0是一个逐渐增大的参数,称为惩罚因子。F(X,Mk)称为问题(1)的增广目标函数。

显然,F(X,Mk)是定义在Rn上的一个无约束函数,由增广目标函数F(X,Mk)的构造可知,如果已经求出F(X,Mk)的最优解为XMk,则判断 是否属于D。

(1) 如果XMk∈D,则XMk是问题(1)的最优解;

(2) 如果XMk∈/D,则XMk不是问题(1)的最优解。此时说明原来的罚因子给小了,需要加大罚因子,使得Mk+1>Mk,然后再重新计算F(X,Mk)的最优解。

事实上,随着罚因子Mk的增大,迫使惩罚项的值逐渐减小,从而使的F(X,Mk)极小点X*(Mk)沿着某一轨迹逐渐接近于可行域D上的最优点X*。当Mk趋于无穷大时,F(X,Mk)的极小点就是原问题(1)的最优点X*。

2.2 内点罚函数法

基本思想:对企图从可行域内部穿越可行域的点,在目标函数中加入相应的“障碍”,距边界越近,障碍越大,在边界上给以无穷大的障碍,从而保证迭代点一直在可行域内部移动。具体过程如下:

对于问题

其实质是在可行域D1的边界上设置一道障碍,从D1中的某一点Xo出发进行迭代,当迭代点靠近D1的边界时,便被此边界上的障碍碰回,此时即便rk很小,但使得F(X,rk)的函数值变得很大,容易想象不可能在靠近D1的边界上取得最优解,于是迫使迭代点被碰回到远离区域D1的边界去寻找。因为F(X,rk)和F(X)都在D1中,rk取得很小时,在可行域内部距离边界较远的地方,有F(X,rk)≈F(X),此时F(X,rk)的解可以作为f(X)的近似解。但当rk取得过小,将给障碍函数的极小化计算带来很大的困难,因此,取一个严格单调递减且大于零的障碍因子序列{rk},用式子表示为r1>r2>...rv>...>0,当rk逐渐减小时,有

初始点Xo应选为满足不等式约束条件的点,罚因子rk按照内点罚函数法确定,且rk0时,

2.4 复合形法

基本思想:在可行域内产生一个由K(n+2

考虑问题

(6)

在可行域内随机选取K个可行点,X1,X2..XK。计算除去最坏点XH外其余(k-1)个顶点的几何中心点 ,即

若约束可行域为凸集时,Xo一定为可行点;若约束可行域为非凸集时,则应检测Xo是否为可行点。然后以Xo点为轴心求最坏点XH的映射点XR,即

其中t为映射系数;接着检查映射点XR是否在可行域内,且其目标函数值f(XR)是否比最坏点的目标函数值f(XH)小,如果这两个条件都得到满足,则以XR点代替最坏点XH并与其余(k-1)个点重新构成新的复合形法。然后重复进行上述工作,直到满足收敛条件。如果上述两个条件至少有一个不满足,则通过缩减映射系数 的方法,使其最终满足这两个条件。

3 数学实验

利用MATLAB中的优化算法工具箱中的函数,以外点罚函数法、内点罚函数法和混合罚函数法为实例进行数学实验,通过迭代可以方便、快捷的求得满足约束条件的最优解。

1 用外点罚函数法编程实现

2 用内点罚函数法编程实现

3 用混合罚函数法编程实现

4 结论

本文对常用约束优化问题的几种算法的基本思想进行了描述,并分别对它们的特点进行了细致的总结,突出了各种算法的适用性,并利用MATLAB进行数学实验,结果表明在给定的条件范围内,可以得到原优化问题的最优解。

参考文献

[1]郭科, 陈聆等.最优化方法及其应用[M].北京:高等教育出版社,2007.

[2]何坚勇.最优化方法[M].北京:清华大学出版社,2007.

作者简介:张守业 黑龙江省海伦人(1984--)在读硕士研究生 专业:计算数学,在读硕士研究生 专业:计算数学