互补问题是由美国的R.W.Cottle在其1964年博士学位论文中首先提出的.互补问题是从线性规划与非线性规划的推广而形成的, 所以它的算法研究与可解性研究一样, 受到了研究者的重视.互补问题的研究包括:可解性、解集的拓扑性质、稳定性、误差界以及不同类型的互补问题的算法等.互补问题被提出后, 很快在工程技术中得到了重要应用, 许多文献讨论了它在力学、交通、经济、金融、控制等许多领域中的广泛应用^[1-2].

线性互补问题就是求一个向量 $x\in {{R}^{n}}$, 使得 $x\ge 0, Mx+q\ge 0, {{x}^{T}}(Mx+q)=0$.线性互补问题是一类具有广泛实际应用背景的优化问题, 它也为线性规划、二次规划提供了一个统一研究的框架, 因此求解线性互补问题的有效算法一直受到学术界的重视^[3-4].线性互补问题简记为 $LCP\left(M, q \right)$, 对 $LCP\left( M, q\right)$的研究, 主要集中在理论与算法两个方面, 前者主要研究其解的存在性、唯一性、稳定性及灵敏度分析, 而后者主要建立其有效的求解方法和相应的收敛性分析.求解线性互补问题的算法有很多, 经典的有Lemke算法; 近年来出现的一些具有多项式复杂性的算法, 诸如投影法^[5]、内点法^[6-9]、非光滑牛顿法^[10]、光滑牛顿法等^[11-12].

线性互补问题的一个研究热点就是对矩阵 $M$进行分类, 目前已经成熟的分类有 $P$矩阵类, $P_{0}$矩阵类, $P_{*}$矩阵类, $Q$矩阵类, $R$矩阵类, $R_{0}$矩阵类, 充分矩阵类等^[2].然后针对不同的矩阵类给出不同的算法.另一个研究热点是光滑牛顿法.光滑牛顿法的一个重点问题就是NCP函数的构造(函数 $\varphi (a, b):{{R}^{2}}\to R$称为是NCP函数, 如果 $\varphi (a, b)=0\Leftrightarrow a\ge 0, b\ge 0, ab=0$), 因为许多算法都是通过构造NCP函数将互补问题转化为方程组或最小化问题来进行求解的.常见NCP函数有Fisher-Burmeister函数、CHKS函数, 更多的NCP函数可以参考文献[2, 13-14].

近年来, 随着各种智能算法的出现, 也开始尝试用智能算法来求解互补问题.具体方法就是把互补问题转化为无约束优化问题, 然后用智能算法进行求解^[15-17].

本文在文献[19]的基础上, 对线性互补问题和多目标优化进行了深入的研究.首先把线性互补问题转化为多目标优化问题, 借助于多目标优化有效解的定义, 给出了零有效解的概念, 进而得到多目标优化问题的零有效解就是线性互补问题的最优解.最后给出了有解、无解线性互补问题, 并分别把这些问题转化为多目标优化, 采用极大极小方法求解转化后的多目标优化问题.数值实验结果表明了该方法的正确性和有效性.

本文组织如下:第一节把线性互补问题转化为多目标优化问题, 并给出了多目标优化解的一些概念; 第二节给出求解多目标优化的极大极小法; 第三节给出数值例子; 最后对本文进行了总结.

本文研究如下线性互补问题

(P1) $ \text{ }x\ge 0, Mx+q\ge 0, {{x}^{T}}(Mx+q)=0, $其中 $x, q\in {{R}^{n}}$, $M\in {{\mathbb{R}}^{n\times n}}$.

多目标优化问题的一般形式为

(MOP) $\text{ }\left\{ \begin{aligned} &\min \text{ }\left( {{f}_{1}}(x), {{f}_{2}}(x), \cdot \cdot \cdot, {{f}_{n}}(x) \right), \\ &{\hbox{s.t.}}\text{ }x\in X, \end{aligned} \right.$

这里

$ \begin{eqnarray*}&& {{f}_{i}}(x):{{\mathbb{R}}^{n}}\to {{\mathbb{R}}^{1}}, i=1, \cdots, n, X=\{x|g(x)\ge 0\}, \\ && g(x)=({{g}_{1}}(x), {{g}_{2}}(x), \cdots, {{g}_{n}}(x)), {{g}_{i}}(x):{{\mathbb{R}}^{n}}\to {{\mathbb{R}}^{1}}, i=1, \cdots, m.\end{eqnarray*} $

定义2.1  设 ${{x}^{*}}\in X$, 若对任意 $x\in X$, 都有 ${{f}_{i}}({{x}^{*}})\le {{f}_{i}}(x), i=1, 2, \cdots, n$, 则称 ${{x}^{*}}$为问题(MOP)的最优解.

定义2.2  若 ${{x}^{*}}\in X$, 且不存在另一个可行点 $x'\in X$, 使得 ${{f}_{i}}(x')\le {{f}_{i}}({{x}^{*}}), i=1, 2, \cdots, n$成立, 且其中至少有一个严格不等式成立, 则称 ${{x}^{*}}$是问题(MOP)的一个有效解.记问题(MOP)的有效解集合为 ${{X}_{E}}$.

有效解又称Pareto最优解, 非劣解, 非支配解等^[18].

定义2.3  若 $x\in {{X}_{E}}$, 且有 ${{f}_{i}}(x)=0, i=1, 2, \cdots, n$成立, 则称 $x$为问题(MOP)的零有效解.

下面我们把问题(P1) 转化为一个优化问题.记 $X=\{x|x\ge 0, Mx+q\ge 0\}$, $y=Mx+q\ge 0$, 我们考虑如下多目标优化问题

(P2) $\text{ }\left\{ \begin{aligned} &\min \text{ }\left( {{x}_{1}}{{y}_{1}}, {{x}_{2}}{{y}_{2}}, \cdot \cdot \cdot, {{x}_{n}}{{y}_{n}} \right), \\ &{\hbox{ s.t.}}\quad \text{ }x\in X . \end{aligned} \right.$

引理2.1  若 $X\ne \varnothing $, 则问题 $(P2)$存在有效解.

引理2.2  若 $X\ne \varnothing $, 则问题(P1) 无解当且仅当问题(P2) 存在非零有效解.

引理2.3  若问题(P1) 的矩阵 $M$是 $P$矩阵类, 则问题(P2) 仅存在一个零有效解.

引理2.4  若问题(P1) 的矩阵 $M$是 $Q$矩阵类, 则问题(P2) 至少存在一个零有效解.

上述引理的证明见参考文献[19-21].

根据引理2.1和引理2.2, 得到如下结论.

定理2.1  若 $x\in {{X}_{E}}$是多目标优化问题(P2) 的零有效解当且仅当 $x$是问题(P1) 的最优解.

证  若 $x\in {{X}_{E}}$是问题(P2) 的零有效解, 根据可行性则有 $x\ge 0, Mx+q\ge 0$成立, 即 $x\in X$.又因为 ${{f}_{i}}(x)=0, i=1, 2, \cdots, n$, 从而 ${{x}_{i}}{{y}_{i}}=0, i=1, 2, \cdots, n.$因此 $x$是问题(P1) 的最优解.

反之, 若 $x$是问题(P1) 的最优解, 则 $x\ge 0, Mx+q\ge 0$, ${{x}^{T}}(Mx+q)=0$, 也即 ${{x}_{i}}{{y}_{i}}=0, i=1, 2, \cdot \cdot \cdot, n$, 且不存在另一个可行点 ${{x}_{t}}\in X$, 使得 ${{x}_{t}}^{T}(M{{x}_{t}}+q)<0$因此, $x$是问题(P2) 的零有效解.

定理2.1给出了一个求解线性互补问题的新思路, 通过求出多目标优化问题(P2) 的零有效解, 就可以获得线性互补问题的最优解.下面我们采用极大极小方法来求解多目标优化问题(P2).

问题(P2) 的极大极小模型为

(P3) $\text{ }\left\{ \begin{aligned} &\min \text{ max}\left( {{x}_{1}}{{y}_{1}}, {{x}_{2}}{{y}_{2}}, \cdot \cdot \cdot, {{x}_{n}}{{y}_{n}} \right), \\ &s.t.\quad \text{ }x\in X. \end{aligned} \right.$

推论3.1  若问题(P3) 存在非零最优目标值, 则问题(P1) 无解.

证  若(P3) 存在非零最优目标值, 则问题(P2) 存在非零有效解; 结合引理2.2可知, 问题(P1) 无解.

推论3.2  若 ${{x}^{*}}\in X$是问题(P3) 的最优解, 且 ${{x}^{*}}$使得问题(P3) 目标值恰好是零, 则 ${{x}^{*}}$也是问题(P1) 的最优解.

证  由于 ${{x}^{*}}\in X$是问题(P3) 的最优解, 且 ${{x}^{*}}$使得问题(P3) 目标值恰好是零, 则 ${{x}^{*}}$是问题(P2) 的零有效解; 结合定理2.1可知, ${{x}^{*}}$也是问题(P1) 的最优解.

这样, 我们就可以通过求解问题(P3) 来判断问题(P1) 是否有解, 进而在有解的情况下就可以求出问题(P1) 的最优解.

求解极大极小问题(P3) 的方法很多, 这里就不再熬述.为了快速求解问题(P3), 我们直接采用Matlab系统中的极大极小函数fminimax进行求解^[22].

为了测试本文方法的求解性能, 下面我们选择如下4个线性互补问题进行数值计算, 这些算例在变分不等式和互补问题的文章中经常出现, 作为标准测试函数^{[20-21, 23-25]}.

算例4.1  考虑线性互补问题, 其中 $ M = \left[{{\begin{array}{*{20}c} {-1} \hfill&1 \hfill \\ 1 \hfill&1 \hfill \\ \end{array} }} \right], \qquad q = \left[{{\begin{array}{*{20}c} {-2} \hfill \\ {-1} \hfill \\ \end{array} }} \right]. $

解  把线性互补问题转化为如下多目标优化问题

(MOP1) $\left\{ \begin{aligned} &\min \text{ }\left( -x_{1}^{2}+{{x}_{1}}{{x}_{2}}-2{{x}_{1}}, {{x}_{1}}{{x}_{2}}+{{x}_{2}}^{2}-{{x}_{2}} \right), \\ &{\hbox{s.t.}}\text{ }-{{x}_{1}}+{{x}_{2}}-2\ge 0\text{, } \\ &\text{ }\qquad {{x}_{1}}+{{x}_{2}}-1\ge 0, \\ &\text{ }\qquad{{x}_{1}}\ge 0, \text{ }{{x}_{2}}\ge 0. \end{aligned} \right.$

下面采用极大极小方法求出(MOP1) 有效解.

利用函数fminimax求得相应极大极小问题的最优解 ${{x}^{*}}={{(0, 2)}^{T}}$, 此时(MOP1) 相应的目标值为 ${{(0, 2)}^{T}}$, 对应极大极小问题的最优目标值为2, 利用推论3.1, 则此线性互补问题无解.

算例4.2  考虑线性互补问题, 其中 $ M = \left[{{\begin{array}{*{20}c} 1 \hfill&1 \hfill&0 \hfill \\ {-5} \hfill&1 \hfill&0 \hfill \\ {-1} \hfill&1 \hfill&0 \hfill \\ \end{array} }} \right], {\begin{array}{*{20}c} \hfill&\hfill&{q = \left[{{\begin{array}{*{20}c} {-2} \hfill \\ {\begin{array}{l}-1 \\-2 \\ \end{array}} \hfill \\ \end{array} }} \right]} \end{array} }. $

解  把线性互补问题转化为如下多目标优化问题

(MOP2) $\left\{ \begin{aligned} &\min \text{ }\left( x_{1}^{2}+{{x}_{1}}{{x}_{2}}-2{{x}_{1}}, -\text{5}{{x}_{1}}{{x}_{2}}+{{x}_{2}}^{2}-{{x}_{2}}, -{{x}_{1}}{{x}_{3}}+{{x}_{2}}{{x}_{3}}-2{{x}_{3}} \right), \text{ } \\ &{\hbox{s.t.}}\text{ }\quad{{x}_{1}}+{{x}_{2}}-2\ge 0\text{, } \\ &\text{ } \qquad -\text{5}{{x}_{1}}+{{x}_{2}}-1\ge 0, \text{ } \\ &\text{ } \qquad -{{x}_{1}}+{{x}_{2}}-2\ge 0, \\ &\text{ } \quad \qquad {{x}_{1}}\ge 0, \text{ }{{x}_{2}}\ge 0, \text{ }{{x}_{3}}\ge 0. \end{aligned} \right.$

采用函数fminimax求解相应极大极小问题的最优解 ${{x}^{*}}={{(\text{0}\text{.2374, 2}\text{.2374, 0})}^{T}}$, 此时相应的(MOP2) 相应的目标值为 ${{(\text{0}\text{.1127, 0}\text{.1127, 0})}^{T}}$, 对应极大极小问题的最优目标值为0.1127, 利用推论3.1, 则此线性互补问题无解.

事实上, 问题(MOP2) 的有效解为

$ {{X}_{E}}=\left\{ {{\left( {{x}_{1}}, {{x}_{2}}, {{x}_{3}} \right)}^{T}}:{{x}_{1}}=(1-\lambda )/4, {{x}_{2}}=2\lambda +(9-\lambda )/4, {{x}_{3}}=\tau \ge 0, 0\le \lambda \le 1 \right\}. $

把此有效解代入(MOP2), 得到(MOP2) 的前两个目标值如下

$ \begin{eqnarray*} && {{f}_{1}}=x_{1}^{2}+{{x}_{1}}{{x}_{2}}-2{{x}_{1}}=\frac{{{(\lambda -1)}^{2}}}{8}, 0\le \lambda \le 1, \\ && {{f}_{2}}=-\text{5}{{x}_{1}}{{x}_{2}}+{{x}_{2}}^{2}-{{x}_{2}}\text{= }\frac{-\lambda (\lambda -9)}{4}, 0\le \lambda \le 1, \end{eqnarray*} $

这两个函数在 $0\le \lambda \le 1$上的图像如图 1所示.

由图 1可知, 在有效解内, 此问题不存在零有效解.即找不到 ${{\lambda }^{*}}\in[0,1], $使得 ${{f}_{i}}=0, i=1, 2, 3$同时成立.从而相应的线性互补问题就无解.

算例4.3  考虑线性互补问题, 其中 $ M=\left[\begin{matrix} 3 &-2 &-1 \\-2&2&1 \\ -1&1&1 \end{matrix} \right], \begin{matrix} {}&{}&{}&q=\left[\begin{matrix} 14 \\-11 \\-7 \end{matrix} \right]. \end{matrix} $

解  把线性互补问题转化为如下多目标优化问题:

(MOP3) $\left\{ \begin{aligned} &\min \text{ }\left( \text{3}{{x}_{1}}^{2}-2{{x}_{1}}{{x}_{2}}-{{x}_{1}}{{x}_{3}}+14{{x}_{1}}, -\text{2}{{x}_{1}}{{x}_{2}}+2{{x}_{2}}^{2}+{{x}_{2}}{{x}_{3}}-11{{x}_{2}}, \right.\\ &~~~\left.-{{x}_{1}}{{x}_{3}}+{{x}_{2}}{{x}_{3}}+{{x}_{3}}^{2}-7{{x}_{3}}\text{ } \right), \\& {\hbox{s.t.}}\quad \text{ 3}{{x}_{1}}-2{{x}_{2}}-{{x}_{3}}+14\ge 0\text{, } \\&~~~ -\text{2}{{x}_{1}}+2{{x}_{2}}+{{x}_{3}}-11\ge 0, \text{ } \\ &~~~-{{x}_{1}}+{{x}_{2}}+{{x}_{3}}-7\ge 0, \\ & ~~~{{x}_{1}}\ge 0, \text{ }{{x}_{2}}\ge 0, \text{ }{{x}_{3}}\ge 0. \end{aligned} \right.$

采用函数fminimax求解相应极大极小问题的最优解 ${{x}^{*}}={{(0, 4, 3)}^{T}}$, 验证可知 ${{x}^{*}}={{(0, 4, 3)}^{T}}$是问题(MOP3) 的零有效解, 从而此线性互补问题的解为 ${{x}^{*}}={{(0, 4, 3)}^{T}}$.

算例4.4  考虑线性互补问题, 其中 $M=\left[\begin{matrix} \begin{matrix} \begin{matrix} 0 \\ 0 \\ \end{matrix} \\ 1 \\ 3 \\ 2 \end{matrix}&\begin{matrix} \begin{matrix} 0 \\ 0 \\ \end{matrix} \\ 2 \\ 1 \\ 3 \end{matrix}&\begin{matrix} \begin{matrix} 2 \\ 1 \\ \end{matrix} \\ 0 \\ 0 \\ 0 \end{matrix}&\begin{matrix} \begin{matrix} \begin{matrix} 2 \\ 2 \\ \end{matrix} \\ 0 \\ 0 \\ 0 \end{matrix}&\begin{matrix} \begin{matrix} 1 \\ 2 \end{matrix} \\ 0 \\ 0 \\ 0 \end{matrix} \\ \end{matrix} \\ \end{matrix} \right], \begin{matrix} {}&{}&{}&q=\left[\begin{matrix} \begin{matrix}-1 \\-1 \end{matrix} \\-1 \\ -1 \\ -1 \end{matrix} \right] \end{matrix}.$

解  把线性互补问题转化为如下多目标优化问题

(MOP4) $\left\{ \begin{aligned} &\min \text{ }\left( {} \right.2{{x}_{1}}{{x}_{3}}+2{{x}_{1}}{{x}_{4}}+2{{x}_{1}}{{x}_{5}}-{{x}_{1}}, {{x}_{2}}{{x}_{3}}+2{{x}_{2}}{{x}_{4}}+2{{x}_{2}}{{x}_{5}}-{{x}_{2}}, \\ &\qquad\quad \text{ }{{x}_{1}}{{x}_{3}}+2{{x}_{2}}{{x}_{3}}-{{x}_{3}}, {3{x}_{1}}{{x}_{4}}+{{x}_{2}}{{x}_{4}}-{{x}_{4}}\text{, 2}{{x}_{1}}{{x}_{5}}+3{{x}_{2}}{{x}_{5}}-{{x}_{5}}\left. {} \right), \\ &{\hbox{s.t.}}\qquad\text{ }2{{x}_{3}}+2{{x}_{4}}+{{x}_{5}}-1\ge 0\text{, } \\ &\qquad\qquad\text{ }{{x}_{3}}+2{{x}_{4}}+2{{x}_{5}}-1\ge 0, \\ &\qquad\qquad\text{ }{{x}_{1}}+2{{x}_{2}}-1\ge 0, \text{ } \\ &\qquad\qquad\text{ 3}{{x}_{1}}+{{x}_{2}}-1\ge 0, \text{ } \\ &\qquad\qquad\text{ 2}{{x}_{1}}+3{{x}_{2}}-1\ge 0, \text{ } \\ &\qquad\qquad\text{ }{{x}_{1}}\ge 0, \text{ }{{x}_{2}}\ge 0, \text{ }{{x}_{3}}\ge 0. \end{aligned} \right.$

采用函数fminimax求解相应极大极小问题的最优解为 ${{x}^{*}}={{(\text{0}\text{.1960, 0}\text{.4121, 0, 0}\text{.5000, 0})}^{T}}$, 验证可知 ${{x}^{*}}={{(\text{0}\text{.1960, 0}\text{.4121, 0, 0}\text{.5000, 0})}^{T}}$是问题(MOP4) 的零有效解, 从而该线性互补问题的解为 ${{x}^{*}}={{(\text{0}\text{.1960, 0}\text{.4121, 0, 0}\text{.5000, 0})}^{T}}$.

事实上该线性互补问题的解为 ${{x}^{*}}={{\left( \alpha, \beta, 0, 0.5, 0 \right)}^{T}}$， $\alpha $与 $\beta $满足 $3\alpha +\beta =1$, 见文献[23].本文的方法执行一次只能得到一个零有效解.若要得到多个不同的零有效解, 则需要多次执行该算法, 且每次需要选取不同的初始点.

本文将线性互补转化为多目标优化问题进行求解, 指出多目标优化问题的零有效解是线性互补问题的最优解. 4个测试算例计算结果表明, 本文的方法是有效的.因此本文方法可作为线性互补问题目前算法的一个重要补充和完善.