经典的数学规划是在已知准确数据的条件下建立模型,并利用优化方法求解.但在实际生活中,优化模型往往受到各种因素的影响,许多问题带有不确定信息.特别在解决具体应用问题时,往往受制于未知参数影响,因此存在这样的风险:实际参数值偏离估计的参数值,则优化的解决方案可能是次优的或甚至是不可行的.因此,不确定优化问题引起了大家的广泛关注.鲁棒优化是处理不确定优化问题的有效方法之一,它是在满足约束条件下,对于可能出现的所有情况,以求出最坏情况下目标函数值最优为目的.本文所研究的内容就是用鲁棒优化方法处理不确定优化问题.

鲁棒优化问题可追溯到20世纪70年代^[1],并在90年代末得到飞速发展.自进入21世纪之后,越来越多的学者加入到鲁棒优化问题的研究中,从而使得鲁棒优化在理论、方法及其应用方面的到了空前的发展^[2-3].最优性条件和对偶理论是鲁棒优化研究的两个主要内容,例如:文献[4-5]借助一类鲁棒次微分约束品性,刻画了不确定凸优化问题的鲁棒最优解,并得到了相应的Wolfe型鲁棒对偶定理.众所周知,数学规划的模型一般都是实际问题的简化表示,利用数值算法求得的解大多是近似解.因此研究近似解不仅有理论价值而且有实际意义.最近, Lee和Jiao^[6]在闭凸锥约束品性假设下,利用鲁棒优化方法研究了不确定凸优化问题的拟近似解,得到了相应的近似最优性条件和对偶定理;文献[7]对不确定多目标凸优化问题,研究了鲁棒近似弱有效解的最优性条件及Wolfe型和Mond-Weir型鲁棒对偶定理.另外,鞍点定理也是最优化问题研究的最主要的内容之一.文献[8]在一定的凸性条件下,得到了不确定多目标优化问题鲁棒弱有效解的鞍点刻划.本文是对鲁棒优化问题近似解的进一步研究,我们将在文献[6]中所用的约束品性下,讨论鲁棒近似解的最优性条件和鞍点定理.

本文内容安排如下:第2节,约定本文所用符号,并给出要用到的定义和引理;第3节,在闭凸锥约束品性假设下,建立鲁棒凸优化问题关于近似解的最优性条件;第4节,定义鲁棒近似鞍点的概念,并给出所研究的不确定凸优化问题鲁棒近似解的鞍点定理.

本文用$ {{\Bbb R}} ^{n} $表示$ n $维Euclid空间,对任意的$ x, y\in {{\Bbb R}} ^{n} $,用$ \langle x, y\rangle $表示$ x $和$ y $之间的内积.集合$ A\subset {{\Bbb R}} ^{n} $称之为凸集是指:对任意的$ \mu\in [0, 1] $, $ a_{1}, a_{2}\in A $,满足

(2.1) $\mu a_{1}+(1-\mu)a_{2}\in A.$

集合$ A $的闭包和凸包分别记为$ \mbox{cl}(A) $和$ \mbox{co}(A) $.令$ f :{{\Bbb R}} ^{n}\longrightarrow {{\Bbb R}} \bigcup \{+\infty\} $为一扩充实值函数, $ f $的有效域和上图分别定义为

$ \mbox{dom} (f): = \{x\in {{\Bbb R}} ^{n}|\ f(x)<+\infty\}, \nonumber $

$ \mbox{epi} (f): = \{(x, r)\in {{\Bbb R}} ^{n}\times {{\Bbb R}} \ |\ f(x)\leq r\}.\nonumber $

若$ \mbox{dom} (f)\neq \emptyset $,则称$ f $为真函数.如果对任意的$ x, y\in {{\Bbb R}} ^{n}, \mu\in [0, 1] $,有

$ f((1-\mu)x+\mu y)\leq(1-\mu)f(x)+\mu f(y), \nonumber $

则称$ f $为凸函数. $ f $为凸函数等价于$ \mbox{epi} (f) $是凸集.称$ f $是凹函数,如果$ -f $是凸函数.令$ f:{{\Bbb R}} ^{n}\rightarrow {{\Bbb R}} \cup \{+\infty\} $为凸函数,当$ x\in \mbox{dom} (f) $时,函数$ f $在$ x $的次微分定义为

$ \partial f(x) = \{x^{\ast}\in {{\Bbb R}} ^{n}|\ f(y)-f(x)\geq \langle x^{\ast}, y-x\rangle, \ \forall y\in {{\Bbb R}} ^{n}\}, \nonumber $

对任意的$ \varepsilon\geq0 $,函数$ f $在$ x $的$ \varepsilon $-次微分定义为

$ \partial_{\varepsilon}f(x) = \{x^{\ast}\in {{\Bbb R}} ^{n}|\ f(y)-f(x)+\varepsilon \geq \langle x^{\ast}, y-x\rangle, \ \forall y\in {{\Bbb R}} ^{n} \}.\nonumber $

对任意的$ x^{\ast}\in {{\Bbb R}} ^{n} $, $ f $的共轭函数$ f^{\ast}:{{\Bbb R}} ^{n}\rightarrow {{\Bbb R}} \cup \{+\infty\} $定义为

$ f^{\ast}(x^{\ast}) = \mbox{sup} \ \{\langle x^{\ast}, x\rangle-f(x)\ | \ x\in {{\Bbb R}} ^{n}\}.\nonumber $

文献[9-10]给出共轭函数的上图及函数的$ \varepsilon $ -次微分具有下面两个重要性质,它们在证明本文主要结果中起关键作用.

引理2.1^[9]  假设$ f: {{\Bbb R}} ^{n}\rightarrow {{\Bbb R}} \cup \{+\infty\} $是一个真下半连续函数, $ x\in {\rm dom}(f) $, $ \varepsilon\geq 0 $,则有

$ {\rm epi} (f^{\ast}) = \bigcup\limits_{\varepsilon\geq 0}\{(p, \langle p, x \rangle+\varepsilon-f(x)) \ | \ v\in \partial_{\varepsilon}f(x)\}.\nonumber $

引理2.2^[10]  令$ f_{1}, f_{2}: {{\Bbb R}} ^{n}\rightarrow {{\Bbb R}} \cup \{+\infty\} $为真凸函数,且$ {\rm dom} (f_{1})\cap {\rm dom} (f_{2})\neq \emptyset $.

(1)如果$ f_{1} $和$ f_{2} $是下半连续函数,则有

$ {\rm epi} \ (f_{1}+f_{2})^{\ast} = \mbox{cl} \ ({\rm epi} \ (f_{1}^{\ast})+{\rm epi} \ (f_{2}^{\ast})).\nonumber $

(2)如果$ f_{1} $和$ f_{2} $至少有一个在$ \bar{x}\in {\rm dom}(f_{1})\cap {\rm dom}(f_{2}) $连续,则有

$ {\rm epi} \ (f_{1}+f_{2})^{\ast} = {\rm epi} ( f_{1}^{\ast})+{\rm epi} ( f_{2}^{\ast}).\nonumber $

注2.1^[7]  令$ p\in {{\Bbb R}} ^{n} $,由Lisz表示定理, $ p $可视为$ {{\Bbb R}} ^{n} $的线性函数,定义为$ p(x) = \langle p, x\rangle $, $ x\in {{\Bbb R}} ^{n} $.设函数$ f: {{\Bbb R}} ^{n}\rightarrow {{\Bbb R}} \cup \{+\infty\} $,则对任意的$ p\in {{\Bbb R}} ^{n} $以及$ \alpha\in {{\Bbb R}} $,有

(2.2) $ \begin{equation} (f+p+\alpha)^{\ast}(x^{\ast}) = f^{\ast}(x^{\ast}-p)-\alpha, \ \ \forall x^{\ast}\in {{\Bbb R}} ^{n}, \end{equation} $

并且

(2.3) $ \begin{equation} {\rm epi} \ (f+p+\alpha)^{\ast} = {\rm epi}(f^{\ast})+(p, -\alpha). \end{equation} $

本文考虑如下凸优化问题

$ \mbox{(P)}\ \ \ \ \ \ \left\{\begin{array}{ll} \min \ f(x) \ \ \\ {\rm s.t.} \ x\in C, \mbox{ }g_{i}(x)\leq0, & \ \ i = 1, \cdots, m, \\ \end{array}\right. \nonumber $

其中$ C\subset {{\Bbb R}} ^{n} $为非空闭凸集, $ f, g_i : {{\Bbb R}} ^{n}\longrightarrow {{\Bbb R}} $, $ i = 1, \cdots , m $是连续的凸函数.若问题(P)的目标函数和约束条件中含有不确定性数据,则问题(P)变为如下的不确定优化问题(UP)表示为

$ \mbox{(UP)}\ \ \ \ \ \ \left\{\begin{array}{ll} \min \ f(x, u)& \\ {\rm s.t.} \ x\in C, \mbox{ }g_{i}(x, v_{i})\leq0, & \ \ i = 1, \cdots, m, \\ \end{array}\right. \nonumber $

其中$ u $和$ v_{i} $是不确定参数,且分别属于紧凸集$ U\subset {{\Bbb R}} ^{p} $和$ V_{i}\subset{{\Bbb R}} ^{q}, i = 1, \cdots , m $.本文总假设$ f : {{\Bbb R}} ^{n}\times {{\Bbb R}} ^{p}\longrightarrow {{\Bbb R}} $, $ g_{i}: {{\Bbb R}} ^{n}\times {{\Bbb R}} ^{q}\rightarrow {{\Bbb R}} $, $ i = 1, \cdots , m $是连续的,且均关于第一个变量$ x $是凸函数,也即是:对于任意的$ u\in U, v_{i}\in V_{i}, i = 1, \cdots , m $, $ f(\cdot, u) $和$ g_{i}(\cdot, v_{i}) $是凸函数.

下面引入问题(UP)的鲁棒对应(robust counterpart)

$ \mbox{(RUP)}\ \ \ \ \ \ \left\{\begin{array}{ll} \mbox{}\min \psi(x) \\ {\rm s.t.} \ x\in C, \mbox{ }g_{i}(x, v_{i})\leq0, & \ v_{i}\in V_{i}, \ i = 1, \cdots, m, \ \ \ \end{array}\right. \nonumber $

其中$ { } \psi(x): = \max \limits_{u\in U} f(x, u), $称鲁棒对应(RUP)为鲁棒优化问题.问题(RUP)的可行集记为

$ {\cal F}: = {\{x\in C\ |\ g_{i}(x, v_{i})\leq0, \ \forall v_{i}\in V_{i}, i = 1, \cdots, m }\}, \nonumber $

本文总假设鲁棒优化问题(RUP)的可行集$ {\cal F} $为非空集,显然$ {\cal F} $为凸集.

定义2.1^[11]  在问题(RUP)中,如果

(2.4) $ \begin{equation} \bigcup\limits_{v_{i}\in V_{i}, \lambda_{i}\geqq0} {\rm epi}\ \Big(\sum\limits_{i = 1}^{m}\lambda_{i}g_{i}(\cdot, v_{i})\Big)^{\ast} \end{equation} $

是闭凸锥,称鲁棒优化问题(RUP)满足闭凸锥约束品性.

定义2.2^[7]  令$ \varepsilon\geq0, \ \bar{x}\in {\cal F} $.

$ \rm(a) $称$ \bar{x} $是问题(UP)的鲁棒$ \varepsilon $ -最优解,如果$ \bar{x} $是问题(RUP)的$ \varepsilon $ -最优解,即

$ \max \limits_{u\in U} f(\bar{x}, u)\leq \max \limits_{u\in U}f(x, u)+\varepsilon\nonumber, \ \forall x\in {\cal F}, $

$ \rm(b) $称$ \bar{x} $是问题(UP)的鲁棒最优解,当且仅当$ \bar{x} $是问题(RUP)的最优解,即

$ \max \limits_{u\in U} f(\bar{x}, u)\leq\max \limits_{u\in U} f(x, u) \nonumber, \ \forall x\in {\cal F}. $

下面给出凸函数的鲁棒形式的Farkas定理,本文将用此定理建立问题(RUP)鲁棒最优性条件.

引理2.3^[12]  令$ \phi : {{\Bbb R}} ^{n}\rightarrow {{\Bbb R}} $是一凸函数, $ g_{i} :{{\Bbb R}} ^{n}\times {{\Bbb R}} ^{q}\rightarrow {{\Bbb R}}, \; i = 1, \cdots , m $是关于第一个变量的连续凸函数.令$ V_{i}\subseteq {{\Bbb R}} ^{q} $是紧集, $ \ i = 1, \cdots, m $.则下面两个陈述等价

$ \rm(i) $$ \{x\in {{\Bbb R}} ^{n} \ | \ g_{i}(x, v_{i})\leq0, \ \forall v_{i}\in V_{i}, i = 1, \cdots, m\}\subset\{x\in {{\Bbb R}} ^{n} \ | \ \phi(x)\geq0\} $;

$ \rm(ii) $$ (0, 0)\in {\rm epi} \; \phi^{\ast}+{\rm cl}\Big({\rm co}\bigcup\limits_{v_{i}\in V_{i}, \lambda_{i}\geq0}{\rm epi} \big(\sum\limits^{m}_{i = 1}\lambda_{i}g_{i}(\cdot, v_{i})\big)^{\ast}\Big) $.

本节将在闭凸锥约束品性假设下,利用凸函数的鲁棒形式的Farkas定理(引理2.3),建立鲁棒优化问题(RUP)的近似最优性条件.本文以下总假设$ \varepsilon\geq0 $.

定理3.1  在问题(UP)中,令$ \overline{x}\in {\cal F} $.若问题(RUP)满足闭凸锥约束品性,则下面两个结论等价

$ \rm(i) $$ \bar{x} $是(UP)的鲁棒$ \varepsilon $ -解;

$ \rm(ii) $对于任意的$ x\in {{\Bbb R}} ^{n}, $存在$ \bar{\lambda}_{i}\geq0, \bar{v_{i}}\in V_{i}, i = 1, \cdots , m $,使得

(3.1) $ \begin{equation} \max \limits_{u\in U} f(\bar{x}, u)\leq\max \limits_{u\in U} f(x, u)+\sum\limits_{i = 1}^{m}\bar{\lambda}_{i}g_{i}(x, \bar{v_{i}})+\varepsilon. \end{equation} $

证  首先证明(ⅰ)$ \Rightarrow $(ⅱ).假设$ \bar{x} $是(UP)的鲁棒$ \varepsilon $ -解,则有

$ \max \limits_{u\in U}f(\bar{x}, u)\leq\max \limits_{u\in U} f(x, u)+\varepsilon, \ \forall x\in {\cal F}, \nonumber $

因此

$ {\cal F}\subseteq\{x\in {{\Bbb R}} ^{n} \ | \max \limits_{u\in U} f(x, u)+\varepsilon-\max \limits_{u\in U} f(\bar{x}, u)\geq0\}. $

对于任意的$ x\in {{\Bbb R}} ^{n} $,令

$ \phi(x) = \psi(x)+\varepsilon-\psi(\bar{x}), $

其中$ { } \psi(x) = \max \limits_{u\in U} f(x, u), $显然$ \phi $是$ {{\Bbb R}} ^{n} $上的凸函数.由引理2.3,可知

$ (0, 0)\in {\rm epi}\phi^{\ast}+\mbox{cl}\Big(\mbox{co}\bigcup\limits_{v_{i}\in V_{i}, \lambda_{i}\geq0}{\rm epi} \big(\sum\limits^{m}_{i = 1}\lambda_{i}g_{i}(\cdot, v_{i})\big)^{\ast}\Big). \nonumber $

又因问题(UP)满足鲁棒型闭凸锥约束品性,所以有

$ (0, 0)\in {\rm epi}\phi^{\ast}+\bigcup\limits_{v_{i}\in V_{i}, \lambda_{i}\geq0}{\rm epi} \Big(\sum\limits^{m}_{i = 1}\lambda_{i}g_{i}(\cdot, v_{i})\Big)^{\ast}. \nonumber $

因此,存在$ \bar{\lambda}_{i}\geq0, \bar{v_{i}}\in V_{i}, i = 1, \cdots, m, $使得

(3.2) $ \begin{equation} (0, 0)\in {\rm epi}\phi^{\ast}+{\rm epi}\Big(\sum\limits_{i = 1}^{m}\bar{\lambda}_{i}g_{i}(\cdot, \bar{v}_{i})\Big)^{\ast}. \end{equation} $

另外,由引理2.2,可知

$ {\rm epi}\phi^{\ast} = {\rm epi}(\psi(x)+\varepsilon-\psi(\bar{x}))^{\ast} = {\rm epi}\psi^{\ast}+{\rm epi}(\varepsilon-\psi(\bar{x}))^{\ast}.\nonumber $

因为

$ \mbox{}(\varepsilon-\psi(\bar{x}))^{\ast}(x) = \ \left\{\begin{array}{ll} \mbox{} \psi(\bar{x})-\varepsilon, & \ \ \|x\| = 0, \\ \mbox{ }+\infty, & \ \ \mbox{其他}, \\ \end{array}\right. \nonumber $

所以

$ {\rm epi}\phi^{\ast} = {\rm epi}\psi^{\ast}+\{0\}\times [\psi(\bar{x})-\varepsilon, +\infty).\nonumber $

再由(3.2)式,可得

(3.3) $ \begin{equation} (0, \varepsilon-\psi(\bar{x}))\in {\rm epi}\psi^{\ast}+{\rm epi}\Big( \sum\limits_{i = 1}^{m}\bar{\lambda}_{i}g_{i}(\cdot, \bar{v}_{i})\Big)^{\ast}+\{0\} \times {{\Bbb R}} _{+}. \end{equation} $

因此,存在$ p\in {{\Bbb R}} ^{n}, \ \varepsilon^{\prime}\geq0, \ p_{i}\in {{\Bbb R}} ^{n}, \ \varepsilon_{i}^{\prime}\geq0, \ i = 1, \cdots , m, r\in {{\Bbb R}} _{+} $,使得

$ (0, \varepsilon-\psi(\bar{x})) = (p, \psi^{\ast}(p)+\varepsilon^{\prime})+\sum\limits_{i = 1}^{m}\bar{\lambda}_{i}(p_{i}, g_{i}^{\ast}(p_{i}, \bar{v}_{i})+\varepsilon_{i}^{\prime})+(0, r).\nonumber $

故有

$ 0 = p+\sum\limits_{i = 1}^{m}\bar{\lambda}_{i}p_{i}, $

$ \varepsilon-\psi(\bar{x}) = \psi^{\ast}(p)+\varepsilon^{\prime}+\sum\limits_{i = 1}^{m}\bar{\lambda}_{i}(g_{i}^{\ast}(p_{i}, \bar{v}_{i}+\varepsilon_{i}^{\prime})+r. $

所以,对于任意的$ x\in {{\Bbb R}} ^{n} $,有

$ \begin{eqnarray*} -\langle\sum\limits_{i = 1}^{m}\bar{\lambda}_{i}p_{i}, x\rangle-\psi(x)& = &\langle p, x\rangle-\psi(x) \nonumber\\ &\leq &\psi^{\ast}(p) \nonumber\\ & = &\varepsilon-\psi(\bar{x})-\varepsilon^{\prime}-\sum\limits_{i = 1}^{m}\bar{\lambda}_{i}(g_{i}^{\ast}(p_{i}, \bar{v}_{i}+\varepsilon_{i}^{\prime})-r, \nonumber \end{eqnarray*} $

由此可得

$ \begin{eqnarray*} \psi(\bar{x})&\leq&\langle\sum\limits_{i = 1}^{m}\bar{\lambda}_{i}p_{i}, x\rangle+\psi(x)+\varepsilon-\varepsilon^{\prime}-\sum\limits_{i = 1}^{m}\bar{\lambda}_{i}g_{i}^{\ast}(p_{i}, \bar{v}_{i})-\sum\limits_{i = 1}^{m}\bar{\lambda}_{i}\varepsilon_{i}^{\prime}-r \nonumber\\ &\leq&\langle\sum\limits_{i = 1}^{m}\bar{\lambda}_{i}p_{i}, x\rangle+\psi(x)+\varepsilon-\varepsilon^{\prime}-\sum\limits_{i = 1}^{m}\bar{\lambda}_{i}g_{i}^{\ast}(p_{i}, \bar{v}_{i})\nonumber\\ &\leq&\psi(x)+\varepsilon+\langle\sum\limits_{i = 1}^{m}\bar{\lambda}_{i}p_{i}, x\rangle-\sum\limits_{i = 1}^{m}\bar{\lambda}_{i}g_{i}^{\ast}(p_{i}, \bar{v}_{i})\nonumber\\ &\leq &\psi(x)+\varepsilon+\sum\limits_{i = 1}^{m}\bar{\lambda}_{i}g_{i}(x, \bar{v}_{i}), \nonumber \end{eqnarray*} $

这就证明了(eq:a4)式.

下证(ⅱ)$ \Rightarrow $(ⅰ).假设存在$ \bar{\lambda}_{i}\geq0, \ \bar{v}_{i}\in V_{i}, \ i = 1, \cdots , m $,使得

$ \psi(\bar{x})\leq \psi(x)+\sum\limits_{i = 1}^{m}\bar{\lambda}_{i}g_{i}(x, \bar{v}_{i})+\varepsilon, \forall x\in {{\Bbb R}} ^{n}, $

且

$ \sum\limits_{i = 1}^{m}\bar{\lambda}_{i}g_{i}(x, \bar{v}_{i})\leq 0, \ \forall x\in {\cal F}. $

因此,有

$ \psi(\bar{x})\leq\psi(x)+\varepsilon+\sum\limits_{i = 1}^{m}\bar{\lambda}_{i}g_{i}(x, \bar{v}_{i})\leq\psi(x)+\varepsilon, \forall x\in {\cal F}.\nonumber $

也即

$ \psi(\bar{x})\leq\psi(x)+\varepsilon, $

由此可知$ \bar{x} $是问题(RUP)的$ \varepsilon $ -解.

定理3.2  对于问题(UP),令$ \bar{x}\in {\cal F} $.若问题(RUP)满足闭凸锥约束品性,则下面两个结论等价

$ \rm(i) $$ \bar{x} $是问题(UP)的鲁棒$ \varepsilon $ -解;

$ \rm(ii) $存在$ \bar{v}_{i}\in V_{i}, \ \bar{\lambda}_{i}\geq0, i = 1, \cdots , m, \varepsilon_{j}\geq0, j = 1, 2, r\geq0 $,使得

(3.4) $ \begin{equation} 0\in \partial_{\varepsilon_{1}}\psi(\bar{x})+\partial_{\varepsilon_{2}}\Big(\sum\limits_{i = 1}^{m}(\bar{\lambda}_{i} g_{i})(\cdot, \bar{v}_{i})\Big)(\bar{x}), \end{equation} $

并且

(3.5) $ \begin{equation} \varepsilon_{1}+\varepsilon_{2}-\varepsilon = \sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\bar{x}, \bar{v}_{i})-r. \end{equation} $

证  首先证明(i)$ \Rightarrow $(ii).假设$ \bar{x} $是问题(UP)的鲁棒$ \varepsilon $ -解,根据定理3.1证明过程,可知存在$ \bar{v}_{i}\in V_{i}, \; \bar{\lambda}_{i}\geq0, $使得式(eq:a6)成立,也即

$ (0, \varepsilon-\psi(\bar{x}))\in {\rm epi}\psi^{\ast}(x)+{\rm epi}\Big(\sum\limits_{i = 1}^{m}\bar{\lambda}_{i}g_{i}(\cdot, \bar{ v}_{i})\Big)^{\ast}+\{0\}\times {{\Bbb R}} _{+}.\nonumber $

因此,存在$ (u^{\ast}, t)\in {\rm epi}\psi^{\ast}(x), (v^{\ast}_{i}, s_{i})\in {\rm epi}(\bar{\lambda}_{i}g_{i}(\cdot, \bar{v}_{i}))^{\ast}, \; i = 1, \cdots , m, \; r\in {{\Bbb R}} _{+} $,使得

(3.6) $ \begin{equation} u^{\ast}+\sum\limits_{i = 1}^{m}v_{i}^{\ast} = 0, \end{equation} $

(3.7) $ \begin{equation} t+\sum\limits_{i = 1}^{m}s_{i}+r = \varepsilon-\psi(\bar{x}). \end{equation} $

由共轭函数上图的定义可知，存在$ \varepsilon_{j}\geq0, \; j = 1, 2, $使得

$ u^{\ast}\in \partial_{\varepsilon_{1}}\psi(\bar{x}), \; t = \langle u^{\ast}, \bar{x}\rangle+\varepsilon_{1}-\psi(\bar{x}), \nonumber $

$ v_{i}^{\ast}\in \partial_{\varepsilon_{2}}(\bar{\lambda}_{i}g_{i}(\cdot, \bar{v}_{i}))(\bar{x}), s_{i} = \langle v_{i}^{\ast}, \bar{x}\rangle+\varepsilon_{2}-\bar{\lambda}_{i}g_{i}(\bar{x}, \bar{v}_{i}), \\ \; i = 1, \cdots , m.\nonumber $

由(3.6)和(3.7)两式可得

$ 0\in \partial_{\varepsilon_{1}}\psi(\bar{x})+\partial_{\varepsilon_{2}}\Big(\sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\cdot, \bar{v}_{i})\Big)(\bar{x}), \nonumber $

$ \varepsilon-\psi(\bar{x}) = t+\sum\limits_{i = 1}^{m}s_{i}+r = \langle u^{\ast}+\sum\limits_{i = 1}^{m}v_{i}^{\ast}, \bar{x}\rangle+\varepsilon_{1}+\varepsilon_{2}-\psi(\bar{x})-\sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\bar{x}, \bar{v}_{i})+r.\nonumber $

由此可得

$ \varepsilon_{1}+\varepsilon_{2}-\varepsilon = \sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\bar{x}, \bar{v}_{i})-r.\nonumber $

因此, (3.4)和(3.5)式成立.

下面证明(ⅱ)$ \Rightarrow $(ⅰ).假设存在$ \bar{v}_{i}\in V_{i}, \ \bar{\lambda}_{i}\geq0, i = 1, \cdots , m, \varepsilon_{j}\geq0, \ j = 1, 2 $,使得(3.4)和(3.5)式成立.所以存在$ u^{\ast}\in \partial_{\varepsilon_{1}}\psi(\bar{x}), \; v_{i}^{\ast}\in \partial_{\varepsilon_{2}}((\bar{\lambda}_{i}g_{i})(\cdot, \; \; \bar{v}_{i}))(\bar{x}), $使得

$ u^{\ast}+\sum\limits_{i = 1}^{m}v_{i}^{\ast} = 0.\nonumber $

因此,对任意的$ x\in {\cal F} $,有

$ \psi(x)-\psi(\bar{x})\geq\langle u^{\ast}, x-\bar{x}\rangle-\varepsilon_{1}, \nonumber $

$ \sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(x, \bar{v}_{i})-\sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\bar{x}, \bar{v}_{i})\geq\langle \sum\limits_{i = 1}^{m}v_{i}^{\ast }, x-\bar{x}\rangle-\varepsilon_{2}.\nonumber $

上面两式相加得

$ \psi(x)-\psi(\bar{x})+\sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(x, \bar{v}_{i})-\sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\bar{x}, \bar{v}_{i})\geq\langle u^{\ast}+ \sum\limits_{i = 1}^{m}v_{i}^{\ast }, x-\bar{x}\rangle-\varepsilon_{1}-\varepsilon_{2}.\nonumber $

注意到对任意的$ x\in {\cal F}, $有$ \sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(x, \bar{v}_{i})\leq0 $,再根据(3.6)式,可得

$ \psi(x)-\psi(\bar{x})-\sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\bar{x}, \bar{v}_{i})\geq-\varepsilon_{1}-\varepsilon_{2}. \nonumber $

再由

$ \varepsilon_{1}+\varepsilon_{2}-\varepsilon = \sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\bar{x}, \bar{v}_{i})-r.\nonumber $

有

$ \psi(x)+\varepsilon\geq \psi(\bar{x})+r. \nonumber $

又因为$ r\geq0, $所以

$ \psi(x)\geq\psi(\bar{x})-\varepsilon, \nonumber $

由此可知, $ \bar{x} $是问题(UP)的鲁棒$ \varepsilon $ -解.

下面给出一具体实例验证定理3.2的结论.

令$ f : {{\Bbb R}} ^{2}\times {{\Bbb R}} \rightarrow {{\Bbb R}}, \; g : {{\Bbb R}} ^{2}\times {{\Bbb R}} \rightarrow{{\Bbb R}} , \; U = [-1, 0], V = [-1, 1] $,对于任意的$ x = (x_{1}, x_{2})\in {{\Bbb R}} ^{2}, $定义以下函数

$ f(x, u) = x_{1}+2x_{2}^{2}+u, \ \ \ g(x, v) = x_{1}^{2}-vx_{1}, \nonumber $

其中, $ u\in U, v\in V $为不确定参数,显而易见,上述定义的$ f, g $均关于第一个变量$ x $是凸函数,考虑如下形式的鲁棒凸优化问题

$ \mbox{(RUP)}^{1}\ \ \ \ \ \ \left\{\begin{array}{ll} \mbox{}\min \max \limits_{u\in U} f(x, u) = x_{1}+2x_{2}^{2} \\ {\rm s.t.} \mbox{ }x_{1}^{2}-vx_{1}\leq0, \ v\in V.\ \ \ \end{array}\right. \nonumber $

显然

$ \psi(x) = \max \limits_{u\in U} f(x, u) = x_{1}+2x_{2}^{2}. \nonumber $

问题(RUP)$ ^{1} $可行集为

$ {\cal F}^{1} = \{(x_{1}, x_{2})\in {{\Bbb R}} ^{2}: x_{1}^{2}-vx_{1}\leq0, v\in [-1, 1] \} = \{(x_{1}, x_{2})\in {{\Bbb R}} ^{2}: x_{1} = 0, x_{2}\in {{\Bbb R}} \}.\nonumber $

令$ \bar{x} = (0, 0)\in {\cal F}, \; \varepsilon = 1 $,可知(0, 0)是问题(UP)的一个鲁棒最优解,令$ \varepsilon_{1} = \varepsilon_{2} = \frac{1}{2}, v = 1, $$ \lambda = \frac{1}{2} $,可得

$ \partial_{\varepsilon_{1}}\psi(\bar{x}) = \{1\}\times [-\sqrt{2}, \sqrt{2}], \nonumber $

$ \partial_{\varepsilon_{2}}\sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\cdot, \bar{v})(\bar{x}) = [-2, 0]\times \{0\}.\nonumber $

上面两式相加可得

$ \partial_{\varepsilon_{1}}\psi(\bar{x})+\partial_{\varepsilon_{2}}\sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\cdot, \bar{v})(\bar{x}) = [-3, 1]\times[-\sqrt{2}, \sqrt{2}].\nonumber $

可知, $ \bar{x} $是问题(UP)的鲁棒$ \varepsilon $ -解.

注3.1  一些文献也对鲁棒优化问题近似解的最优性套条件进行了研究,例如文献[4],这些文献所讨论所讨论的模型通常只是在约束函数中含有不确定数据.本文证明了问题(UP)的鲁棒$ \varepsilon $ -解的最优性条件,模型(RUP)中目标函数与约束均含不确定参数.

本节建立了不确定凸优化问题(UP)的$ \varepsilon $ -弱鞍点定理.设$ x\in {{\Bbb R}} ^{n}, \; v\in V, \; \lambda\geq0, $定义以下形式的拉格朗日函数

$ L(x, v, \lambda) = f(x)+\lambda^{T}g(x, v).\nonumber $

定义4.1  令$ x\in {{\Bbb R}} ^{n}, \; v\in V, \; \lambda\geq0, $若

$ L(x, \bar{v}, \bar{\lambda})+\varepsilon\geq L(\bar{x}, \bar{v}, \bar{\lambda})\geq L(\bar{x}, v, \lambda)-\varepsilon, \nonumber $

称$ (\bar{x}, \bar{v}, \bar{\lambda})\in {{\Bbb R}} ^{n}\times {{\Bbb R}} ^{m}_{+}\times V $为拉格朗日函数的$ \varepsilon $ -弱鞍点.

注4.1  若$ \varepsilon = 0, \varepsilon $ -弱鞍点退化为^[13]研究的广义拉格朗日鞍点.

下面给出实例验证定义4.1.

令$ U = [1, 2] $, $ V = [-1, 1] $,分别定义$ f : {{\Bbb R}} ^{2}\rightarrow {{\Bbb R}}, \; g : {{\Bbb R}} ^{2}\times {{\Bbb R}} \rightarrow {{\Bbb R}} $,

$ f(x, u) = x_{1}+2x_{2}^{2}-2u, \ \ g(x, v) = x_{1}^{2}-vx_{1}.\nonumber $

其中$ x: = (x_{1}, x_{2})\in {{\Bbb R}} ^{2}, $且$ u\in U, v\in V $为不确定参数,显而易见,上述定义的$ f, g $均关于第一个变量$ x $是凸函数,考虑如下形式的鲁棒凸优化问题

$ \mbox{(RUP)}^{2}\ \ \ \ \ \ \left\{\begin{array}{ll} \mbox{}\min \max \limits_{u\in U} f(x, u) = x_{1}+2x_{2}^{2}-2u \\ {\rm s.t.} \mbox{ }x_{1}^{2}-vx_{1}\leq0, \ v\in [-1, 1].\ \ \ \end{array}\right. \nonumber $

显然

$ \max \limits_{u\in U} f(x, u) = x_{1}+2x_{2}^{2}-2, \nonumber $

问题(RUP)$ ^{2} $的可行集为

$ {\cal F}^{2} = \{(x_{1}, x_{2})\in {{\Bbb R}} ^{2}: x_{1}^{2}-vx_{1}\leq0, v\in [-1, 1] \} = \{(x_{1}, x_{2})\in {{\Bbb R}} ^{2} \ | \ x_{1} = 0, x_{2}\in {{\Bbb R}} ^{2}\}. $

令$ \bar{x} = (0, 0), \; \bar{v} = 1, \; \bar{\lambda} = 1, \; \varepsilon = 1, $对任意的$ x\in {\cal F}, $有

$ L(x, v, \lambda) = x_{1}^{2}+x_{1}-vx_{1}+2x_{2}^{2}, \nonumber $

通过定义4.1,对任意的$ x\in {{\Bbb R}}, $$ \lambda\in {{\Bbb R}} _{+}^{m}, $得

$ L(\bar{x}, v, \lambda)-\varepsilon = -1\leq L(\bar{x}, \bar{v}, \bar{\lambda}) = 0, \nonumber $

$ L(\bar{x}, \bar{v}, \bar{\lambda}) = 0\leq L(x, \bar{v}, \bar{\lambda})+\varepsilon = x_{1}^{2}+2x_{2}^{2}+1.\nonumber $

即$ (\bar{x}, \bar{v}, \bar{\lambda})\in {{\Bbb R}} ^{n}\times {{\Bbb R}} _{+}^{m}\times V $是问题(RUP)的$ \varepsilon $ -鞍点.

定理4.1  假设$ \bar{x} $是问题(RUP)的$ \varepsilon $ -解,且满足定理3.2,则称$ L(\bar{x}, \bar{v}, \bar{\lambda}) $是问题(RUP)的$ \varepsilon $ -弱鞍点.

证  假设(3.4)和(3.5)式成立,那么存在$ \bar{v}_{i}\in V_{i} $, $ \bar{\lambda}_{i}\in {{\Bbb R}} _{+}^{m}, i = 1, \cdots , m, $使得

$ 0\in\partial_{\varepsilon_{1}}\psi(x)+\partial_{\varepsilon_{2}}\sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\cdot, \bar{v}_{i})(\bar{x}), \nonumber $

$ r+\varepsilon_{1}+\varepsilon_{2}-\varepsilon = \sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\bar{x}, \bar{v}_{i}), \\i = 1, \cdot \cdot \cdot, m. \nonumber $

令$ x\in{{\Bbb R}} ^{n}, \eta\in \partial_{\varepsilon_{1}}\psi(x), \zeta\in\partial_{\varepsilon_{2}} \sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\cdot, \bar{v}_{i})(\bar{x}), i = 1, \cdot \cdot \cdot, m, $使得

$ \begin{equation} 0 = \eta+\zeta. \end{equation} $

由$ \varepsilon $ -次微分定义有

$ \psi(x)-\psi(\bar{x})\geq\langle \eta, x-\bar{x}\rangle-\varepsilon_{1}, \nonumber $

$ \sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(x, \bar{v}_{i})-\sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\bar{x}, \bar{v}_{i})\geq\langle\zeta, x-\bar{x}\rangle-\varepsilon_{2}, \nonumber $

式(3.5)经变换可得

$ r+\varepsilon_{1}+\varepsilon_{2} = \sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\bar{x}, \bar{v}_{i})+\varepsilon\geq0.\nonumber $

也即是

$ \sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\bar{x}, \bar{v}_{i})+\varepsilon-\sum\limits_{i = 1}^{m}(\lambda_{i}g_{i})(\bar{x}, v_{i})\geq0. $

故有

$ \psi(\bar{x})+\sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\bar{x}, \bar{v}_{i})+\varepsilon-(\psi(\bar{x})+\sum\limits_{i = 1}^{m}(\lambda_{i}g_{i})(\bar{x}, v_{i}))\geq0, $

即

$ \psi(\bar{x})+\sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\bar{x}, \bar{v}_{i})\geq\psi(\bar{x})+\sum\limits_{i = 1}^{m}(\lambda_{i}g_{i})(\bar{x}, v_{i})-\varepsilon. $

有

$ L(\bar{x}, \bar{v}, \bar{\lambda})\geq L(\bar{x}, v, \lambda)-\varepsilon. \nonumber $

下面证明$ L(x, \bar{v}, \bar{\lambda})+\varepsilon\geq L(\bar{x}, \bar{v}, \bar{\lambda}), $对任意的$ x\in {{\Bbb R}} ^{n}, $假设上式不成立,则存在$ x\in {{\Bbb R}} ^{n}, $有

$ \psi(\bar{x})+\sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\bar{x}, \bar{v_{i}})>\psi(x)+\sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(x, \bar{v_{i}})+\varepsilon, \nonumber $

$ \psi(x)-\psi(\bar{x})+\sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(x, \bar{v_{i}})-\sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\bar{x}, \bar{v_{i}})+\varepsilon<0. \nonumber $

由$ \varepsilon $ -次微分定义,上式可化简为

$ \langle\eta+\zeta, x-\bar{x}\rangle-\varepsilon_{1}-\varepsilon_{2}+\varepsilon<0.\nonumber $

将(3.5)式变换,与(4.1)式代入上式,有

$ r-\sum\limits_{i = 1}^{m}(\bar{\lambda}_{i}g_{i})(\bar{x}, \bar{v_{i}})\geq0, \nonumber $

这与假设矛盾,结论成立.

定理4.2  若存在$ \bar{\lambda}\in {{\Bbb R}} _{+}^{m}, $使得$ (\bar{x}, \bar{v}, \bar{\lambda}) $是问题(RUP)的$ \varepsilon $ -弱鞍点, $ \bar{x} $为$ \max\lambda^{T}g_{i}(x, v_{i}) $的最优解, $ \bar{x} $是问题(RUP)的$ \varepsilon $ -有效解.

证  令$ (\bar{x}, \bar{v}, \bar{\lambda}) $是问题(RUP)的$ \varepsilon $ -弱鞍点,对任意的$ \lambda_{i}\geq0 $,我们可以得到

$ \psi(x)-\psi(\bar{x})+\varepsilon+\bar{\lambda}_{i}^{T}(g(x, \bar{v}_{i})-g(\bar{x}, \bar{v}_{i}))\geq0, \ \ \ \forall x\in{{\Bbb R}} ^{n}.\nonumber $

并且$ \bar{x} $为$ \max\lambda^{T}g_{i}(x, v_{i}) $的最优解,有$ \psi(x)\geq \psi(\bar{x})-\varepsilon, \nonumber $结论成立.