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

$ {\rm{(GFP)}:}\left\{ \begin{array}{llll} \rm{min} & \varphi_0(x) = \sum\limits_{j = 1}^{p}a_j\prod\limits_{t = 1}^{T_j}(\frac{f_{jt}(x)}{g_{jt}(x)})^{\mu_{jt}} = \sum\limits_{j = 1}^{p}a_j\prod\limits_{t = 1}^{T_j}(\frac{\sum\limits_{i = 1}^{n}a_{jti}^{1}x_i+\alpha_{jt}^{1}}{\sum\limits_{i = 1}^{n}a_{jti}^{2}x_i+\alpha_{jt}^{2}})^{\mu_{jt}}, \\ \rm{s.t. }& \varphi_{k}(x) = \sum\limits_{t = 1}^{{T}_{k}^{1}}{b}_{kt}^{1}\prod\limits_{i = 1}^{n}x_{i}^{{\gamma}_{kti}^{1}}\leq 0, \quad k = 1, 2, \cdots, m_{1}, \\ & x\in X = \{x|0<\underline{x}_{i}\leq x_{i}\leq \overline{x}_{i}<\infty, \ i = 1, \cdots, n\}, \\ \end{array} \right. $

其中$ {a}_{j}, $ $ {b}_{kt}^{1}, {\gamma}_{kti}^{1}, $为任意实数, $ \mu_{jt} $为正实数, 且$ f_{jt}(x), g_{jt}(x) $在$ x\in X $上为正的仿射函数.

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

为求解问题(GFP), 引入变量$ \eta_{jt}, \ \xi_{jt} $, 记

$ \eta = (\eta_{11}, \eta_{12}, \cdots, \eta_{1T_1}, \eta_{21}, \cdots, \eta_{pT_{p}})\in R^{T}, \; \; \xi = (\xi_{11}, \xi_{12}, \cdots, \xi_{1T_1}, \xi_{21}, \cdots, \xi_{pT_{p}})\in R^{T}, $

其中$ T = T_1+T_2+\cdots+T_p. $并令$ {a}_{j}>0, \ j = 1, \cdots, p_1;\ \ $$ {a}_{j}<0, \ j = p_1+1, \cdots, p. $问题(GFP)有如下等价形式

$ {\rm{(EGFP)}:}\left\{ \begin{array}{lll} \rm{min} & \sum\limits_{j = 1}^{p_1}{a}_{j}\prod\limits_{t = 1}^{T_j} (\frac{\eta_{jt}}{\xi_{jt}})^{\mu_{jt}}+ \sum\limits_{j = p_1+1}^{p}{a}_{j}\prod\limits_{t = 1}^{T_j} (\frac{\eta_{jt}}{\xi_{jt}})^{\mu_{jt}}, \\ \rm{s.t. } & f_{jt}(x)\leq \eta_{jt}, \ \ \xi_{jt}\leq g_{jt}(x), \quad j = 1, \cdots, p_1;\ t = 1, \cdots, T_{j}, \\ & \eta_{jt}\leq f_{jt}(x), \ \ g_{jt}(x)\leq \xi_{jt}, \quad j = p_1+1, \cdots, p;\ t = 1, \cdots, T_{j}, \\ & \varphi_{k}(x)\leq 0, \quad k = 1, \cdots, m_{1}, \ \ x\in X, \\ & \eta_{jt}>0, \ \ xi_{jt}>0, \quad j = 1, \cdots, p;\ t = 1, \cdots, T_{j}. \end{array} \right. $

问题(GFP)和问题$ {\rm{(EGFP)}} $在如下意义下是等价的.

定理2.1  如果$ (x^{\ast}, \eta^{\ast}, \xi^{\ast}) $是问题(EGFP)的最优解, 则$ x^{\ast} $是问题(GFP)的最优解.反之, 如果$ x^{\ast} $是问题(GFP)的最优解, 那么$ (x^{\ast}, \eta^{\ast}, \xi^{\ast}) $是问题(EGFP)的最优解, 其中$ \eta^{\ast}_{jt} = f_{jt}(x^{\ast}), $ $ \xi^{\ast}_{jt} = g_{jt}(x^{\ast}), $ $ j = 1, 2, \cdots, p;\ t = 1, 2, \cdots, T_{j} $.

证  由问题(GFP)和问题$ {\rm{(EGFP)}} $的结构易得结论成立.

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

$ {\rm{(P)}:}\left\{ \begin{array}{llll} \rm{min} & h_{0}^{+}(z)-h_{0}^{-}(z), \\ \rm{s.t. }& h_{k}^{+}(z)-h_{k}^{-}(z)\leq 0, \quad k = 1, \cdots, m_{1}+2T, \ \ z_{i}>0, \quad i = 1, \cdots, N, \end{array} \right. $

其中$ h_{k}^{+}(z) = \sum\limits_{j = 1}^{ T_{k}^{+}}\alpha_{kj}^{1}\prod\limits_{i = 1}^{N}z_{i}^{\beta_{kji}^{1}} $, $ h_{k}^{-}(z) = \sum\limits_{j = 1}^{ T_{k}^{-}}\alpha_{kj}^{2}\prod\limits_{i = 1}^{N}z_{i}^{\beta_{kji}^{2}} $, 且$ \alpha_{kj}^{1}, \alpha_{kj}^{2} \in R^{+}, $ $ \beta_{kji}^{1}, \beta_{kji}^{2}, \in R $, $ k = 0, 1, \cdots, m_{1}+2T $.

对问题(P), 通过选取充分大的正数$ M $, 使其满足$ h_{0}^{+}(z)-h_{0}^{-}(z)+M>0. $于是引入变量$ z_{N+1} $, 并记$ K = \{{1, \cdots, m_{1}+2T}\}, $问题(P)能够等价转化为如下问题

$ \begin{eqnarray*} \mbox{ (EP)}: \left\{\begin{array}{ll} \min&z_{N+1}, \\ {\rm{s.t.}}&h_{0}^{+}(z)+M\leq h_{0}^{-}(z)+z_{N+1}, \quad k = 0, \ \ h_{k}^{+}(z)\leq h_{k}^{-}(z), \quad k\in K, \\ &z_{i}>0, \quad i = 1, \cdots, N+1.\nonumber \end{array} \right. \end{eqnarray*} $

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

$ \begin{eqnarray*} T_{k1} = \{k|T_k^{-} = 1, k\in K \}, \quad T_{k2} = \{k|T_k^{-}>1, k\in K \}. \end{eqnarray*} $

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

$ \begin{eqnarray*} {\rm{(P1)}:}\left\{ \begin{array}{lll} \rm{min} &z_{N+1}, \\ \rm{s.t. }&G_{k}(z)\leq 1, \ \ \ k\in {\{0\}}\cup T_{k1}\cup T_{k2}, \ \ z_{i}>0, \ \ i = 1, \cdots, N+1, \nonumber \end{array} \right. \end{eqnarray*} $

其中

$ {{G}_{k}(z) = }\left\{ \begin{array}{ll} &\frac{h_{0}^{+}(z)+M}{h_{0}^{-}(z)+z_{N+1}}, \ k = 0, \\ &\frac{h_{k}^{+}(z)}{h_{k}^{-}(z)}, \ k\in T_{k1}, \\ &\frac{h_{k}^{+}(z)}{h_{k}^{-}(z)}, \ k\in T_{k2}. \end{array} \right. $

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

$ \begin{eqnarray} &H(z) = \sum\limits_{j = 1}^{m}b_{j}\prod\limits_{i = 1}^{N+1}z_{i}^{a_{ji}}. \end{eqnarray} $

(2.1)

给定点$ \bar{z}\in R^{N+1}_{+} $, 由代数–几何平均不等式有

$ \begin{eqnarray} H(z)\geq \hat{H}(z;\bar{z})& = &\prod\limits_{j = 1}^{m}\left (\frac{b_j}{\theta_j(\bar{z})}\prod\limits_{i = 1}^{N+1}z_{i}^{a_{ji}}\right )^{\theta_j(\bar{z})}, \end{eqnarray} $

(2.2)

其中参数$ \theta_{j}(\bar{z}) $可通过下式得到

$ \begin{eqnarray} \theta_{j}(\bar{z}) = \frac{b_{j}\prod\limits_{i = 1}^{N+1}\bar{z_{i}}^{a_{ji}}}{H(\bar{z})}, \quad j = 1, 2, \cdots, m. \end{eqnarray} $

(2.3)

将参数$ \theta_{j}(\bar{z}) $代入(2.2)式得

$ \begin{eqnarray} H(z)\geq \hat{H}(z;\bar{z})& = &{\beta\prod\limits_{i = 1}^{N+1}\bar{z_{i}}^{\alpha_{i}}}, \end{eqnarray} $

(2.4)

其中

$ \begin{eqnarray} \alpha_{i} = \frac{\sum\limits_{j = 1}^{m}a_{ji}b_{j}\prod\limits_{i = 1}^{N+1}\bar{z_{i}}^{a_{ji}}}{H(\bar{z})}, \ \ \ \beta = \frac{H(\bar{z})}{\prod\limits_{i = 1}^{N+1}\bar{z_{i}}^{\alpha_{i}}}. \end{eqnarray} $

(2.5)

接下来, 类似式(2.1)–(2.5)的结果, 对于给定的点$ \bar{z}\in R^{N+1}_{+} $, 若$ k = 0 $, 记

$ \begin{eqnarray} &&{\alpha}_{0i} = \frac{\sum\limits_{j = 1}^{T_0^{-}}{{\beta}_{0ji}^{2}}{{\alpha}_{0j}^{2}}\prod\limits_{i = 1}^{N}\bar{z_{i}}^{{\beta}_{0ji}^{2}}}{\sum\limits_{j = 1}^{T_0^{-}}{{\alpha}_{0j}^{2}}\prod\limits_{i = 1}^{N}\bar{z_{i}}^{{\beta}_{0ji}^{2}}+z_{N+1}}, \ \ \ \ {\beta}_0 = \frac{\sum\limits_{j = 1}^{T_0^{-}}{{\alpha}_{0j}^{2}}\prod\limits_{i = 1}^{N}\bar{z_{i}}^{{\beta}_{0ji}^{2}}+z_{N+1}}{\prod\limits_{i = 1}^{N}\bar{z_{i}}^{{\alpha}_{0i}(\bar{z})}}, \end{eqnarray} $

(2.6)

则有

$ \begin{eqnarray} {h_{0}^{-}(z)+z_{N+1}} = \sum\limits_{j = 1}^{T_0^{-}}{{\alpha}_{0j}^{2}}\prod\limits_{i = 1}^{N}{z_{i}}^{{\beta}_{0ji}^{2}}+z_{N+1}\geq {{\beta}_{0}\prod\limits_{i = 1}^{N}{z_{i}}^{\alpha_{0i}}}&\triangleq&{B}_{0}(z;\bar{z}). \end{eqnarray} $

(2.7)

若$ k\in T_{k2} $, 记

$ \begin{eqnarray} &&{\lambda}_{ki} = \frac{\sum\limits_{j = 1}^{T_k^{-}}{{\beta}_{kji}^{2}}{{\alpha}_{kj}^{2}}\prod\limits_{i = 1}^{N}\bar{z_{i}}^{{\beta}_{kji}^{2}}}{\sum\limits_{j = 1}^{ T_{k}^{-}}\alpha_{kj}^{2}\prod\limits_{i = 1}^{N}z_{i}^{\beta_{kji}^{2}}}, \ \ \ {\sigma}_k = \frac{\sum\limits_{j = 1}^{ T_{k}^{-}}\alpha_{kj}^{2}\prod\limits_{i = 1}^{N}z_{i}^{\beta_{kji}^{2}}}{\prod\limits_{i = 1}^{N}\bar{z_{i}}^{{\lambda}_{ki}(\bar{z})}}, \end{eqnarray} $

(2.8)

则有

$ \begin{eqnarray} {h_{k}^{-}(z)} = \sum\limits_{j = 1}^{ T_{k}^{-}}\alpha_{kj}^{2}\prod\limits_{i = 1}^{N}z_{i}^{\beta_{kji}^{2}}\geq {{\sigma}_{k}\prod\limits_{i = 1}^{N}{z_{i}}^{\lambda_{ki}}}&\triangleq&{B}_{k}(z;\bar{z}). \end{eqnarray} $

(2.9)

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

$ \begin{eqnarray*} {{({\rm{P}}2(\bar{z}))}:}\left\{ \begin{array}{lll} \rm{min} &z_{N+1}, \\ \rm{s.t. }&\hat{G}_{k}(z;\bar{z})\leq 1, \ \ \ k\in {\{0\}}\cup T_{k2}, \\ &\hat{G}_{k}(z)\leq 1, \ \ \ k\in T_{k1}, \ \ z_{i}>0, \ \ i = 1, \cdots, N+1, \nonumber \end{array} \right. \end{eqnarray*} $

其中$ {\hat{G}_{k}(z;\bar{z}) = }\left\{ \begin{array}{llll} & \frac{h_{0}^{+}(z)+M}{{B}_{0}(z;\bar{z})}, \ k = 0, \\ &\frac{h_{k}^{+}(z)}{{B}_{k}^{-}(z;\bar{z})}, \ k\in T_{k2}, \\ \end{array} \right. $ $ \hat{G}_{k}(z) = \frac{h_{k}^{+}(z)}{h_{k}^{-}(z)}, \ k\in T_{k1}. $此时, 问题(P2($ \bar{z} $))为几何规划问题, 能够通过指数变换, 即$ z_i = \exp(t_i), i = 1, \cdots, N+1 $, 将其等价转化为关于变量$ t $的凸规划问题.实际计算时, 可调用Matlab工具箱中的GGP求解器直接问题(P2($ \bar{z} $))进行求解.

根据问题(P1)和(P2($ \bar{z} $)), 任给点$ \bar{z}\in R^{N+1} $, 对$ G_{k}(z) $与$ \hat{G}_{k}(z;\bar{z}) $, 满足$ G_{k}(z)\geq \hat{G}_{k}(z;\bar{z}) $, 及$ G_{k}(\bar{z}) = \hat{G}_{k}(\bar{z};\bar{z}). $这样问题(P1)的可行域$ X $包含问题(P2($ \bar{z} $))的可行域$ Y $, 即$ Y\subseteq X $, 且通过选取$ \bar{z}\in R^{N+1} $, 问题(P2($ \bar{z} $))可以作为问题(P1)的近似.因此, 依靠选取不同点$ \bar{z} $, 可以构造一系列的(P2($ \bar{z} $)), 通过求解(P2($ \bar{z} $)), 进而得到(P1)的解.根据定理2.1, 得原问题的解.

根据上述讨论, 问题(GFP)等价于问题(P1).给定点$ \bar{z} $, 利用算术–几何平均不等式, 将问题(P1)压缩为(P2($ \bar{z} $)).为了获得原问题(GFP)的最优解, 这里提出一种迭代算法.给定初始参数$ {z^0} $和误差$ \varepsilon $.令$ \bar{z} = z^0 $, 计算式(2.6), (2.8)中的参数$ {\alpha}_{0i}, {\beta}_0 $ $ {\lambda}_{ki}, {\sigma}_k $, 可构造几何规划问题(P2($ \bar{z} $)), 求解(P2($ \bar{z} $))可获得新的点$ {z^1} $.若$ \|z^1-z^0\|\leq\varepsilon $成立, 算法终止, $ z^{\ast} = z^1 $即为问题(GFP)的近似最优解.否则, 令$ \bar{z} = z^{1} $, 重复上述过程直到满足终止条件为止.算法的具体步骤如下

步0 给定容许误差$ \varepsilon> 0 $, 选择初始点$ {z^{0}} $, 令迭代次数$ r = 1 $.

步1 令$ \bar{z} = z^{r-1} $, 计算式(2.6), (2.8)中的参数$ {\alpha}_{0i}, \beta_0, $ $ {\lambda}_{ki}, {\sigma}_k $.

步2 求解问题(P2($ \bar{z} $)), 得最优解$ {z^{r}} $.

步3 若$ \|z^{r}-z^{r-1}\|\leq \varepsilon $, 算法终止.令$ z^{\ast} = z^r $, 且$ z^{\ast} $是问题(P1)的最优解.否则, 令$ r = r+1, $返回到步1.

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

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

引理3.1  对于算法中产生的每一点$ {z^{r}}\; (r\geq1) $均有

$ G_{k}(z^{r}) = \hat{G}_{k}(z^{r};z^{r}), \ \ \ \nabla G_{k}(z^{r}) = \nabla \hat{G}_{k}(z^{r};z^{r}), \ k = 0, 1, \cdots, m_{1}+2T, $

其中$ \bigtriangledown $代表函数的梯度.

证  由函数$ {H}(z), \hat{H}(z;\bar{z}) $的定义以及代数平均不等式易得

$ h_{0}^{-}(z^{r})+z_{N+1}^{r} = {B}_{0}(z^{r};z^{r}), \ \ \ \nabla\left(h_{0}^{-}(z^{r})+z_{N+1}^{r}\right) = \nabla{B}_{0}(z^{r};z^{r}), $

进而由$ {G}_{k}(z), \hat{G}_{k}(z;\bar{z}) $的表达式, 容易得出$ G_{k}(z^{r}) = \hat{G}_{k}(z^{r};z^{r}), \ k = 0, 1, \cdots, m_{1}+2T. $

当$ k = 0 $时, 对任意$ q = 1, 2, \cdots, N+1 $, 有

$ \begin{eqnarray*} &&\dfrac{\partial G_{k}(z^{r})}{\partial z_{q}} = \frac{\dfrac{\partial (h_{0}^{+}(z^{r})+M)}{\partial z_{q}}(h_{0}^{-}(z^{r})+z_{N+1}^{r})-(h_{0}^{+}(z^{r})+M)\dfrac{\partial (h_{0}^{-}(z^{r})+z_{N+1}^{r})}{\partial z_{q}}}{[h_{0}^{-}(z^{r})+z_{N+1}^{r}]^{2}}, \\ &&\dfrac{\partial \hat{G}_{k}(z^{r};z^{r})}{\partial z_{q}} = \frac{\dfrac{\partial (h_{0}^{+}(z^{r})+M)}{\partial z_{q}}{B}_{0}(z^{r};z^{r})-(h_{0}^{+}(z^{r})+M)\dfrac{\partial {B}_{0}(z^{r};z^{r})}{\partial z_{q}}}{[{B}_{0}(z^{r};z^{r})]^{2}}. \end{eqnarray*} $

又因为$ h_{0}^{-}(z^{r})+z_{N+1}^{r} = {B}_{0}(z^{r};z^{r}), \ \ \ \nabla\left(h_{0}^{-}(z^{r})+z_{N+1}^{r}\right) = \nabla{B}_{0}(z^{r};z^{r}). $因此$ \dfrac{\partial G_{k}(z^{r})}{\partial z_{q}} = \dfrac{\partial \hat{G}_{k}(z^{r};z^{r})}{\partial z_{q}}, $即$ \nabla G_{k}(z^{r}) = \nabla \hat{G}_{k}(z^{r};z^{r}), \ \ k = 0. $

当$ k\in T_{k1}, k\in T_{k2} $时, 可类似证明.从而$ \nabla G_{k}(z^{r}) = \nabla \hat{G}_{k}(z^{r};z^{r}), \ k = 0, 1, \cdots, m_{1}+2T. $

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

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

$ \begin{eqnarray} &&\sum\limits_{k\in{\{0\}}\cup T_{k2}}{\lambda}_k{\nabla}\left(\hat{G}_k(z^{r};z^{r-1})\right)+ \sum\limits_{k\in T_{k1}}{\mu}_{k}{\nabla}\left(\hat{G}_k(z^{r})\right)+C = 0, \end{eqnarray} $

(3.1)

$ \begin{eqnarray} &&\hat{G}_{k}(z^{r};z^{r-1})\leq 1, \ \ \ \lambda_{k}\geq 0, \ \ \ {\lambda_{k}}\left(\hat{G}_k(z^{r};z^{r-1})-1\right) = 0, \quad k\in{\{0\}}\cup T_{k2}, \end{eqnarray} $

(3.2)

$ \begin{eqnarray} &&\hat{G}_{k}(z^{r})\leq 1, \ \ \ \mu_{k}\geq 0, \ \ \ {\mu}_{k}\left(\hat{G}_k(z^{r})-1\right) = 0, \quad k\in T_{k1}, \end{eqnarray} $

(3.3)

$ \begin{eqnarray} &&-z^{r}_{i}\leq 0, \ \ \ \nu_{i}\geq 0, \ \ \ \nu_{i}\left(-z^{r}_{i}\right) = 0, \quad i = 1, \cdots, N+1, \end{eqnarray} $

(3.4)

其中$ {\lambda}_k, {\mu}_{k}, \nu_{i} $是拉格朗日乘子, $ C = (-\nu_{0}, -\nu_{1}, \cdots, -\nu_{N+1}+1)^{T}\in R^{N+1} $.另外, 由算法中的第3步, 有$ z^{r} = z^{r-1} $.因此

$ \begin{eqnarray*} &&\sum\limits_{k\in{\{0\}}\cup T_{k2}}{\lambda}_k{\nabla}\left(\hat{G}_k(z^{r};z^{r})\right)+ \sum\limits_{k\in T_{k1}}{\mu}_{k}{\nabla}\left(\hat{G}_k(z^{r})\right)+C = 0\nonumber, \\ &&\hat{G}_{k}(z^{r};z^{r})\leq 1, \ \ \ \lambda_{k}\geq 0, \ \ \ {\lambda_{k}}\left(\hat{G}_k(z^{r};z^{r})-1\right) = 0, \quad k\in{\{0\}}\cup T_{k2}, \\ &&\hat{G}_{k}(z^{r})\leq 1, \ \ \ \mu_{k}\geq 0, \ \ \ {\mu}_{k}\left(\hat{G}_k(z^{r})-1\right) = 0, \quad k\in T_{k1}, \\ &&-z^{r}_{i}\leq 0, \ \ \ \nu_{i}\geq 0, \ \ \ \nu_{i}\left(-z^{r}_{i}\right) = 0, \quad i = 1, \cdots, N+1.\nonumber \end{eqnarray*} $

由$ {G}_{k}, \hat{G}_{k} $的定义以及引理3.1, 有

$ \begin{eqnarray} &&\sum\limits_{k\in{\{0\}}\cup T_{k2}}{\lambda}_k{\nabla}\left({G}_k(z^{r})\right)+ \sum\limits_{k\in T_{k1}}{\mu}_{k}{\nabla}\left({G}_k(z^{r})\right)+C = 0, \\ &&{G}_{k}(z^{r})\leq 1, \ \ \ \lambda_{k}\geq 0, \ \ \ {\lambda_{k}}\left({G}_k(z^{r})-1\right) = 0, \quad k\in{\{0\}}\cup T_{k2}, \\ &&{G}_{k}(z^{r})\leq 1, \ \ \ \mu_{k}\geq 0, \ \ \ {\mu}_{k}\left({G}_k(z^{r})-1\right) = 0, \quad k\in T_{k1}, \\ &&-z^{r}_{i}\leq 0, \ \ \ \nu_{i}\geq 0, \ \ \ \nu_{i}\left(-z^{r}_{i}\right) = 0, \quad i = 1, \cdots, N+1, \end{eqnarray} $

这意味着$ {z^r} $是问题(P1)的KKT点.

若算法是无限步迭代的, 易证序列$ \{z^r\} $是有界的.那么序列$ \{z^r\} $存在一个收敛的子列.不失一般性, 仍记为序列$ \{z^r\} $, 并假设$ \lim\limits_{r\to\infty}{z^r} = {z^*} $.由$ \hat G_{k}(z;\bar{z}) $和$ \hat G_{k}(z)\, $的连续可微性, 对式(3.1)–(3.4)两边取极限, 可得

$ \begin{eqnarray} &&\sum\limits_{k\in{\{0\}}\cup T_{k2}}{\lambda}_k{\nabla}\left(\hat{G}_k(z^{*};z^{*})\right)+ \sum\limits_{k\in T_{k1}}{\mu}_{k}{\nabla}\left(\hat{G}_k(z^{*})\right)+C = 0, \end{eqnarray} $

(3.5)

$ \begin{eqnarray} &&\hat{G}_{k}(z^{*};z^{*})\leq 1, \ \ \ \lambda_{k}\geq 0, \ \ \ {\lambda_{k}}\left(\hat{G}_k(z^{*};z^{*})-1\right) = 0, \quad k\in{\{0\}}\cup T_{k2}, \end{eqnarray} $

(3.6)

$ \begin{eqnarray} &&\hat{G}_{k}(z^{*})\leq 1, \ \ \ \mu_{k}\geq 0, \ \ \ {\mu}_{k}\left(\hat{G}_k(z^{*})-1\right) = 0, \quad k\in T_{k1}, \end{eqnarray} $

(3.7)

$ \begin{eqnarray} &&-z^{*}_{i}\leq 0, \ \ \ \nu_{i}\geq 0, \ \ \ \nu_{i}\left(-z^{*}_{i}\right) = 0, \quad i = 1, \cdots, N+1. \end{eqnarray} $

(3.8)

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

$ \begin{eqnarray*} &&\sum\limits_{k\in{\{0\}}\cup T_{k2}}{\lambda}_k{\nabla}\left({G}_k(z^{*};z^{*})\right)+ \sum\limits_{k\in T_{k1}}{\mu}_{k}{\nabla}\left({G}_k(z^{*})\right)+C = 0, \\ &&{G}_{k}(z^{*};z^{*})\leq 1, \ \ \ \lambda_{k}\geq 0, \ \ \ {\lambda_{k}}\left({G}_k(z^{*};z^{*})-1\right) = 0, \quad k\in{\{0\}}\cup T_{k2}, \\ &&{G}_{k}(z^{*})\leq 1, \ \ \ \mu_{k}\geq 0, \ \ \ {\mu}_{k}\left({G}_k(z^{*})-1\right) = 0, \quad k\in T_{k1}, \\ &&-z^{*}_{i}\leq 0, \ \ \ \nu_{i}\geq 0, \ \ \ \nu_{i}\left(-z^{*}_{i}\right) = 0, \quad i = 1, \cdots, N+1. \end{eqnarray*} $

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

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

例1

$ \begin{array}{llllll} \rm{min} & {(\frac{x_1+x_2+1}{x_1+x_2+2})^{1.5}\times(\frac{x_1+x_2+2}{x_1+x_2+3})^{2.1}}, \\ {\rm{s.t. }}&x_1^{1.1}x_2^{1.6}-x_1^{1.2}x_2^{1.5}\leq5, \ \ 1.0\leq x_1\leq 2.0, \ 1.0\leq x_2\leq2.0. \end{array} $

例2

$ \begin{array}{llll} \rm{min} & {(\frac{x_1+x_2+1}{x_1+x_2+2})^{1.1}\times(\frac{x_1+x_2+3}{x_1+x_2+4})^{1.2}-(\frac{x_1+x_2+6}{x_1+x_2+5})^{1.1}\times(\frac{x_1+x_2+8}{x_1+x_2+7})^{1.2}}, \\ {\rm{s.t. }}&x_1x_2^{0.5}+x_1x_2\leq4, \ \ 1.0\leq x_1\leq 2.0, \ 1.0\leq x_2\leq2.0. \end{array} $

例3

$ \begin{array}{ll} \rm{min} & {\frac{x_1+x_2+1}{x_1+x_2+2}+\frac{x_1+x_2+2}{x_1+x_2+3}}, \\ {\rm{s.t. }}&x_1^{1.1}x_2^{1.6}-x_1^{1.2}x_2^{1.5}\leq5, \ \ 1.0\leq x_1\leq 2.0, \ 1.0\leq x_2\leq2.0. \end{array} $

例4

$ \begin{array}{ll} \rm{min} & {(\frac{x_1+x_2+1}{x_1+x_2+2})^{1.1}\times(\frac{x_1+x_2+3}{x_1+x_2+4})^{1.2}+(\frac{x_1+x_2+5}{x_1+x_2+6})^{1.1}\times(\frac{x_1+x_2+7}{x_1+x_2+8})^{1.2}}, \\ {\rm{s.t. }}&x_1x_2^{2}+x_1^{2}x_2\leq10, \ \ 1.0\leq x_1\leq 2.0, \ 1.0\leq x_2\leq2.0. \end{array} $

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

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