ABSTRACT

In this paper, we consider a class of sums of linear multiplicative programming problems. Using two-stage relaxation technique, a new lower bound of the objective function is obtained. If so, we only solve a sequence of linear programming problems. Moreover, we use a rectangular reduction strategy to provide a new branch and bound reduction algorithm for determining the lower bound of global optimal value. Numerical examples are given to illustrate the obtained results.

Keywords:The Global Value, Linear Multiplicative Programming, Branch and Bound

一类线性乘积和规划问题的分支定界缩减方法

井霞，高磊

宝鸡文理学院数学与信息科学学院，陕西 宝鸡

收稿日期：2017年10月3日；录用日期：2017年10月15日；发布日期：2017年10月23日

摘 要

本文考虑一类带有符号的线性乘积和规划问题。利用二级松弛技术，得到原问题中目标函数的一个新的下逼近函数，进而将原来的非凸规划问题转化为一系列的线性规划问题。进一步，采用超矩形的缩减技术提出了确定此类问题全局最优值下界的分支定界缩减方法。最后，通过数值算例验证了本文所给算法的可行性与有效性。

关键词 :全局最优值，线性乘积规划，分支定界

Copyright © 2017 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

本文考虑如下带有符号的线性乘积和规划问题：

$\left(GLMP\right)\{\begin{array}{l}\min f\left(x\right)={\displaystyle \underset{j=1}{\overset{p}{\sum }}{\delta }_j}{n}_j\left(x\right)d_j\left(x\right)\\ s.t.x\in D=\left\{x\in R^n|Ax\le b\right\}\end{array}$

其中 $n_j\left(x\right),d_j\left(x\right)\left(j=1,2,\cdots ,p\right)$ 为 $R^n$ 上的线性函数， ${\delta }_j=+1$ 或 $-1$ ， $j=1,2,\cdots ,p$ ， $A\in R^{m\times n}$ ， $b\in R^m$ ，p，m，n都是正整数，D是非空有界的凸多面体。

乘积规划问题在用于经济、交通等众多领域具有广泛的使用价值，如金融优化 [1] 、鲁棒优化 [2] 、证券投资 [3] 等。乘积规划问题的多极值性(多个局部最优解)，使得求其全局最优解变得十分困难。所以，有许多学者关注于乘积规划问题的全局最优值的求解。近年来，一些求解乘积规划问题的方法相继被提出，包括外逼近方法 [4] ，割平面法 [5] ，分支定界方法 [5] [6] [7] 等。本文针对一类带有符号的线性乘积和规划问题(GLMP)，采用二级松弛技术和超矩形缩减策略，提出了一种新的分支定界算法，并进行了数值分析。

本文的结构安排如下：第2节利用二级松弛技术，确定(GLMP)问题全局最优值的下界；第3节利用超矩形的剖分与缩减技术，给出分支定界算法，通过数值算例验证算法的可行性与有效性。

2. 松弛定下界方法

本节首先利用凸包络技术给出(GLMP)问题中乘积函数的一个下界函数，进一步，通过二次松弛得到原问题的线性松弛规划问题，进而给出(GLMP)问题的下界。

不失一般性，我们假定 ${\delta }_j=+1$ ， $j=1,2,\cdots ,p_1$ ； ${\delta }_j=-1$ ， $j=p_1+1,p_1+2,\cdots ,p$ 。因(GLMP)问题的可行域D是非空有界集，我们可构造包含D的超矩形 $H^{\text{0}}=\left[v^{\text{0}},h^{\text{0}}\right]$ ， $v^{\text{0}}={\left(v_{\text{1}}^{\text{0}},v_{\text{2}}^{\text{0}},\cdots ,v_n^{\text{0}}\right)}^{\text{T}}$ ， $h^{\text{0}}={\left(h_{\text{1}}^{\text{0}},h_{\text{2}}^{\text{0}},\cdots ,h_n^{\text{0}}\right)}^{\text{T}}$ ，其中 $v_i^{\text{0}}=\underset{x\in D\cap H^0}{\min }{x}_i$ ， $h_i^{\text{0}}=\underset{x\in D\cap H^0}{\max }{x}_i$ ， $i=1,2,\cdots ,n$ .

下面确定乘积函数 $n_j\left(x\right)d_j\left(x\right)$ 的凸包络，首先求解如下线性规划问题：

$\{\begin{array}{l}\min n_j\left(x\right)\\ s.t.x\in D\cap H^0\end{array}$ ， $\{\begin{array}{l}\max n_j\left(x\right)\\ s.t.x\in D\cap H^0\end{array}$ ， $\{\begin{array}{l}\min d_j\left(x\right)\\ s.t.x\in D\cap H^0\end{array}$ 和 $\{\begin{array}{l}\max d_j\left(x\right)\\ s.t.x\in D\cap H^0\end{array}$ (1)

设问题(1)的最优解分别为 $x_j^1$ ， $x_j^2$ ， $x_j^3$ ， $x_j^4$ ，最优值分别为 ${\underset{\_}{\epsilon }}_j$ ， ${\bar{\epsilon }}_j$ ， ${\underset{\_}{\eta }}_j$ ， ${\bar{\eta }}_j$ ( $j=1,2,\cdots ,p$ )，从而有

${\underset{\_}{\epsilon }}_j\le n_j\left(x\right)\le {\bar{\epsilon }}_j$ ， ${\underset{\_}{\eta }}_j\le d_j\left(x\right)\le {\bar{\eta }}_j$ (2)

显然 $x_j^1$ ， $x_j^2$ ， $x_j^3$ ， $x_j^4$ 均为(GLMP)问题的可行解，设 $Q=Q\cup \left\{x_j^1,x_j^2,x_j^3,x_j^4:j=1,\cdots ,p\right\}$ ，其中Q表示(GLMP)问题目前可行解的集合。

令 ${\Omega }_j=\left[{\underset{\_}{\epsilon }}_j,{\bar{\epsilon }}_j\right]\times \left[{\underset{\_}{\eta }}_j,{\bar{\eta }}_j\right]$ ， $j=1,2,\cdots ,p$ 。下面确定乘积函数 $n_j\left(x\right)d_j\left(x\right)$ 在 ${\Omega }_j$ 上的凸包络 [8] ：

由(2)式可得：

1) 若 $\left(n_j-{\underset{\_}{\epsilon }}_j\right)\ge 0$ 且 $\left(d_j-{\underset{\_}{\eta }}_j\right)\ge 0$ ，则

$\left(n_j-{\underset{\_}{\epsilon }}_j\right)\left(d_j-{\underset{\_}{\eta }}_j\right)\ge 0$

展开得

$n_j{d}_j\ge {\underset{\_}{\eta }}_j{n}_j+{\underset{\_}{\epsilon }}_j{d}_j-{\underset{\_}{\epsilon }}_j{\underset{\_}{\eta }}_j$

2) 若 $\left(n_j-{\bar{\epsilon }}_j\right)\le 0$ 且 $\left(d_j-{\bar{\eta }}_j\right)\le 0$ ，则

$n_j{d}_j\ge {\bar{\eta }}_j{n}_j+{\bar{\epsilon }}_j{d}_j-{\bar{\epsilon }}_j{\bar{\eta }}_j$

3) 若 $\left(n_j-{\underset{\_}{\epsilon }}_j\right)\ge 0$ 且 $\left(d_j-{\bar{\eta }}_j\right)\le 0$ ，则

$n_j{d}_j\le {\bar{\eta }}_j{n}_j+{\underset{\_}{\epsilon }}_j{d}_j-{\underset{\_}{\epsilon }}_j{\bar{\eta }}_j$

4) 若 $\left(n_j-{\bar{\epsilon }}_j\right)\le 0$ 且 $\left(d_j-{\underset{\_}{\eta }}_j\right)\ge 0$ ，则

$n_j{d}_j\le {\underset{\_}{\eta }}_j{n}_j+{\bar{\epsilon }}_j{d}_j-{\bar{\epsilon }}_j{\underset{\_}{\eta }}_j$

为了表达方便，令：

${\underset{\_}{\eta }}_j{n}_j+{\underset{\_}{\epsilon }}_j{d}_j-{\underset{\_}{\epsilon }}_j{\underset{\_}{\eta }}_j\triangleq {\underset{\_}{f}}_j^1\left(x\right)$ ， ${\bar{\eta }}_j{n}_j+{\bar{\epsilon }}_j{d}_j-{\bar{\epsilon }}_j{\bar{\eta }}_j\triangleq {\underset{\_}{f}}_j^2\left(x\right)$

${\bar{\eta }}_j{n}_j+{\underset{\_}{\epsilon }}_j{d}_j-{\underset{\_}{\epsilon }}_j{\bar{\eta }}_j\triangleq {\bar{f}}_j^1\left(x\right)$ ， ${\underset{\_}{\eta }}_j{n}_j+{\bar{\epsilon }}_j{d}_j-{\bar{\epsilon }}_j{\underset{\_}{\eta }}_j\triangleq {\bar{f}}_j^2\left(x\right)$

即

$\max \left\{{\underset{\_}{f}}_j^1\left(x\right),{\underset{\_}{f}}_j^2\left(x\right)\right\}\le n_j{d}_j\le \min \left\{{\bar{f}}_j^1\left(x\right),{\bar{f}}_j^2\left(x\right)\right\}$

由此，我们可以得到(GLMP)问题在超矩形 $H^k\subseteq H^0$ 上的松弛规划问题(SLMP)：

$\left(SLMP\right)\{\begin{array}{l}\text{min}{\displaystyle \underset{j=1}{\overset{p_1}{\sum }}\max \left\{{\underset{\_}{f}}_j^1\left(x\right),{\underset{\_}{f}}_j^2\left(x\right)\right\}-{\displaystyle \underset{j=p_1+1}{\overset{p}{\sum }}\min \left\{{\bar{f}}_j^1\left(x\right),{\bar{f}}_j^2\left(x\right)\right\}}}\\ s.t.x\in D\cap H^k\end{array}$

又因

${\displaystyle \underset{j=1}{\overset{p_1}{\sum }}\max \left\{{\underset{\_}{f}}_j^1\left(x\right),{\underset{\_}{f}}_j^2\left(x\right)\right\}}\ge \max \left\{{\displaystyle \underset{j=1}{\overset{p_1}{\sum }}{\underset{\_}{f}}_j^1\left(x\right)},{\displaystyle \underset{j=1}{\overset{p_1}{\sum }}{\underset{\_}{f}}_j^2\left(x\right)}\right\}$

${\displaystyle \underset{j=p_1+1}{\overset{p}{\sum }}\min \left\{{\bar{f}}_j^1\left(x\right),{\bar{f}}_j^2\left(x\right)\right\}}\le \min \left\{{\displaystyle \underset{j=p_1+1}{\overset{p}{\sum }}{\bar{f}}_j^1\left(x\right)},{\displaystyle \underset{j=p_1+1}{\overset{p}{\sum }}{\bar{f}}_j^2\left(x\right)}\right\}$

所以我们可得到(GLMP)问题在超矩形 $H^k\subseteq H^0$ 上的二级松弛规划问题(SSLP):

$\left(SSLP\right)\{\begin{array}{l}\text{min}\underset{\_}{f}\left(x\right)=\max \left\{{\displaystyle \underset{j=1}{\overset{p_1}{\sum }}{\underset{\_}{f}}_j^1\left(x\right)},{\displaystyle \underset{j=1}{\overset{p_1}{\sum }}{\underset{\_}{f}}_j^2\left(x\right)}\right\}-\min \left\{{\displaystyle \underset{j=p_1+1}{\overset{p}{\sum }}{\bar{f}}_j^1\left(x\right),{\displaystyle \underset{j=p_1+1}{\overset{p}{\sum }}{\bar{f}}_j^2\left(x\right)}}\right\}\\ s.t.x\in D\cap H^k\end{array}$

(SSLP)问题的最优解为(GLMP)问题的一个可行解，其最优值恰好为(GLMP)问题在超矩形 $H^k$ 上全局最优值的一个下界，该可行解记为 $x^k$ ，令 $Q=Q\cup \left\{x^k\right\}$ ，其中Q表示(GLMP)问题目前所有可行解构成的集合。

进一步，我们可以得到与(GLMP)问题等价的线性规划问题(LP)：

$\left(LP\right)\{\begin{array}{l}\min \underset{\_}{f}\left(x,t_1,t_2\right)=t_1-t_2\\ s.t.{\displaystyle \underset{j=1}{\overset{p_1}{\sum }}{\underset{\_}{f}}_j^1\left(x\right)}-t_1\le 0,\\ {\displaystyle \underset{j=1}{\overset{p_1}{\sum }}{\underset{\_}{f}}_j^2\left(x\right)}-t_1\le 0,\\ {\displaystyle \underset{j=p_1+1}{\overset{p}{\sum }}{\bar{f}}_j^1\left(x\right)}-t_2\ge 0,\\ {\displaystyle \underset{j=p_1+1}{\overset{p}{\sum }}{\bar{f}}_j^2\left(x\right)}-t_2\ge 0,\\ x\in D=\left\{x\in R^n|Ax\le \text{b}\right\}\cap H^k=\left[v^k,h^k\right]\end{array}$

显然，(LP)问题在 $H^k$ 上的最优值是(GLMP)问题全局最优值的一个下界，它也是(GLMP)问题在 $H^k$ 上全局最优值的一个下界。

3. 分支定界算法

本节利用超矩形的剖分与缩减技术，给出确定(GLMP)问题全局最优值的分支定界算法，并进行数值实验。

3.1. 超矩形的剖分

不失一般性，假设第k次剖分的超矩形为 $H^k=\left[v^k,h^k\right]\subseteq H^0$ ：

步骤1：

1) 选择 $H^k$ 的最长边，即 $h_{\xi }^k-v_{\xi }^k=\max \left\{h_i^k-v_i^k:i=1,2,\cdots ,n\right\}$ ；

2) 令 $x_{\xi }^k=\frac{v_{\xi }^k+h_{\xi }^k}{2}$ ， $\bar{x}=\left(v_1^k,v_2^k,\cdots ,v_{i-1}^k,x_{\xi }^k,v_{i+1}^k,\cdots ,v_n^k\right)$

步骤2：将超矩形 $H^k$ 沿着 $\bar{x}$ 剖分为子超矩形

$H_1^{k+}{}^1=\left[v^{k+1,1},h^{k+1,1}\right]$ , $H_2^{k+}{}^1=\left[v^{k+1,2},h^{k+1,2}\right]$

其中

$v^{k\text{+}1,1}={\left(v_1^{k\text{+}1,1},v_2^{k\text{+}1,1},\cdots ,v_n^{k\text{+}1,1}\right)}^{\text{T}}$ ， $h^{k\text{+}1,1}={\left(h_1^{k\text{+}1,1},\cdots ,h_{i-1}^{k\text{+}1,1},x_{\xi }^k,h_{i+1}^{k\text{+}1,1},\cdots ,h_n^{k\text{+}1,1}\right)}^{\text{T}}$ ，

$h^{k\text{+}1,2}={\left(h_1^{k\text{+}1,2},h_2^{k\text{+}1,2},\cdots ,h_n^{k\text{+}1,2}\right)}^{\text{T}}$ ， $v^{k\text{+}1,2}={\left(v_1^{k\text{+}1,2},\cdots ,v_{i-1}^{k\text{+}1,2},x_{\xi }^k,v_{i+1}^{k\text{+}1,2},\cdots ,v_n^{k\text{+}1,2}\right)}^{\text{T}}$ 。

令 $P=\left\{H_1^{k+1},H_2^{k+1}\right\}$ ， $T=\left(T\backslash \left\{H^k\right\}\right)\cup P$ 。

3.2. 超矩形的缩减

为了叙述方便，缩减后的超矩形仍记为 $H^k$ 。对(GLMP)问题中的线性不等式约束条件 ${\displaystyle \underset{j=1}{\overset{n}{\sum }}{a}_{ij}{x}_j\le b_i}$ ( $i=1,2,\cdots ,m$ )，利用文献 [6] [9] 中超矩形缩减技术进行缩减。

3.3. 分支定界算法

给出以下记号(假定算法迭代到第k步)：

D：(GLMP)问题的可行域；Q：当前可行解的集合； $H^k$ ：选择剖分的超矩形；

T：剪支剩余超矩形的集合； $\tau$ ：(GLMP)问题全局最优值的上界；

$\eta$ ：(GLMP)问题全局最优值的下界。

下面给出算法过程的具体描述。

步骤1：(初始化)

构造包含 $D$ 的超矩形 $H^{\text{0}}=\left[v^{\text{0}},h^{\text{0}}\right]$ ，在超矩形 $H^{\text{0}}$ 上求解问题(LP)，其对应最优解和最优值分别记为 $x^d$ 和 $\eta$ ， $\eta$ 就是(GLMP)问题全局最优值的一个下界，显然 $x^d\in D$ ，令 $Q=Q\cup \left\{x^d\right\}$ ，初始上界为 $\gamma =\min \left\{f\left(x\right):x\in Q\right\}$ ，并找一个当前最优解 $x^{*}\in \arg \min \gamma$ ，给定精度 $\sigma$ ， $T=\left\{H^{\text{0}}\right\}$ ，置k = 1。

步骤2：(终止规则)

若 $\gamma -\eta \le \sigma$ 或 $T=\Phi$ ，则终止，输出(GLMP)问题的全局最优解 $x^{*}$ 、全局最优值 $f\left(x^{*}\right)$ ; 否则，转步骤3；

步骤3：(选择规则)

在 $T$ 中选择 $H^k$ ， $H^k$ 为 $\eta$ 所对应的超矩形，即 $\eta =\eta \left(H^k\right)$ ；

步骤4：(剖分及缩减技术)

运用2.1中超矩形的剖分方法，将 $H^k$ 剖分为 $H_1^{k\text{+}1}$ 与 $H_2^{k\text{+}1}$ 两部分， $\mathrm{int}{H}_1^{k+1}\cap \mathrm{int}{H}_2^{k+1}=\Phi$ ；再应用2.2

中超矩形的缩减技术，将 $H_1^{k+1}$ 和 $H_2^{k+1}$ 缩减后的超矩形仍记为 $H_i^{k+1}$ ，令 $T=T\cup \left\{H_i^{k+1}\right\}$ ( $i\in \Gamma$ )，缩减后的超矩形的指标集，记为 $\Gamma \subseteq \left\{1,2\right\}$ 。

步骤5：(剪支规则)让 $T=T\backslash \left\{H:\overline{\stackrel{¯}{\eta }}\left(H\right)\ge \gamma ,H\in T\right\}$ 。

步骤6：(定界)定下界： $\eta =\min \left\{\underset{\_}{f}\left(H\right):H\in T\right\}$ ；

定上界： $\gamma =\min \left\{f\left(x\right):x\in Q\right\}$ ，当前最好的可行解： $x^{*}\in \arg \min \left\{f\left(x\right):x\in Q\right\}$

置 $k\leftarrow k+1$ ，转步骤2。

4. 数值实验

为了检测新算法的可行性与有效性，做以下的数值实验，算法编程在Pentium(R)4，CPU3.20 GHZ，1.00 GB内存微机上运行，精度取为 $\sigma ={10}^{-6}$ 。

例1 [7]

$\{\begin{array}{l}\min \left(2x_1-2x_2+x_3+2\right)\times \left(-2x_1+3x_2+x_3-4\right)+\left(-2x_1+x_2+x_3+2\right)\\ \times \left(x_1+x_2-3x_3+5\right)+\left(-2x_1-x_2+2x_3+7\right)\times \left(4x_1-x_2-2x_3-5\right)\\ s.t.x_1+x_2+x_3\le 10\\ x_1-2x_2+3x_3\le 10\\ -2x_1+2x_2+3x_3\le 10\\ -x_1+2x_2-3x_3\le 10\\ -x_1+2x_2+3x_3\ge 6\\ x_1\ge 1,x_2\ge 1,x_3\ge 1\end{array}$

运用本文所提出的算法得到：最优解为(5.5556; 1.7778; 2.6667)，最优值为−112.7531，迭代次数为3，计算时间为1.586198。文献 [7] 的最优解为(5.5556; 1.7778; 2.6667)，最优值为−112.7531，迭代次数为54。

通过以上计算所得结果显示，本文所提出的方法是有效可行的。

基金项目

陕西省自然科学基础研究项目(2017JQ3020)；陕西省高校科协青年人才托举项目资助(20160234)；宝鸡文理学院校级科研项目(ZK2017095; ZK2017021)。

文章引用

井 霞,高 磊. 一类线性乘积和规划问题的分支定界缩减方法
A Branch and Bound Reduction Algorithm for Solving a Class of Sums of Linear Multiplicative Programming Problems[J]. 运筹与模糊学, 2017, 07(04): 104-109. http://dx.doi.org/10.12677/ORF.2017.74012

参考文献 (References)