求解一般D.C.规划的全局最优解

徐俊彦,苗 壮,刘庆怀

(长春工业大学 基础科学学院,长春 130012)

0 引言与预备知识

考虑优化问题:

(1)

其中：f(x),gi(x)(i=1,2,….m)：n→,并且有二阶连续偏导数.

通常用求解问题(1)的外逼近或分支定界算法求出一个不可行的解序列xk,使得xk→x*(k→∞),x*为最优解,而f(xk)→f*(k→∞),f*为最优值.但在实际应用中,算法必须在有限步内终止于某个xk,将xk作为x*的近似值,此时的xk可能是不可行的,甚至远离真正的最优解.为了克服这些问题,文献[1-7]提出了非孤立最优解的概念.本文将其推广到一般D.C.优化问题中.

引理1[8]二阶偏导数处处连续的函数是D.C.函数.

引理2[8]对于集合

M={(x,xn+1)∈n+1|di(x,xn+1)≤0(i=1,2,…,m)},

存在一个D.C.集:

F={(x,xn+1,xn+2)∈n+2|φ(x,xn+1,xn+2)≤0,ψ(x,xn+1,xn+2)≥0},

使得

(x,xn+1,xn+2)∈F⟺ (x,xn+1)∈M,

其中:di(x,xn+1)(i=1,2,…,m)为D.C.函数;φ(x,xn+1,xn+2)和ψ(x,xn+1,xn+2)是凸函数.

1 问题(1)的等价转化

由引理1可知,问题(1)中的函数是D.C.函数,该问题为一般D.C.规划.问题(1)等价于:

(2)

记

M={(x,xn+1)∈n+1|gi(x)≤0,f(x)-xn+1,i=1,2,…,m},

d(x,xn+1)=max{gi(x),f(x)-xn+1,i=1,2,…,m}.

根据D.C.函数的性质,d(x,xn+1)是D.C.函数.

设d(x,xn+1)=p(x,xn+1)-q(x,xn+1),p,q均为凸函数,则

M={(x,xn+1)∈n+1|d(x,xn+1)≤0}.

令

φ(x,xn+1,xn+2)=p(x,xn+1)-xn+2,ψ(x,xn+1,xn+2)=q(x,xn+1)-xn+2.

显然φ,ψ都是凸函数.

记

F={(x,xn+1,xn+2)∈n+2|φ(x,xn+1,xn+2)≤0,ψ(x,xn+1,xn+2)≥0},

(3)

则由引理2知,问题(2)等价于:

min{xn+1|(x,xn+1,xn+2)∈F},

(4)

其中F由式(3)定义.易见问题(4)是典范D.C.规划.

因此,求解问题(1)的最优解等价于求解一个典范D.C.规划的最优解.记D={(x,xn+1,xn+2)∈n+2|φ(x,xn+1,xn+2)≤0},则D为凸集.问题(4)可写为

min{xn+1|(x,xn+1,xn+2)∈D,ψ(x,xn+1,xn+2)≥0}.

(5)

2 主要结果

在实际应用中,孤立最优解是不可用的,因为孤立最优解极不稳定,当约束条件稍有扰动时,孤立最优解就可能是不可行的.因此非孤立最优解更有应用价值.

假设:

(H1)D={(x,xn+1,xn+2)∈n+2|φ(x,xn+1,xn+2)≤0}是紧集,并且intD≠Ø；

(H2) 存在满足ψ(a,an+1,an+2)<0和an+1

(H3)F=cl intF,其中F由式(3)定义;

(H4) {(x,xn+1,xn+2)∈D|xn+1≤γ}=cl{(x,xn+1,xn+2)∈intD|xn+1≤γ},γ∈;

(H5) 存在(ω,ωn+1,ωn+2)∈n+2,使得对任意的(x,xn+1,xn+2)∈D,有ωn+1-ε>xn+1成立.

如果(x,xn+1,xn+2)为问题(5)的可行解,存在点(x,xn+1,xn+2)的某个领域,使得在该领域内除点(x,xn+1,xn+2)外,其他点均为不可行的,则称点(x,xn+1,xn+2)为问题(5)的孤立可行解.若最优解在孤立可行解处得到,则称其为孤立最优解.

其中

s*=cl{(x,xn+1,xn+2)|(x,xn+1,xn+2)∈intD,ψ(x,xn+1,xn+2)>0},

设

{(x,xn+1,xn+2)∈n+2|(x,xn+1,xn+2)∈intD,ψ(x,xn+1,xn+2)>0}≠Ø.

对于给定的ε≥0,若

(x,xn+1,xn+2)∈{(x,xn+1,xn+2)∈n+2|(x,xn+1,xn+2)∈D,ψ(x,xn+1,xn+2)>ε},

则称问题(5)是正则的.

考虑如下辅助问题(p/γ):

max{ψ(x,xn+1,xn+2)|(x,xn+1,xn+2)∈D,xn+1≤γ,γ∈}.

由于函数ψ(x,xn+1,xn+2)连续,所以在条件(H4)成立时,问题(p/γ)是正则的.下面证明当条件(H4)成立时,求问题(5)的ε-非孤立最优解等价于求问题(p/γ)的最优解.

令min(问题(5))和max(p/γ)分别表示问题(5)和问题(p/γ)的最优值.

定理1设条件(H4) 成立.

{(x,xn+1,xn+2)∈n+2|(x,xn+1,xn+2)∈D,ψ(x,xn+1,xn+2)≥ε}=Ø.

因而,对使得ψ(x,xn+1,xn+2)>ε的每个(x,xn+1,xn+2)∈D,都有xn+1≥γ成立,即

(6)

{(x,xn+1,xn+2)∈n+2|(x,xn+1,xn+2)∈D,ψ(x,xn+1,xn+2)≥ε}=Ø,

即问题(5)没有ε-非孤立可行解.

3 算法及数值实例

算法1在假设(H1)～(H5)成立的条件下,算法步骤如下：

3) 计算

5) 若xn+1-γ=0,则令nk=(0,…,0,1,0)∈n+2；若则令

定理2算法1在有限步迭代后终止,或产生问题(5)的一个ε-非孤立最优解或证明问题(5)没有ε-非孤立可行解.

例1

其辅助问题(p/γ)为

当ε=0.000 1时,计算所得数值结果列于表1,其最优解为(6.000 1,0.764 0),最优值为-3.127 4.

表1 例1的计算结果Table 1 Computational results of example 1

例2

其辅助问题(p/γ)为

当ε=0.000 1时,计算所得数值结果列于表2,其最优解为(-0.988 6,3.100 1),最优值为57.325 7.

表2 例2的计算结果Table 2 Computational results of example 2

由表1和表2可见,算法1是有效的,收敛于非孤立全局最优解.

[1] Tuy H.Robust Solution of Non-convex Global Optimization Problems [J].J Glob Optim,2005,32(2):307-323.

[2] Tuy H.Polynomial Optimization:A Robust Approach [J].Pac J Optim,2005,1:357-374.

[3] Tuy H,Hoai Phuong.A Robust Algorithm for Quadratic Optimization under Quadratic Constraints [J].J Glob Optim,2007,37(4):557-569.

[4] SHEN Pei-ping,MA Yuan,CHEN Yong-qiang.A Robust Algorithm for Generalized Geometric Programming [J].J Glob Optim,2008,41(4):593-612.

[5] Tuy H.D(c)-Optimization and Robust Global Optimization [J].J Glob Optim,2010,47(3):485-501.

[6] SHEN Pei-ping,MA Yuan,CHEN Yong-qiang.Global Optimization for the Generalized Polynomial Sum of Ratios Problem [J].J Glob Optim,2011,50(3):439-455.

[7] Tuy H,Thach P T,Konno H.Optimization of Polynomial Fractional Functions [J].J Glob Optim,2004,29(1):19-44.

[8] Horst R,Pardalos P M,Thoai N M.Introduction to Global Optimization [M].Dordrecht:Kluwer Academic Publishers,2000.