带有多项式约束的广义分式规划问题的迭代算法

申培萍,班凤丽

(河南师范大学数学与信息科学学院,河南新乡453007)

1 引言

考虑如下一类带有多项式约束的广义分式规划问题

广义分式规划问题是一类非凸优化模型, 它包含比式和问题、多乘积问题、几何规划问题等. 近年来这类问题的特殊形式已经引起许多学者的关注. 一方面, (GFP) 问题通常存在多个非全局的局部最优解, 在计算方面有很大的挑战. 另一方面, (GFP) 能广泛应用于实际问题中, 如运输行业、政府合同、经济投资等[1–7]. 关于问题(GFP) 的特殊形式, 文献[8–11]中已给出不同的求解算法, 如分支定界算法、鲁棒算法等. 本文针对一般形式的(GFP) 问题提出一种迭代算法, 利用等价转化技巧与特殊不等式的有关性质将原问题压缩为几何规划问题, 通过求解一系列几何规划问题得到原问题的解, 并对算法进行理论分析, 通过数值算例表明提出的算法是可行有效的.

2 预备知识

为求解问题(GFP), 引入变量ηjt, ξjt, 记

其中T = T1+T2+···+Tp. 并令aj> 0, j = 1,··· ,p1; aj< 0, j = p1+1,··· ,p. 问题(GFP) 有如下等价形式

问题(GFP) 和问题(EGFP) 在如下意义下是等价的.

定理2.1如果(x∗,η∗,ξ∗)是问题(EGFP)的最优解,则x∗是问题(GFP)的最优解. 反之,如果x∗是问题(GFP)的最优解,那么(x∗,η∗,ξ∗)是问题(EGFP)的最优解,其中j =1,2,··· ,p; t=1,2,··· ,Tj.

证由问题(GFP) 和问题(EGFP) 的结构易得结论成立.

基于以上讨论, 为了获得问题(GFP) 的最优解, 可以转而求解其等价问题(EGFP). 令z =(x,η,ξ)∈RN(N =n+2T). 通过改变记号, 问题(EGFP) 可被重新写为如下形式

为了求解问题(EP), 下面将提出一种迭代算法, 该算法通过求解一系列的几何规划来获得问题(EP) 的最优解. 为此, 需要对问题(EP) 中的约束进行处理与变形, 当k ∈K 时, 根据的值将不等式约束分成如下两类

于是问题(EP) 可以写为如下形式

其中

下面为了求解问题(P1), 我们需要对问题(P1) 中k =0,k ∈Tk2所对应约束的右端项用近似单项式替换. 为此, 考虑如下函数

其中

接下来, 类似式(2.1)–(2.5) 的结果, 对于给定的点若k =0, 记

则有

若k ∈Tk2, 记

则有

因此问题(P1) 可被压缩为以下问题

3 算法及其收敛性

根据上述讨论, 问题(GFP) 等价于问题(P1). 给定点¯z, 利用算术– 几何平均不等式, 将问题(P1) 压缩为(P2(¯z)). 为了获得原问题(GFP) 的最优解, 这里提出一种迭代算法. 给定初始参数z0和误差ε. 令¯z =z0, 计算式(2.6), (2.8) 中的参数α0i,β0λki,σk, 可构造几何规划问题(P2(¯z)), 求解(P2(¯z)) 可获得新的点z1. 若≤ε 成立, 算法终止, z∗=z1即为问题(GFP) 的近似最优解. 否则, 令¯z =z1, 重复上述过程直到满足终止条件为止. 算法的具体步骤如下

步0给定容许误差ε>0, 选择初始点z0, 令迭代次数r =1.

步1令, 计算式(2.6), (2.8) 中的参数α0i,β0, λki,σk.

步2求解问题得最优解zr.

步3若≤ε, 算法终止. 令z∗= zr, 且z∗是问题(P1) 的最优解. 否则, 令r =r+1, 返回到步1.

算法的实际操作中, 若初始点为非可行点, 那么算法经过很少的迭代次数后就会产生问题(P2的可行点[12]. 因此, 当初始可行点未知时, 可以用非可行点代替.

下面为了讨论算法的收敛性, 先给出引理3.1.

引理3.1对于算法中产生的每一点zr(r ≥1) 均有

证由函数H(z),的定义以及代数平均不等式易得

进而由Gk(z),的表达式, 容易得出Gk(zr)=k =0,1,··· ,m1+2T.

当k =0 时, 对任意q =1,2,··· ,N +1, 有

当k ∈Tk1,k ∈Tk2时,可类似证明. 从而

定理3.2对于算法中产生的点zr(r ≥1), 假设问题(P2(zr)) 满足Slater’s 约束规范.如果算法有限步迭代, 则算法终止于问题(P1) 的KKT 点. 否则, 如果算法产生无穷序列{zr}, 则无穷序列{zr} 的聚点是问题(P1) 的KKT 点.

证若算法迭代r 步后终止. 由于问题(P2(zr)) 满足Slater’s 约束规范, 则问题(P2(zr−1)) 的最优解zr是它的KKT 点, 即有

其中λk,µk,νi是拉格朗日乘子, C = (−ν0,−ν1,··· ,−νN+1+1)T∈RN+1. 另外, 由算法中的第3 步, 有zr=zr−1. 因此

这意味着zr是问题(P1) 的KKT 点.

若算法是无限步迭代的, 易证序列{zr} 是有界的. 那么序列{zr} 存在一个收敛的子列.不失一般性, 仍记为序列{zr}, 并假设由和的连续可微性, 对式(3.1)–(3.4) 两边取极限, 可得

再结合引理3.1 和式(3.5)–(3.8), 有

因此z∗是问题(P1) 的KKT 点. 定理得证.

4 数值实验

为验证算法的有效性, 在酷睿双核CPU (主频2.4 GHz), 2GB 内存的微机上用Matlab进行数值计算. 表1 的数值结果表明本文算法是可行有效的.

例1

例2

例3

表1: 例1–4 的数值计算结果

例4

由表1 可知, 本文算法的运行时间及迭代次数较文献[11, 13] 都有明显改善, 结果表明提出的算法是可行有效的.

5 结论

本文针对一类带有多项式约束的广义分式规划问题提出相应的迭代算法, 利用等价转化技巧与特殊不等式的有关性质将原问题的求解过程转为一系列几何规划问题的求解, 数值结果表明提出的算法是可行有效的. 另外, 本文考虑的问题模型中要求fjt(x),gjt(x) 为正的仿射函数, 但是本文算法针对更一般的模型也可以进行求解.