求解具有非精确信息的非光滑凸半无限规划束方法

吴 奇，田 琦，庞 丽 萍

(大连理工大学 数学科学学院,辽宁 大连 116024 )

0 引 言

半无限规划是指具有有限数量的决策变量和无限数量的约束的数学规划，其在数学、经济学和工程学等领域都有着广泛的应用．给定一点，检查它的可行性需要检查无数个约束，或者等价地求解一个全局优化问题，并且伴随着迭代不断进行，全局优化问题逐渐发生变化．目前求解半无限规划问题的数值方法主要有离散化方法、交换集方法、下降方法和牛顿型方法等[1-4]．然而，所有的这些方法都需要计算目标函数和约束函数的梯度，因此无法应用到函数是非光滑的情况．除此之外，Fuduli等考虑了用非光滑方法求解光滑半无限极小极大问题，他们允许通过隐式方法得到内部最大问题的非精确解[5]．Pang等研究了非光滑半无限规划的数值方法[6-8]，他们利用非精确方法和离散化方法将半无限规划问题转化为一系列有限约束优化问题并通过束方法进行求解．

对于一些问题，函数值可能无法精确计算或者精确计算的代价太大，如无导数优化、大规模拉格朗日或半定松弛以及随机模拟，这种情况往往只能得到非精确信息(或者称为受噪声污染的信息)．对于采用非精确信息的非光滑优化问题，已有不少研究成果．Kiwiel提出了一种束方法可以处理函数和次梯度值是非精确的问题，其中设置噪声是渐近消失的[9]．束方法中，Hintermüller首次考虑了不消失型扰动，文中只有次梯度值是非精确的，而函数值必须是精确的[10]．Solodov考虑函数与次梯度都是非精确的并且不会渐近消失的[11]．van Ackooij等提出了一种方法求解基于非精确信息的非光滑带约束问题[12]．de Oliveira等给出了凸情况下非精确束方法的统一理论，概括了已经存在的多种处理噪声的束方法[13]．Hare等提出了一种束方法求解基于非精确信息的非光滑非凸无约束优化问题[14]．

本文考虑如下半无限规划问题：

s.t.g(x，ω)≤0；∀ω∈Ω

考虑下水平问题：

当采用非精确方法求解下水平问题的非精确解时，原始问题(1)可以转化为一个基于非精确信息的非光滑有限约束问题．值得注意的是，当约束函数g关于ω是非凸的情况，下水平问题的求解是困难的，并且每进行一次迭代就需要一次非精确全局优化．

本文主要研究具有非精确信息的非光滑凸半无限问题的数值解法．对于下水平问题，本文将采用离散化方法将下水平问题进行近似．具体地，通过选择集合Ω的有限子集对其进行替换，将原始非光滑半无限规划问题转化为一系列非光滑有限约束规划问题．在迭代过程中，约束函数是不断发生变化的．

1 算 法

令k为当前迭代指标，xk表示当前迭代点(或称为稳定中心)．此外，迭代过程中还将产生一系列试探点{yj}j∈Jk，Jk⊂{0，1，…，k}．并且有xk∈{yj}j∈Jk．因此存在一个指标ck=j，j∈Jk使得xk=yj．定义Ωk={ωq|q=1，2，…，Qk}⊂Ω，为Ω的一个细分．

定义Ω与Ωk之间的Hausdorff距离如下：

其中

(1)

ρk、σk满足如下条件：

(2)

因此可以定义近似割平面模型如下：

(3)

其中

(4)

接下来求解二次规划问题：

下面介绍问题(2)解的特征：

(5)

其中IX表示集合X的指示函数，∂IX(yk+1)等于X在点yk+1处的法锥．令

(6)

(7)

为了刻画求解问题(1)的进度，本文采用了如下的预测下降量：

(8)

其中αk∈[0，2]．根据式(6)和(8)可以得到

(9)

则认为由不精确信息引入的噪声太大．为了数值上的通用性，本文考虑更一般的噪声测量准则：

(10)

其中βk∈(-1，1-αk-B]，B>0．当上述关系成立时，噪声被认为太大，此时需要执行噪声衰减：保持稳定中心和近似割平面模型不变，减小迫近参数μk．

对于模型(3)，除了要检查噪声是否可以接受，还需要对Ωk进行选取．Ωk的选取对算法的计算效率影响较大．Ωk中包含元素过多会导致计算约束函数时付出的时间代价大．反过来，当Ωk中包含元素过少，尽管计算约束函数的时间代价小，但是会导致模型与原问题偏差较大，也就是说计算的解的可行性牺牲很大．当细分发生变化时，约束函数会发生变化，因此要较少地更新细分．本文引入如下准则来确定是否执行噪声衰减步或者细化步(更新细分)．

(11)

(12)

(13)

注意，条件(11)等价于不等式(10)，用于判断当前迭代噪声是否可以接受．通过选择参数αk、βk可以更灵活地控制噪声衰减．条件(12)和(13)用于控制细分的更新并以此降低计算约束函数的时间代价．

如果Ωk需要细化，选择新的Ωk+1满足如下条件：

Ωk+1⊃Ωk，Dk+1

(14)

当噪声被宣布为可接受的并且当前细分不需要被细化时，需要判断最新产生的试探点是否足够好，即是否可以成为下一个稳定中心．下面给出下降条件：

(15)

当上述关系成立时，该迭代被宣布为下降步，稳定中心转移到新的试探点：xk+1=yk+1．否则，该迭代被声明为空步，稳定中心不发生变化：xk+1=xk，新的试探点信息被加入近似割平面模型中用来丰富模型．注意到，当gk，ck>0时，若式(15)成立，则有gk，k+1-gk，ck≤-mδk．当gk，ck≤0时，若式(15)成立，则有fk+1-fck≤-mδk．由此可以看出，下降条件(15)背后的基本原理是通过以下两种方式之一来衡量实现问题(1)最小化的进展：

①稳定中心可行的情况，重点放在降低目标值而又不降低稳定中心的可行性；

②稳定中心不可行的情况，重点放在降低稳定中心的不可行性．

下面给出求解问题(1)的具体算法．

算法1

步骤2(1)如果条件(11)和(12)成立，选择μk+1∈(0，μk)并转步骤3．

(2)条件(11)不成立．如果δk≤γ2，停止迭代．否则，转步骤5．

步骤6置xk+1=xk，ρk+1=ρk，σk+1=σk，Jk+1=Jk，ck+1=ck．置k=k+1并转步骤1．

当迭代k+1是空步时，即xk+1=xk，根据步骤5(2)可以得到

2 收敛性结果

假设2[8]假设Slater约束规范成立，即存在x∈X，使得g(x，ω)<0，∀ω∈Ω成立．

命题1[12]在假设1下，存在常数M，M′>0，使得

现在分析算法1无限循环时出现的不同情况：

(1)无限多次细化迭代(步骤3中Ωk+1更新发生无限多次)．

(2)有限数量细化迭代．在这种情况下，又可以具体分成下列两种情况：

①无限多次下降迭代(步骤5(1)执行了无限多次)．

②有限数量迭代后稳定中心保持不变．在这种情况下，又可以具体分成下列两种情况：

a.无限多次噪声衰减(步骤2(2)执行了无限多次)．

b.有限数量噪声衰减后，最终仅执行空步．

上述情况是互斥的，即只有其中一种情况会发生．首先考虑有限数量细化迭代发生的情况．

证明由文献[12]中的引理3.1易证明Ξk+vk→0，δk→0，当K1k→∞．证明第2个结论采用反证法．假设由算法1步骤3可得对任意的k>因为是最后一步细化步，对任意的k∈K1，都有这与δk→0，k∈K1相矛盾，因此有

证明由文献[12]中的引理3.2易证明Ξk+vk→0，Ek<0，当K2k→∞．证明第2个结论采用反证法．假设由算法1步骤3可得对任意的k>因为是最后一步细化步，对任意的k∈K2，都有这与Ξk+vk→0，k∈K2相矛盾，因此有

证明由文献[12]中的引理3．3易证明Ξk+vk→0，δk→0，当K3k→∞．第2个结论可以用与证明引理1相同的方法得到．

根据文献[8]中的引理8，可以得到如下引理．

定理1令假设1和2成立，假设算法1产生无限多循环，如果存在无穷指标集K使得

此外，如果K⊆K4，则有

〈Ξk+vk，xk-y〉

3 数值算例

表1 数值结果Tab.1 Numerical results

图1 不同噪声结果比较Fig.1 Comparison of results of different noise

例1考虑如下算例[15]：

s.t.(1+ω2)2-x1-x2ω-x3ω2-x4ω3≤0；

∀ω∈[0，1]

其中

11x3-3x4-80

21x3-3x4-100

例2考虑如下算例[8]：

s.t.x1+x2ex3ω-e2x1ω+sin(4ω)≤0；

∀ω∈[0，1]

例3考虑如下算例[16]：

s.t.|φT(ω)x-1|≤0.057 5；∀ω∈[0，0.05]

|φT(ω)x|≤0.01；∀ω∈[0.1，0.5]

其中

φ(ω)=(2cos(2×17πω)… 2cos(2πω)1)T

4 结 语

本文提出一种离散化束方法，来求解具有非精确信息的非光滑凸半无限规划问题．在目标函数只能获取非精确信息的情况下，通过选择带参数型的改进函数，证明了在适当条件下迭代点的任何聚点对于原始问题都是可行的．通过与算法2、3进行比较，可以得到算法1在求解半无限规划问题时更加有效且稳定．此外数值实验也表明，算法1在求解具有不同类型噪声的凸半无限规划问题时具有有效性．