在处理实际问题中的优化问题时, 由于估计或测量误差以及信息不对称等众多因素的影响, 很难保证数据的精确性. 因此研究含有不确定性信息的优化问题引起了学者们的极大兴趣. 当前主要借助随机优化方法和鲁棒优化方法来处理含有不确定性信息的优化问题, 即不确定优化问题. 随机优化方法常常依赖于不确定参数的概率分布. 然而在现实生活中, 实际的概率分布不易获得. 由于鲁棒优化方法基于已知的不确定集, 将不确定优化问题转化为确定性优化问题, 并且求解不依赖于概率分布. 因此鲁棒优化方法近些年得到了国内外学者的广泛关注, 并在理论和应用等各方面取得了系列研究成果详见文献[1–7].

众所周知, 借助鲁棒优化方法处理不确定优化问题时, 需要首先引入该不确定优化问题的鲁棒对等问题. 然而鲁棒对等问题的可行域要求对于给定的不确定集中的所有数据, 均需满足约束条件. 这极易导致鲁棒对等问题的可行集为空集, 即产生一个不可行的鲁棒对等问题. 因此研究不确定优化问题的鲁棒可行性半径, 即研究鲁棒对等问题的可行集非空时所对应的不确定集的最大“半径”(下见定义)是十分有意义的课题. 最近国内外学者从不同的角度对不确定优化问题的鲁棒可行性半径进行了研究, 并得到了一定的前期成果. Goberna等人^{[8, 9]}借助距离函数, 研究了基于仿射数据不确定集下的不确定多目标线性半无限优化问题的鲁棒可行性半径. Goberna等人^[10]借助Minkowski泛函和共轭函数上图性质, 刻画了带多项式约束的不确定凸优化问题的鲁棒可行性半径的上界, 并得到了带有平方和凸多项式约束的不确定优化问题的鲁棒可行性半径的精确公式. Chuong和Jeyakumar^[11]刻画了不确定线性优化问题的鲁棒可行性半径的精确公式, 并通过引入Spectrahedral不确定集, 得到了基于椭球、球、多面体以及箱子等各种不确定集下的不确定线性优化问题的易处理的鲁棒可行性半径计算公式. 陈加伟等人^[12]借助共轭函数所引入的上图像集和由不确定集所生成的Minkowski泛函, 刻画了一类不确定凸不等式系统的鲁棒可行性半径的上下界, 推广和改进了文献[10–11]的结果.

值得注意的是, 文献[10]仅仅给出了带有凸多项式约束的不确定凸优化问题的鲁棒可行性半径的上界刻画, 并未给出鲁棒可行性半径的详细范围. 受文献[10–12]的启发, 本文拟给出带有凸多项式约束的不确定凸优化问题的鲁棒可行性半径的下界, 并得到了带有平方和凸多项式约束的不确定优化问题的鲁棒可行性半径的精确公式. 为此, 本文首先引入了该不确定凸优化问题的鲁棒对等问题, 并给出了它的鲁棒可行性半径的定义. 随后借助一类不确定性集合和共轭函数上图性质, 刻画了该不确定问题的鲁棒可行性半径的下界. 特别的, 在不确定集是仿射不确定集时, 给出了带有平方和凸多项式的不确定优化问题的鲁棒可行性半径的精确公式.

若无特殊说明, 本文总是假设$ {{\Bbb R}} ^n $为$ n $维欧氏空间, 并赋予通常的欧氏范数$ \|\cdot\| $. $ 0_n $为$ {{\Bbb R}} ^n $中的零元素, $ {\Bbb B}_n $为$ {{\Bbb R}} ^n $中的闭单位球, $ {{\Bbb R}} ^n_+ $为$ {{\Bbb R}} ^n $中的非负象限. 若$ x, y\in {{\Bbb R}} ^n $, 则$ x $与$ y $的内积定义为$ \langle x, y \rangle=x^Ty $. 给定非空集合$ Z\subset{{\Bbb R}} ^n $, $ Z $的内部, 闭包, 凸包, 锥包和闭锥包分别定义为$ \mbox{int}Z $, $ \mbox{cl}Z $, $ \mbox{conv}Z $, $ \mbox{cone}Z $和$ \mbox{clcone}Z $. 假定$ h: {{\Bbb R}} ^n\rightarrow {{\Bbb R}} \cup \{+\infty\} $为广义实值函数. 函数$ h $的有效域、上图以及共轭函数分别定义为

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

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

和

$ h^{*}(x^{*})=\mathop{{\rm sup}}_{x\in{{\Bbb R}} ^n}\left\{\langle x^{*}, x \rangle-h(x)\right\}. $

若$ {\rm dom }h\neq \emptyset $, 则称函数$ h $是真函数. 若$ {\rm epi }h $为凸集, 则称函数$ h $是凸函数. 若$ {\rm epi }h $为闭集, 则称函数$ h $是下半连续的. 记$ \Gamma({{\Bbb R}} ^n) $为全体真凸下半连续的广义实值函数组成的集合. 若函数$ h\in \Gamma({{\Bbb R}} ^n) $, 则

(2.1) $ \begin{eqnarray} \mbox{epi }(\alpha h)^*=\alpha \mbox{epi }h^*+\{0_n\}\times {{\Bbb R}} _+, \; \forall\alpha>0. \end{eqnarray} $

特别的, 令函数$ h_1, h_2\in\Gamma({{\Bbb R}} ^n) $并且$ \mbox{dom }h_1\cap \mbox{dom }h_2\neq\emptyset $. 若$ h_1 $或$ h_2 $在$ \bar{x}\in\mbox{dom }h_1\cap \mbox{dom }h_2 $处连续, 则

(2.2) $ \begin{eqnarray} \mbox{epi }(h_1+h_2)^*=\mbox{epi }h_1^*+\mbox{epi }h_2^*. \end{eqnarray} $

关于广义实值函数的更多详细性质可参见文献[13].

引理2.1^{[14, 定理3.1]}  设$ T $为任意的指标集. 若$ h_t\in \Gamma({{\Bbb R}} ^n) $, $ \forall t\in T $, 则以下命题等价

(i) $ \{x\in {{\Bbb R}} ^n:h_t(x)\leq0, t\in T\}\neq \emptyset; $

(ii) $ (0, -1)\notin {\rm clcone}\Big(\bigcup\limits_{t\in T}{\rm epi }h_t^*\Big) $.

引理2.2^{[10, 引理2.2]}  设$ h_t:{{\Bbb R}} ^n\rightarrow {{\Bbb R}} $, $ t\in T $, 为凸函数, $ Z\subset {{\Bbb R}} ^{n+1} $为紧凸集且$ 0_{n+1}\in {\rm int}Z $. 假定$ \beta\geq0 $以及$ (0, -1)\in{\rm clcone}\Big(\bigcup\limits_{t\in T}{\rm epi}h_t^*+\beta Z\Big) $. 则

$ (0, -1)\in{\rm cone}\bigg(\bigcup\limits_{t\in T}{\rm epi}h_t^*+(\beta+\delta)Z\bigg), \; \forall \delta>0. $

定义2.1  设$ Z\subset{{\Bbb R}} ^{n+1} $为非空凸集且$ 0_{n+1}\in {\rm int}Z $. 函数$ \phi_Z(x):=\inf\{t>0:x\in tZ\} $称为由$ Z $生成的$ {\rm Minkowski} $泛函.

命题2.1^{[15, 引理1.3.13]}  令$ Z $为$ {{\Bbb R}} ^{n+1} $中的紧凸集并且$ 0_{n+1}\in{\rm int}Z $. 则

(i) $ \phi_Z $具有次线性和连续性;

(ii) $ \{x\in {{\Bbb R}} ^{n+1}:\phi_Z(x)\leq1\}={\rm cl}Z $;

(iii) 如果$ Z $是有界且对称的(即, $ -Z=Z) $, 那么$ \phi_Z:=\|\cdot\|_Z $是$ {{\Bbb R}} ^{n+1} $中由$ Z $生成的范数.

定义2.2^[16]  设$ f:{{\Bbb R}} ^n\rightarrow {{\Bbb R}} $为实多项式函数. 若存在实多项式函数$ f_i:{{\Bbb R}} ^n\rightarrow {{\Bbb R}} , $$ i=1, \cdots , r $, 使得$ f=\sum\limits_{i=1}^rf_i^2, $则称$ f $是平方和多项式函数. 记$ \Sigma^2 $为所有平方和实多项式函数组成的集合.

定义2.3^[17]  设$ f:{{\Bbb R}} ^n\rightarrow {{\Bbb R}} $为实多项式函数. 若$ \sigma(x, y):=f(x)-f(y)-\nabla f(y)^T(x-y) $, $ \forall x, y\in {{\Bbb R}} ^n $, 为平方和多项式, 则称$ f $是平方和凸多项式函数.

注  显然平方和凸多项式函数是凸多项式函数, 反之凸多项式函数却不一定是平方和凸多项式函数, 详见文献[16–17].

设$ f:{{\Bbb R}} ^n\rightarrow {{\Bbb R}} $为凸函数, $ g_j $, $ g_j^l:{{\Bbb R}} ^n\rightarrow {{\Bbb R}} , $$ j=1, \cdots , q $, $ l=1, \cdots , p $, 均为凸多项式函数. 考虑如下不确定凸优化问题

$ \min\limits_{x\in {{\Bbb R}} ^n}\left\{f(x):g_j(x)+\sum^p_{l=1}v^l_j g^{l}_j(x)+a^T_j x+b_j\leq 0\right\}. \ \ \ \ \ \ \ \ \ \ \ \ {\rm (UP)} $

此处$ v_j^l\in {{\Bbb R}} $, $ a_j\in {{\Bbb R}} ^n $, $ b_j\in {{\Bbb R}} $, $ j=1, \cdots , q $, $ l=1, \cdots , p $, 均为不确定参数. 假定不确定参数向量$ (v_j^1, \cdots , v_j^p)\in \bar\alpha_jM $和$ (a_j, b_j)\in \bar\alpha_j{\Bbb B}_{n+1} $, $ j=1, \cdots , q $, 其中$ \bar\alpha_j\geq0 $, $ M\subset {{\Bbb R}} _+^p $是含零元素$ 0_p $的紧凸集, $ {\Bbb B}_{n+1}\subset {{\Bbb R}} ^{n+1} $为闭单位球. 如无特殊说明, 本文总是记$ J:=\{1, \cdots , q\} $和$ v_j:=(v_j^1, \cdots , v_j^p) $, $ j\in J $.

设$ \bar\alpha :=(\bar\alpha_1, \cdots , \bar\alpha_q)\in {{\Bbb R}} ^q_+ $. 则基于不确定集$ \bar\alpha_j(M\times{\Bbb B}_{n+1}) $, $ j\in J $, 借助鲁棒优化方法^{[1, 3]}, 易得$ \mbox{(UP)} $的鲁棒对等问题为

$ \begin{array}{l}\mathop {\min }\limits_{x \in {\mathbb{R}^n}} \{ f(x):{g_j}(x) + \sum\limits_{l = 1}^p {v_j^l} g_j^l(x) + a_j^Tx + {b_j} \le 0,\\\forall ({v_j},({a_j},{b_j})) \in {{\bar \alpha }_j}(M \times {\mathbb{B}_{n + 1}}),j \in J\} . \ \ \ \ \ \ \ \ \ \ \ \ ({\rm{R}}{{\rm{P}}_{\bar \alpha }})\end{array} $

不失一般性, 本文假设$ \rm{(RP_{ \mathsf{\bar α}})} $的可行集非空, 即

$ \left\{x\in {{\Bbb R}} ^n:{g}_j(x)+\sum^p_{l=1}v^l_j {g}^{l}_j(x)+a^T_j x+b_j\leq 0, \forall (v_j, (a_j, b_j))\in \bar\alpha_j(M\times {\Bbb B}_{n+1}), j\in J\right\}\neq \emptyset. $

令$ \alpha :=(\alpha_1, \cdots , \alpha_q)\in {{\Bbb R}} ^q_+ $. 考虑一类不确定集

$ U_j:=(\bar\alpha_j+\alpha_j)(M\times{\Bbb B}_{n+1}), {\quad} j\in J, $

则此时$ {\rm (UP)} $的鲁棒对等问题可表示为

$ \min\limits_{x\in {{\Bbb R}} ^n} \Bigg\{f(x):{g}_j(x)+\sum^p_{l=1}v^l_j {g}^{l}_j(x)+a^T_j x+b_j\leq 0, \forall(v_j, (a_j, b_j))\in U_j, j\in J\Bigg\}. \eqno{\rm (RP_{\bar\alpha, \alpha})} $

显然, 不确定集$ U_j $中的所有数据均需满足$ \rm (RP_{\bar\alpha, \alpha}) $的约束条件, 这极易导致$ \rm (RP_{\bar\alpha, \alpha}) $的可行集为空集, 从而导致$ \rm (RP_{\bar\alpha, \alpha}) $不可行. 因此对于任意给定的不确定集合, 研究$ \rm(UP) $的鲁棒可行性半径, 即研究确保$ \rm (RP_{\bar\alpha, \alpha}) $的可行集非空时所对应的不确定集$ U_j $中$ \alpha_j $的最大取值十分必要. 受文献[10–12]的启发, 我们首先引入$ {\rm (UP)} $的鲁棒可行性半径概念.

定义3.1  (UP)的鲁棒可行性半径$ \rho $定义为

(3.1) $ \begin{eqnarray} \rho:=\sup\Big\{\min\limits_{j\in J}\alpha_j:({\rm RP}_{\bar\alpha, \alpha})\ \mbox{可行域非空}\Big\}. \end{eqnarray} $

注3.1  不难发现, 若$ \bar\alpha=0_q $, 则此时$ \rho $是保证$ {\rm (UP)} $的鲁棒可行性所对应的不确定集的最大半径.

定义3.2^[18]  (UP)中的凸多项式$ g_j(x) $所对应的上图像集定义为

(3.2) $ \begin{eqnarray} E(g):=\mathop{{\rm conv}}\bigg(\bigcup\limits_{j\in J}\mathop{{\rm epi }} g_j^*\bigg). \end{eqnarray} $

接下来将借助上图像集和Minkowski泛函, 刻画(UP)的鲁棒可行性半径$ \rho $的下界. 简便起见, 假定

$ Z_j:=\mathop{{\rm clconv}}\bigg(\bigcup\limits_{(v_j^1, \cdots , v_j^p)\in M}\sum\limits_{l=1}^pv_j^l\mathop{{\rm epi}}( g_j^l)^*\bigg)+{\Bbb B}_{n+1}. $

显然$ Z_j\subset {{\Bbb R}} ^{n+1} $是闭凸集且$ 0_{n+1}\in {\rm int}Z_j $.

定理3.1(鲁棒可行性半径的下界)  设$ {\rm (RP_{\bar\alpha})} $可行. 则$ {\rm (RP_{\bar\alpha, \alpha})} $的鲁棒可行性半径$ \rho $满足

$ \rho\geq\min\Big\{\min\limits_{j\in J}\phi_{Z_j}(-z):z\in E({g})\Big\}-\min\limits_{j\in J}\{\bar{\alpha}_j\}. $

证  令$ \epsilon>0 $以及$ \tilde{\alpha}=\rho+\epsilon $. 若$ \alpha_j=\tilde{\alpha} $, $ j\in J $, 则由$ \rho $的定义可知

(3.3) $ \begin{equation} \begin{array}{ll} &\bigg\{{ } x\in {{\Bbb R}} ^n:{g}_j(x)+\sum\limits_{i=1}^p v_j^l {g}_j^l(x)+a_j^T x+b_j\leq 0, \\ &{\quad} \forall(v_j, (a_j, b_j)) \in(\bar{\alpha}_j+ \tilde{\alpha})(M\times {\Bbb B}_{n+1}), j\in J\bigg\}= \emptyset. \end{array} \end{equation} $

令

$ \psi_j(x)= g_j(x)+\sum\limits_{i=1}^p v_j^l {g}_j^l(x)+a_j^T x+b_j, \; \forall x\in{{\Bbb R}} ^n. $

则由(2.1), (2.2)式和$ {\rm epi} g_j^*={\rm epi} g_j^*+\{0_n\}\times{{\Bbb R}} _+ $有

(3.4) $ \begin{equation} {\rm epi}\psi_j^*={\rm epi}g_j^*+\sum\limits_{i=1}^p v_j^l {\rm epi}({g}_j^l)^*+(a_j, -b_j). \end{equation} $

从而由引理2.1和(3.4) 式可知, (3.3) 式等价于

(3.5) $ \begin{equation} (0_n, -1)\in {\rm clcone} \Bigg(\bigcup\limits_{ (v_j^1, \cdots , v_j^p)\in (\bar{\alpha}_j+ \tilde{\alpha})M \atop (a_j, b_j) \in(\bar{\alpha}_j+ \tilde{\alpha}){\Bbb B}_{n+1}, j\in J}\bigg({\rm epi} {g}_j^* +\sum\limits_{l=1}^pv_j^l{\rm epi}( g_j^l)^*+(a_j, -b_j)\bigg)\Bigg). \end{equation} $

由(3.5)式可知

$ \begin{eqnarray*} (0_n, -1) &\in & {\rm clcone}\Bigg(\bigcup\limits_{j\in J}\Bigg({\rm epi} {g}_j^* +(\bar{\alpha}_j+ \tilde{\alpha})\bigg(\bigcup\limits_{(v_j^1, \cdots , v_j^p)\in M}\sum\limits_{l=1}^pv_j^l{\rm epi}( g_j^l)^*\bigg)+(\bar{\alpha}_j+ \tilde{\alpha}){\Bbb B}_{n+1}\Bigg)\Bigg)\\ &\subset& {\rm clcone}\Bigg(\bigcup\limits_{j\in J}\Bigg({\rm epi} {g}_j^* +(\bar{\alpha}_j+ \tilde{\alpha})\bigg(\bigcup\limits_{(v_j^1, \cdots , v_j^p)\in M}\sum\limits_{l=1}^pv_j^l{\rm epi}( g_j^l)^*+{\Bbb B}_{n+1}\bigg)\Bigg)\Bigg)\\ &\subset& {\rm clcone}\bigg(\bigcup\limits_{j\in J}\big({\rm epi} {g}_j^* +(\bar{\alpha}_j+ \tilde{\alpha})Z_j\big)\bigg). \end{eqnarray*} $

再结合引理2.2可知

$ (0_n, -1)\in {\rm cone}\bigg(\bigcup\limits_{j\in J}\left({\rm epi} {g}_j^* +(\bar{\alpha}_j+ \tilde{\alpha}+\epsilon)Z_j\right)\bigg), \; \forall\epsilon>0. $

因此存在$ \lambda_j\geq0, \; z_j\in Z_j $和$ (u_j, t_j)\in {\rm epi}{g}_j^*, \; j\in J $, 使得

(3.6) $ \begin{equation} (0_n, -1)=\lambda_j\big[(u_j, t_j)+ (\bar{\alpha}_j+ \tilde{\alpha}+\epsilon)z_j\big]. \end{equation} $

又因为$ (u_j, t_j)\in {\rm epi}{g}_j^* $, 所以存在$ r_j\geq0 $, 使得$ t_j={g}_j^*(u_j)+r_j $. 从而由(3.6)式可知

$ (0_n, -1)=\lambda_j\left[\big(u_j, {g}_j^*(u_j)+r_j\big)+ \big(\bar{\alpha}_j+ \tilde{\alpha}+\epsilon\big)z_j\right]. $

故

$ \begin{eqnarray*} -(\bar{\alpha}_j+ \tilde{\alpha}+\epsilon)z_j &=&{\frac{1}{\lambda_j}}(0_n, 1)+(u_j, {g}_j^*(u_j)+r_j)\\ &=&\Big(u_j, {g}_j^*(u_j)+r_j+{\frac{1}{\lambda_j}}\Big)\in {\rm epi}{{g}_j^* }\subseteq E({g}). \end{eqnarray*} $

因此

(3.7) $ \begin{eqnarray} \min\Big\{\min\limits_{j\in J}\phi_{Z_j}(-z):z\in E(g)\Big\} &\leq&\min\limits_{j\in J}\phi_{Z_j}\left((\bar{\alpha}_j+\tilde {\alpha}+\epsilon)z_j\right) {}\\ &\leq & (\bar{\alpha}_j+\tilde{\alpha}+\epsilon)\min\limits_{j\in J}\phi_{Z_j}(z_j) {}\\ &\leq&\bar{\alpha}_j+\tilde{\alpha}+\epsilon{}\\ &=&\rho+\bar{\alpha}_j+2\epsilon. \end{eqnarray} $

其中第二个不等式成立由命题$ 2.1{\rm (i)} $可得, 第三个不等式成立源于命题$ 2.1{\rm (ii)} $且$ z_j\in Z_j $. 进一步的, 在(3.7)式中, 令$ \epsilon\rightarrow 0 $. 则

$ \rho\geq \min\Big\{ \min\limits_{j\in J}\phi_{Z_j}(-z):z\in E({g})\Big\}-\min\limits_{j\in J}\{\bar{\alpha}_j\}. $

定理得证.

注3.2  文献[10, 定理2.1]仅仅给出了$ {\rm (UP)} $的鲁棒可行性半径$ \rho $的上界, 即

$ 0\leq \rho\leq\min\Big\{\mathop{{\rm max}}\limits_{j\in J}\phi_{Z_j}(-z):z\in E(g)\Big\}-\mathop{{\rm min}}\limits_{j\in J}\{\bar\alpha_j\}. $

本文定理$ 3.1 $给出了$ {\rm (UP)} $的鲁棒可行性半径$ \rho $的下界, 从而得到了$ {\rm (UP)} $的鲁棒可行性半径$ \rho $的取值范围, 即

$ \min\Big\{ \min\limits_{j\in J}\phi_{Z_j}(-z):z\in E({g})\Big\}-\min\limits_{j\in J}\{\bar{\alpha}_j\}\leq \rho\leq\min\Big\{\mathop{{\rm max}}\limits_{j\in J}\phi_{Z_j}(-z):z\in E(g)\Big\}-\mathop{{\rm min}}\limits_{j\in J}\{\bar\alpha_j\}. $

因此定理$ 3.1 $完善和改进了文献[10, 定理2.1] 的结论.

下面给出一个简单例子解释定理$ 3.1 $.

例3.1  考虑$ {\rm (RP_{\bar\alpha, \alpha})} $. 令

$ n:=1, p=q:=2, J:=\{1, 2\}, M:=[0, 1]\times[0, 1], $

$ g_1(x):=x^4-1, g_2(x):=x^2-1, g_1^1(x)=g_1^2(x):=x, g_2^1(x)=g_2^2(x):=x^2, \bar\alpha_1=\bar\alpha_2:=0. $

因此根据共轭函数的定义可知

$ (g_1^1)^*(y)=(g_1^2)^*(y)= \left \{ \begin{array}{l} 0, \;\;\;\;\;\;\mbox{若}\ y=1, \\ +\infty, \;\mbox{若}\ y\not=1. \end{array} \right . $

$ ( g_2^1)^*(y)=( g_2^2)^*(y)=\frac{y^2}{4}, \; g_1^*(y)=\frac{3}{4\sqrt[3]{4}}y^{\frac{4}{3}}+1, \; g_2^*(y)=\frac{1}{4}y^2+1. $

从而

$ \begin{eqnarray*} Z_1 &=&{\rm clconv}\Bigg(\bigcup\limits_{(v_1^1, v_1^2)\in M}\sum\limits_{l=1}^2v_1^l{\rm epi}( g_1^l)^*\Bigg)+{\Bbb B}_2\\ &=&{\rm clconv}\Bigg(\bigcup\limits_{(v_1^1, v_1^2)\in M}(v_1^1+v_1^2)( \{1\}\times {{\Bbb R}} _+)\Bigg)+{\Bbb B}_2\\ & =& [0, 2]\times{{\Bbb R}} _++{\Bbb B}_2, \\ Z_2& =&{\rm clconv}\Bigg(\bigcup\limits_{(v_2^1, v_2^2)\in M}\sum\limits_{l=1}^2v_2^l{\rm epi}( g_2^l)^*\Bigg)+{\Bbb B}_2\\ &=&{\rm clconv}\Bigg(\bigcup\limits_{(v_2^1, v_2^2)\in M}(v_2^1+v_2^2)\left\{(y, r)\in {{\Bbb R}} ^2: r\geq\frac{y^2}{4}\right\}\Bigg)+{\Bbb B}_2\\ &=&\left\{(y, r)\in {{\Bbb R}} ^2: r\geq\frac{y^2}{8}\right\}+{\Bbb B}_2, \end{eqnarray*} $

以及

$ \begin{eqnarray*} E(g)& =&\mathop{{\rm conv}}\bigg(\bigcup\limits_{j\in J}\mathop{{\rm epi }} g_j^*\bigg)\\ & =&{\rm conv}\left( \left\{(y, r)\in {{\Bbb R}} ^2: y\leq -\frac{\sqrt{27}}{2}\ \mbox{或}\ y\geq \frac{\sqrt{27}}{2}, r\geq\frac{3}{4\sqrt[3]{4}}y^{\frac{4}{3}}+1\right\}\right.\\ &&\left.\; \; \; \; \; \; \; \; \; \; \bigcup\left\{(y, r)\in {{\Bbb R}} ^2: -\frac{\sqrt{27}}{2} \leq y\leq \frac{\sqrt{27}}{2}, r\geq\frac{1}{4}y^{2}+1\right\}\right) . \end{eqnarray*} $

故可得

$ \min\limits_{z\in E(g)}\phi_{Z_1}(-z)=\min\limits_{z\in E(g)}\phi_{Z_2}(-z)=1. $

因此

$ \min\Big\{ \min\limits_{j\in J}\phi_{Z_j}(-z):z\in E({g})\Big\}-\min\limits_{j\in J}\{\bar{\alpha}_j\}=1. $

从而由定理$ 3.1 $可知$ \rho\geq1. $

在实际应用中, 判断一个多项式函数是否是凸多项式函数是相对困难的. 而判断一个多项式函数是否是平方和多项式函数可以转化为求解一个相对应的半定优化问题, 并且一个平方和凸多项式函数一定是凸多项式函数. 因此作为特例, 本章节的最后考虑带平方和多项式函数约束的不确定优化问题的鲁棒可行性半径.

设$ f:{{\Bbb R}} ^n\rightarrow {{\Bbb R}} $为凸函数, $ g_j $, $ j\in J $, 为平方和凸多项式函数. 考虑如下不确定优化问题

$ \min\limits_{x\in{{\Bbb R}} ^n} \Big\{f(x):{g}_j(x)+a^T_j x+b_j\leq 0\Big\}. \ \ \ \ \ \ \ \ \ \ \ \ \ {\rm (UP_0)} $

其中$ a_j\in {{\Bbb R}} ^n $, $ b_j\in {{\Bbb R}} $, $ j\in J $, 为不确定参数, 并且对于给定的$ \alpha_0\geq0 $, $ (a_j, b_j)\in \alpha_0{\Bbb B}_{n+1} $, $ j \in J $.

设不确定集为$ (\alpha_0+\alpha_j){\Bbb B}_{n+1} $, $ j\in J $, 以及$ \alpha:=(\alpha_1, \cdots , \alpha_q)\in {{\Bbb R}} _+^q $. 则$ (\rm UP_0) $的鲁棒对等问题为

$ \min\limits_{x\in{{\Bbb R}} ^n} \Big\{f(x):{g}_j(x)+a^T_j x+b_j\leq 0, \forall (a_j, b_j)\in (\alpha_0+\alpha_j){\Bbb B}_{n+1}, j\in J \Big\}. \ \ \ \ \ \ \ \ \ \ \ \ \ \ {\rm (RP_{\alpha_0, \alpha})} $

不失一般性, 假设$ (\rm RP_{\alpha_0, \alpha}) $的可行集非空, 即

$ \Big\{x\in {{\Bbb R}} ^n: g_j(x)+a_j^T x+b_j\leq 0, \forall (a_j, b_j)\in \alpha_0 {\Bbb B}_{n+1}, j\in J\Big\} \neq \emptyset. $

令$ \Delta_q $为$ {{\Bbb R}} ^q $中的单纯形, 即

$ \Delta_q:=\Bigg\{\lambda=(\lambda_1, \cdots , \lambda_{q})\in {{\Bbb R}} _+^{q}:\sum\limits_{j=1}^{q}\lambda_j=1\Bigg\}. $

接下来, 利用不同于文献[10, 定理3.1]的证明方法, 得到了$ (\rm UP_0) $的鲁棒可行性半径的一个精确计算公式.

定理3.2  考虑$ {\rm (RP_{\alpha_0, \alpha})} $. 令$ \rho $为(3.1) 式中用$ {\rm (RP_{\alpha_0, \alpha})} $代替$ {\rm (RP_{\bar\alpha, \alpha})} $之后所对应的鲁棒可行性半径. 则$ \rho=\rho_0-\alpha_0 $, 其中$ \rho_0\geq0 $且

$ \rho_0^2=\min\limits_{(\omega, r)\in {{\Bbb R}} ^n\times{{\Bbb R}} , \lambda\in \Delta_q}\Bigg\{\|(\omega, r)\|^2:r-\langle\omega, \cdot\rangle+\sum\limits_{j\in J}\lambda_jg_j\in \Sigma^2\Bigg\}. $

证  由定理$ 3.1 $和文献[10, 定理2.1]有

$ \min\Big\{\min\limits_{j\in J}\phi_{Z_j}(-z):z\in E({g})\Big\}-\min\limits_{j\in J}\{\bar{\alpha}_j\}\leq\rho\leq\min\Big\{\mathop{{\rm max}}\limits_{j\in J}\phi_{Z_j}(-z):z\in E(g)\Big\}-\mathop{{\rm min}}\limits_{j\in J}\{\bar\alpha_j\}. $

令$ M=0_p $. 则$ Z_j={\Bbb B}_{n+1} $. 由于$ {\Bbb B}_{n+1} $是对称的, 所以由命题$ 2.1\rm{(iii)} $可知, 对任意的$ z\in {{\Bbb R}} ^n $,

$ \phi_{Z_j}(z)=\|z\|. $

令$ \bar\alpha_j=\alpha_0 $, $ j\in J $. 则

(3.8) $ \begin{equation} \rho=\min \{\|(\omega, r)\|:(\omega, r)\in E(g)\}-\alpha_0. \end{equation} $

进一步的, 类似于文献[10, 定理3.1]可证, $ (\omega, r)\in E(g) $等价于存在$ \lambda \in \Delta_q $, 使得

$ r-\langle\omega, \cdot\rangle+\sum\limits_{j\in J}\lambda_j g_j\in \Sigma^2. $

从而结合(3.8)式可知定理成立.