集值优化问题弱极小解的逼近定理

Approximation Theorem for Weak Minimal Solutions of Set-Valued Optimization Problems

摘要: 目的：针对集值优化问题，考虑该问题的近似弱极小解序列的收敛性。方法：通过定义集值优化问题的ε-近似弱极小解的概念，在有限理性的框架下寻求一个集值优化问题的近似弱极小解序列来逼近其精确解。结果：给出了集值优化问题弱极小解的一个逼近定理以及两个重要推论。结论：证明了在一定条件下对于集值优化问题可以用在有限理性下的近似解来逼近在完全理性下的精确解，这一结果为该问题的计算提供了一种理论支持。

Abstract: Objective: For set-valued optimization problem, we consider the convergence of the approximate weak minimal solution sequence. Method: By defining the concept of ε-approximate weak minimal solution for set-valued optimization problems, we aim to seek a sequence of approximate weak minimal solutions for the problem to approximate their exact solutions. Results: An approximation theorem and two corollaries for set-valued optimization problems are presented. Conclusion: It is proved that under certain conditions, the approximate solution under bounded rationality can be approached by the exact solution under full rationality for set-valued optimization problems. This result provides a theoretical support for the calculation of the problem.

1. 引言

近年来，集值优化问题(简称SOP)引起了大量学者的关注并成为优化领域的一个热点，它不仅推广了数值优化问题和向量优化问题，而且还在鲁棒优化 [1] [2] 、最优控制 [3] 和经济学 [4] 和变分包含 [5] 等领域有着广泛的应用，并为这些理论的研究与发展提供了一个统一的研究框架。因此，对集值优化问题的研究有着重要的理论意义和应用价值。近年来该问题还备受广大研究工作者的青睐，且有了较丰硕的研究成果 [6] [7] [8] [9] [10] 。

由于决策者在做决策时会受到认知、环境等因素的影响，往往不能得到“精确”的最优解，这使得建立在完全理性假设下的经济模型的应用受到了限制，而Simon [11] 引入的有限理性则打破了这种限制，并使结论的假设条件更加符合实际情况。在此之后，Anderlini和Canning [12] 在2001年引入了有限理性函数的概念，建立了一个具有抽象理性函数的模型M。随后，Yu等对模型M进行了改造，不仅大大减弱模型M中的条件，而且扩大了其应用范围，并将结果应用于优化问题、平衡问题、一般n人非合作博弈问题、多目标博弈问题等，参见文献 [13] [14] [15] [16] [17] 。最近，部分学者将该有限理性模型应用到向量平衡问题，广义多目标博弈，种群博弈等方面，产生了较多新的结果，见文献 [18] [19] [20] 。

现实生活中，人们在有限理性下决策时往往寻求“满意解”，而不是精确的“最优解”，也就是“满意原则”。实际上，“满意解”对应近似解，反映了有限理性，精确的“最优解”对应完全理性。然而，现实生活中很难得到精确的“最优解”，我们只有尽可能地去寻求近似解。2009年，俞在文献 [21] 中给出了有限理性下最优化问题和多目标优化问题的逼近定理。他认为问题本身是近似的，其求解方法也是近似的，只能寻求某种近似的，但已经是足够好的，可以使决策者满意和放心的方案或策略。同时他还揭示了在一定假设条件下可以用有限理性来逼近完全理性，回应了Simon有限理性的质疑，这是很有理论意义的。关于有限理性下相关问题的逼近定理的研究还可见 [18] [22] [23] 。

受以上工作的激励，本文致力于在有限理性下研究集值优化问题的逼近定理，即想找到一个集值优化问题的近似解序列来逼近其精确解。这一结果是新的并为该问题的计算提供了一种理论支持。

2. 预备知识

设 $\mathcal{Z}$ 是一个实线性空间， $\mathcal{C}$ 是 $\mathcal{Z}$ 中的凸锥，且满足 $\left\{0\right\}\ne \mathcal{C}\ne \mathcal{Z}$ ，K是一个非空集合， $F:K\to P_0\left(\mathcal{Z}\right)$ 为一个非空值的集值映射，其中 $P_0\left(\mathcal{Z}\right)$ 表示 $\mathcal{Z}$ 中所有非空子集的全体。

集值优化问题(SOP)的模型如下：

$\{\begin{array}{l}{\min }_{\mathcal{C}}F\left(x\right)\hfill \\ x\in K\hfill \end{array}$ .

定义2.1 [7] 设N是 $\mathcal{Z}$ 的非空子集，

1) 集合S称为代数实的，若代数内部非空，即：

$cor\left(S\right)=\left\{\bar{t}\in N:\forall t\in \mathcal{Z},\exists \theta >0,\text{s}\text{.t}.\bar{t}+\left[0,\theta \right]t\subseteq S\right\}\ne \varnothing$ .

2) 假设 $\mathcal{C}$ 是代数实的，若 $\left(\left\{\bar{t}\right\}-cor\left(\mathcal{C}\right)\right)\cap S=\varnothing$ ，则称 $\bar{t}\in S$ 是S的弱极小元；

3) 若存在 $\bar{t}\in F\left(x\right)$ ，使 $\bar{t}\in F\left(x\right)$ 是集合 $F\left(K\right)$ 的一个弱极小元，则 $x\in K$ 是SOP的一个弱极小解。其中， $F\left(K\right)=\underset{x\in K}{\cup }F\left(x\right)$ 。

定义2.2 [24]

1) 设 $\left(X,d\right)$ 是一个度量空间， $S\subset X$ 是一个非空点集， $\forall \epsilon >0$ ，记

$U\left(\epsilon ,S\right)=\left\{r\in X:\exists q\in S,使d\left(r,q\right)<\epsilon \right\}$ .

2) 设 $A,B$ 是X中任意两个非空有界闭集，定义有界闭集A和B之间的Hausdorff距离为：

$\hslash \left(A,B\right)=\inf \left\{\epsilon >0:A\subset U\left(\epsilon ,B\right),B\subset U\left(\epsilon ,A\right)\right\}$ .

定义2.3 [24] 设 $X,\mathcal{Z}$ 为两个Hausdorff拓扑空间， $F:X\to P_0\left(\mathcal{Z}\right)$ 为集值映射。

1) 若对 $\mathcal{Z}$ 中任意包含 $F\left(x\right)$ 的开集 $\mathcal{S}$ ，存在x的开领域 $O\left(x\right)$ ，使 $\forall x^{\prime }\in O\left(x\right)$ ，有 $F\left(x^{\prime }\right)\subset \mathcal{S}$ ，则称F在x是上半连续的；

2) 若F在X中每一点都是上半连续的，则称F在X是上半连续的。

引理2.1 [24] $X,\mathcal{Z}$ 是两个Hausdorff拓扑空间， $\mathcal{Z}$ 是度量空间，集值映射 $F:X\to P_0\left(\mathcal{Z}\right)$ 满足 $\forall x\in X$ ， $F\left(x\right)$ 是紧集，则F在 $x\in X$ 是上半连续的当且仅当 $\forall \epsilon >0$ ，存在x的开邻域 $O\left(x\right)$ ，使 $\forall x^{\prime }\in O\left(x\right)$ ，有 $F\left(x^{\prime }\right)\subset U\left(\epsilon ,F\left(x\right)\right)$ 。

引理2.2 [21] 设 $\left\{S_n\right\}$ 是度量空间X中的一列非空有界子集，S是X中的一个非空紧集，如果 $h\left(S_n,S\right)\to 0$ ， $w_n\in S_n$ ，则存在 $\left\{w_n\right\}$ 的子序列 $\left\{w_{n_k}\right\}$ ，使 $w_{n_k}\to w\in S$ ，其中h是X上的Hausdorff距离。

有限理性模型： [21]

设M是参数空间，任意的 $\lambda$ 是一个博弈；S是行为空间，任意的s是一个策略； $G:\Omega \times S\to P_0\left(S\right)$ 是可行映射，而G诱导出行为映射g，其中 $g\left(\lambda \right)=\left\{s\in S:s\in G\left(\lambda ,s\right)\right\}$ ，集值映射g的图像 $Graph\left(g\right)=\left\{\left(\lambda ,s\right)\in \Omega \times S:s\in g\left(\lambda \right)\right\}$ ； $\text{Φ}:Graph\left(g\right)\to R_{+}$ 是理性函数。

3. 逼近定理

在本节，我们首先引入集值优化问题的 $\epsilon$ -近似弱极小解的概念。

定义3.1 E是Hausdorff线性拓扑空间， $\mathcal{Z}$ 是紧赋范线性空间，K是E中的非空集合， $\mathcal{C}$ 是 $\mathcal{Z}$ 中的代数实的闭凸锥，且 $int\left(\mathcal{C}\right)\ne \varnothing$ 。 $F:K\to P_0\left(\mathcal{Z}\right)$ 是一个非空值的集值映射，满足 $\forall x\in K$ ， $F\left(x\right)$ 是紧集。若对于一个实数 $\epsilon >0$ ，存在 $t\in F\left(x\right)$ ，使 $\left(\left\{t\right\}+\left\{\epsilon \right\}-cor\left(\mathcal{C}\right)\right)\cap F\left(K\right)=\varnothing$ ，则称 $x\in K$ 是SOP的一个 $\epsilon$ -近似弱极小解。

接下来，我们给出本文的主要结果：

定理3.1 设 $\left(E,d\right)$ 是一个度量空间， $\mathcal{Z}$ 是一个紧赋范线性空间，且满足下列条件：

1) $\forall n=1,2,\cdots$ ，集值隐射序列 $F^n:K\to P_0\left(\mathcal{Z}\right)$ 满足： $\underset{x\in K}{\sup }\hslash \left(F^n\left(x\right),F\left(x\right)\right)\to 0\left(n\to \infty \right)$ ，其中 $F:K\to P_0\left(\mathcal{Z}\right)$ 是上半连续的， $\hslash$ 是 $\mathcal{Z}$ 上的Hausdorff距离。

2) $\forall n=1,2,\cdots$ ， $\left\{K_n\right\}$ 是E中非空子集序列，满足 $\tilde{h}\left(K_n,K\right)\to 0\left(n\to \infty \right)$ ，其中K是E中的非空紧集， $\tilde{h}$ 是E上的Hausdorff距离。

3) $\forall n=1,2,\cdots$ ， $x_n\in K$ 满足存在 $t_n\in F^n\left(x_n\right)$ ，使得 $\left(\left\{t_n\right\}+\left\{{\epsilon }_n\right\}-cor\left(\mathcal{C}\right)\right)\cap F^n\left(K_n\right)=\varnothing$ ，且当 $n\to \infty$ 时有 $d\left(x_n,K_n\right)\to 0$ ，其中当 $n\to \infty$ 时有 ${\epsilon }_n\ge 0$ ， ${\epsilon }_n\to 0$ 。

则有：

a) $\left\{x_n\right\}$ 必有子序列 $\left\{x_{n_k}\right\}$ ，使 $x_{n_k}\to x_0\in K$ 。

b) $\exists t\in F\left(x_0\right),\text{s}\text{.t}\text{.}\left(\left\{t\right\}-cor\left(\mathcal{C}\right)\right)\cap F\left(K\right)=\varnothing$ 。

c) 若SOP的解集是单点集，则必有 $x_n\to x_0$ 。

证明：

a) $\forall n=1,2,\cdots$ ，由 $d\left(x_n,K_n\right)\to 0\left(n\to \infty \right)$ 得：存在 ${x^{\prime }}_n\in K_n$ ，使 $d\left(x_n,{x^{\prime }}_n\right)\to 0$ 。由于当 $n\to \infty 时$ $\tilde{h}\left(K_n,K\right)\to 0$，且K是一个紧集，根据引理2.2， $\left\{{x^{\prime }}_n\right\}$ 必有子序列 $\left\{{x^{\prime }}_{n_k}\right\}$ 使 ${x^{\prime }}_{n_k}\to x_0\in K$ 。故 $\left\{x_n\right\}$ 必有子序列 $\left\{x_{n_k}\right\}$ ，使 $x_{n_k}\to x_0$ 。

b) 由结论(a)不妨设 $x_n\to x_0$ 。反证：若结论(b)不成立，即：对任何的 $t\in F\left(x\right)$ ，都有 $\left(\left\{t\right\}-cor\left(\mathcal{C}\right)\right)\cap F\left(K\right)\ne \varnothing$ 成立。

由 $\tilde{h}\left(K_n,K\right)\to 0\left(n\to \infty \right)$ ，则存在 $\bar{x}\in K_n\cap K$ ，使得 $\left(\left\{t\right\}-cor\left(\mathcal{C}\right)\right)\cap F\left(\bar{x}\right)\ne \varnothing$ 。

由 $\underset{x\in K}{\sup }\hslash \left(F^n\left(x\right),F\left(x\right)\right)\to 0\left(n\to \infty \right)$ ，F的上半连续性及 $x_n\to x_0$ 可知，对任意的 $\delta >0$ 有：

$t_n\in F^n\left(x_n\right)\subset U\left(\delta ,F\left(x_n\right)\right)\subset U\left(2\delta ,F\left(x_0\right)\right)$ .

又 $F\left(x\right)$ 是紧集，则 $t_n\in F\left(x_0\right)$ ，故满足 $\left(\left\{t_n\right\}-cor\left(\mathcal{C}\right)\right)\cap F\left(\bar{x}\right)\ne \varnothing$ 。进而可得： $\left(\left\{t_n\right\}-cor\left(\mathcal{C}\right)\right)\cap F^n\left(\bar{x}\right)\ne \varnothing$ 。由 ${\epsilon }_n\to 0$ 知： $\hslash \left(\left\{t_n\right\}+\left\{{\epsilon }_n\right\}-cor\left(\mathcal{C}\right),\left\{t_n\right\}-cor\left(\mathcal{C}\right)\right)\to 0\left(n\to \infty \right)$ 。故有 $\left(\left\{t_n\right\}+\left\{{\epsilon }_n\right\}-cor\left(\mathcal{C}\right)\right)\cap F^n\left(\bar{x}\right)\ne \varnothing$ 。这与条件(3)矛盾。因此结论(b)成立，即：

$\exists t\in F\left(x_0\right),\text{s}\text{.t}\text{.}\left(\left\{t\right\}-cor\left(\mathcal{C}\right)\right)F\left(K\right)=\varnothing$ .

c) 利用反证法，假设(c)的结论不成立，即：若SOP的解集是单点集，但 $x_n\nrightarrow x_0$ 。则存在 $\bar{\delta }>0$ 及 $\left\{x_n\right\}$ 的一个子列 $\left\{x_{n_k}\right\}$ ，使 $d\left(x_{n_k},x_0\right)\ge \bar{\delta }$ 。由(a)知： $\left\{x_{n_k}\right\}$ 必有收敛子列，不妨设 $x_{n_k}\to \bar{x}\in K$ ，即： $d\left(x_{n_k},\bar{x}\right)\to 0$ 。由结论(b)知：

$\exists t\in F\left(\bar{x}\right)\text{,}\text{s}\text{.t}\text{.}\left(\left\{t\right\}-cor\left(\mathcal{C}\right)\right)\cap F\left(K\right)=\varnothing$

又SOP的解集是单点集，则有 $x_0=\bar{x}$ 。这与 $d\left(x_{n_k},x_0\right)\ge \bar{\delta }$ 矛盾。故 $x_n\to x_0$ 。

注3.1：定理3.1的结果是很有理论意义的：尽管目标函数是近似的 $\left(F^n\to F\right)$ ，可行解集是近似的 $\left(K_n\to K\right)$ ，求解精度也是近似的 $\left({\epsilon }_n\to 0\right)$ ，但我们可以得到一个近似问题的近似解序列 $\left\{x_n\right\}$ 的收敛子序列 $\left\{x_{n_k}\right\}$ ，并证明了该子序列的极限属于目标函数的解集 $\left(x_{n_k}\to x_0\in K\right)$ 。如果把集值优化问题 $F^n$ 的 ${\epsilon }_n$ -近似弱极小解看作有限理性下的“满意解”，那么集值优化问题的弱极小解 $x_0$ 被视为完全理性下的“精确解”。定理3.1蕴含了集值优化问题的完全理性弱极小解可以用一系列有限理性的近似弱极小解来逼近。

在上述定理中，若 $x_n\in K_n$ ，则结论仍成立，即下述推论3.1：

推论3.1 设 $\left(E,d\right)$ 是一个度量空间， $\mathcal{Z}$ 是一个紧赋范线性空间，且满足下列条件：

1) $\forall n=1,2,\cdots$ ，集值映射序列 $F^n:K\to P_0\left(\mathcal{Z}\right)$ 满足： $\underset{x\in K}{\sup }\hslash \left(F^n\left(x\right),F\left(x\right)\right)\to 0\left(n\to \infty \right)$ ，其中 $F:K\to P_0\left(\mathcal{Z}\right)$ 是上半连续的， $\hslash$ 是 $\mathcal{Z}$ 上的Hausdorff距离。

2) $\forall n=1,2,\cdots$ ， $\left\{K_n\right\}$ 是E中非空子集序列，满足 $\tilde{h}\left(K_n,K\right)\to 0\left(n\to \infty \right)$ ，其中K是E中的非空紧集， $\tilde{h}$ 是E上的Hausdorff距离。

3) $\forall n=1,2,\cdots$ ， $x_n\in K_n$ 满足 $\exists t_n\in F^n\left(x_n\right),\text{s}\text{.t}\text{.}\left(\left\{t_n\right\}+\left\{{\epsilon }_n\right\}-cor\left(\mathcal{C}\right)\right)\cap F^n\left(K_n\right)=\varnothing$ ，其中 ${\epsilon }_n\ge 0$ ， ${\epsilon }_n\to 0$ 。

则有：

a) $\left\{x_n\right\}$ 必有子序列 $\left\{x_{n_k}\right\}$ ，使 $x_{n_k}\to x_0\in K$ 。

b) $\exists t\in F\left(x_0\right),\text{s}\text{.t}\text{.}\left(\left\{t\right\}-cor\left(\mathcal{C}\right)\right)\cap F\left(K\right)=\varnothing$ 。

c) 若SOP的解集是单点集，则必有 $x_n\to x_0$ 。

在定理3.1中，若 $K=K_n\left(n=1,2,\cdots \right)$ ，则结论仍然成立，因此可以得到推论3.2：

推论3.2 设 $\left(E,d\right)$ 是一个度量空间， $\mathcal{Z}$ 是一个紧赋范线性空间，且满足下列条件：

1) $\forall n=1,2,\cdots$ ，集值映射序列 $F^n:K\to P_0\left(\mathcal{Z}\right)$ 满足： $\underset{x\in K}{\sup }\hslash \left(F^n\left(x\right),F\left(x\right)\right)\to 0\left(n\to \infty \right)$ ，

其中 $F:K\to P_0\left(\mathcal{Z}\right)$ 是上半连续的， $\hslash$ 是 $\mathcal{Z}$ 上的Hausdorff距离。

2) K是E中的非空紧集。

3) $\forall n=1,2,\cdots$ ， $x_n\in K$ 是SOP的一个 ${\epsilon }_n$ -近似若极小解序列，满足 $\exists t_n\in F^n\left(x_n\right),\text{s}\text{.t}\text{.}$ $\left(\left\{t_n\right\}+\left\{{\epsilon }_n\right\}-cor\left(\mathcal{C}\right)\right)\cap F^n\left(K\right)=\varnothing$ ，其中 ${\epsilon }_n\ge 0$ ， ${\epsilon }_n\to 0\left(n\to \infty \right)$ 。

则有：

a) $\left\{x_n\right\}$ 必有子序列 $\left\{x_{n_k}\right\}$ ，使 $x_{n_k}\to x_0\in K$ 。

b) $\exists t\in F\left(x_0\right),\text{s}\text{.t}\text{.}\left(\left\{t\right\}-cor\left(\mathcal{C}\right)\right)\cap F\left(K\right)=\varnothing$ 。

c) 若SOP的解集是单点集，则必有 $x_n\to x_0$ 。

注3.2：在定理3.1以及以上两个推论中，对目标函数 $F^n$ 没有任何连续性的要求，对可行解集 $K_n$ 更没有任何闭性或紧性的要求，这表明该定理的条件较弱，应用更具有普遍性。

4. 结论

本文利用有限理性的思想讨论了集值优化问题逼近定理，我们给出了集值优化问题的逼近定理和两个推论，并证明了在一定假设条件下，集值优化问题的弱极小解可以用有限理性来逼近完全理性，为集值优化问题的算法研究提供了基础。