区间值规划是一类不确定优化问题, 其中考虑的参数是闭区间. 区间值分析可参见文献 [16]. 紧接着, 文献 [17] 定义了两个区间的两种偏序关系并研究了区间值优化问题的模型.

自此, 区间值优化问题的研究引起了广泛关注. 在目标函数和约束函数的凸性假设下, Wu^[19] 在目标函数分别是弱连续可微和连续 H-可微条件下推导了区间值优化问题的 KKT 充分条件. 当约束集是不等式约束且满足 $\boldsymbol{x}\geq\boldsymbol{0}$ 时, Wu^[20] 应用 KKT 条件推导了强对偶定理. 张建科^[21]在不变凸条件下推导了区间值优化问题的 KKT 必要条件和 Wolfe 型对偶. Jayswal 等^[12]在广义凸函数的条件下研究了 KKT 条件, 推导了 Mond-Weir 型和 Wolf 型对偶定理. 在局部凸空间, Sun-Wang 等^[18]研究非光滑单目标区间值规划问题的 Fritz-John 和 KKT 最优性条件.

Cano^[6] 在凸性假设下通过广义导数推导了区间值函数优化问题的 KKT 充分性条件. Zhang 等^[22] 引入了预不变凸和不变凸区间值函数的概念, 并在弱连续可微和连续 H-可微的条件下推导了预不变凸和不变凸区间值优化问题 KKT 最优性条件. Li 等^[14] 通过 gH-可微性引入了区间值函数的不变凸性, 并推导了区间值优化问题的KKT最优性条件.

从以上研究可知, 在凸性或某些广义凸性条件下, KKT 条件是区间值优化问题LU-解的一个充分条件; 当约束函数是凸函数时, 若满足 Slater 约束规范, KKT 条件是区间值优化问题 LU-解的一个必要条件. 然而, 凸性条件并不总是满足. 因此, 我们证明如果满足 Mangasarian-Fromovitz 约束规范 (简记为 MFCQ), 那么 KKT 条件是等式不等式约束的模型 (IVOP) 的可行点成为 LU-解的必要条件.

对于标量值优化问题, 如果在可行点上不满足约束规范, 那么 KKT 必要条件将失效. 为此, Andreani-Haeser-Martínez^[1] 引入了单目标光滑约束优化问题的 AKKT 条件. Andreani-Haeser-Martínez^[1] 和 Haeser-Schuverdt^[9] 证明了在不需要任何约束规范的情况下, AKKT 条件是标量单目标最优化问题局部最优解的必要条件. Giorgi-Jiménez-Novo^[8] 和 Mansoureh^[10] 把 AKKT 最优性条件推广到了标量多目标优化问题. 对于标量值最优化问题, Andreani-Martínez-Svaiter^[2] 引入了互补近似 KKT (简记为 CAKKT) 条件. Andreani-Martínez-Svaiter^[2] 获得了如下结果: (i) 每个局部最小点都是 CAKKT 点; (ii) 每个 CAKKT 点都是 AKKT 点. 这意味着 CAKKT 条件优于 AKKT 条件. 一个有趣的问题是如何把标量值优化问题的 CAKKT 型最优性条件推广到区间值优化问题. 这是本文的主要动机.

本文余下部分安排如下: 第 2 节, 我们回顾闭区间运算的一些性质和 LU-解的概念. 第 3 节, 在满足约束规范的情况下, 推导了带弱可微目标函数的区间值优化问题 (IVOP) 的 KKT 必要条件. 第 4 节, 对于带弱可微目标函数的 (IVOP), 我们引入弱互补近似 Karush-Kuhn-Tucker (简记为 W-CAKKT) 条件. 不需要任何约束规范的情况下, 我们证明了 W-CAKKT 条件是带弱可微目标函数的 (IVOP) 的 LU-解的必要条件 (参见定理 4.1). 进一步, 在凸性假设下, 我们证明了 W-CAKKT 条件是 (IVOP) LU-解的充分条件 (参见定理 4.2). 另外, 当满足约束规范时, 我们证明了 W-CAKKT 必要条件优于 KKT 必要条件 (参见定理 4.3). 本文的主要结果把 Andreani-Martínez-Svaiter^[2] 的主要结果从标量值优化问题推广到了区间值优化问题.

符号说明

$\bullet$ $\|\cdot\|$ 表示某种特定范数.

$\bullet$ $B(\boldsymbol{x}^{0},\delta):=\{\boldsymbol{x}\in \mathbb{R}^{n}|\ \|\boldsymbol{x}-\boldsymbol{x}^{0}\|<\delta\},\ \bar{B}(\boldsymbol{x}^{0},\delta):=\{\boldsymbol{x}\in \mathbb{R}^{n}|\ \|\boldsymbol{x}-\boldsymbol{x}^0\|\leq\delta\}.$

$\bullet$ $\mathbb{R}_{+}^{n}=\{\boldsymbol{x}\in \mathbb{R}^{n}|\ x_{i}\geq 0, i=1,\cdots,n\}$.

$\bullet$ 若 $v\in \mathbb{R}^{n}$, 记$v_+=\{\max\{0,v_1\},\cdots,\max\{0,v_n\}\}$.

$\bullet$ 若 $v\in \mathbb{R}$, 记$v_{+}^{2}=(v_+)^{2}$.

设 $\mathbb{R}$ 为全体实数的集合, 记 $\mathcal{I}_{(\mathbb{R})}$ 为 $\mathbb{R}$ 上所有有界闭区间的集合. 设 $A\in \mathcal{I}_{(\mathbb{R})}$, 记 $A=[a^{L},a^{U}]$, 其中 $a^{L}$ 和 $a^{U}$ 分别表示闭区间 $A$ 的下界和上界. 设 $A, B\in\mathcal{I}_{(\mathbb{R})}$, $k\in\mathbb{R}$, 我们回顾区间的一些运算和序关系 (如参考文献 [19]).

(i) $A+B:=\{a+b:a\in A$, $b\in B\}=[a^{L}+b^{L},a^{U}+b^{U}]$;

(ii) $k A:=\{k a: a\in A\}=\left\{\begin{array}{ll} {[k a^{\mathrm{L}}, k a^{\mathrm{U}}]} & \text {若}\ k \geq0\\ {[k a^{\mathrm{U}}, k a^{\mathrm{L}}]} & \text {若}\ k<0 \end{array}\right., k\in\mathbb{R}$;

(iii) $A\preceq_{LU}B$ 当且仅当 $a^L\leq b^L$ 且 $a^U\leq b^U$;

(iv) $A\prec_{LU}B$ 当且仅当 $A\preceq_{LU}B$ 且 $A\neq B$. 这意味着如下之一成立

设 $T$ 是 $\mathbb{R}^{n}$ 的开集, $f:T\rightarrow \mathcal{I}_{(\mathbb{R})}$ 是区间值函数. 这意味着, 对每一个 $\boldsymbol{x}\in T$, $f(\boldsymbol{x})=f(x_1,\cdots,x_n)$ 是一个闭区间. 一个区间值函数可以写为 $f(\boldsymbol {x})=[f^{L}(\boldsymbol{x}),f^{U}(\boldsymbol{x})]$, 其中 $f^{L}(\boldsymbol{x})$ 和 $f^{U}(\boldsymbol{x})$ 是 $T$ 上的实值函数, 且对每一个 $\boldsymbol{x}\in T$ 满足 $f^{L}(\boldsymbol{x})\leq f^{U}(\boldsymbol{x})$. 另外, Wu^[19] 引入两个闭区间 $A$ 与 $B$ 的 Hausdorff 度量, 即 $d_{H}(A, B)=\text{max}\{|a^{L}-b^{L}|, |a^{U}-b^{U}|\}$. 基于 Hausdorff 度量, Wu^[19] 进一步引入了区间值函数的极限, 连续和两类微分的概念.

定义 2.1^[19] 当 $\boldsymbol{x}$ 趋于 $\boldsymbol{x}^{0}\in \mathbb{R}^{n}$时, 称区间值函数 $f:\mathbb{R}^{n}\rightarrow \mathcal{I}_{(\mathbb{R})}$ 收敛于 $A\in \mathcal{I}_{(\mathbb{R})}$, 如果对于任意的 $\epsilon>0$, 存在 $\delta>0$ 使得对于满足 $\|\boldsymbol{x}-\boldsymbol{x}^{0}\|<\delta$ 的每一个 $\boldsymbol{x}$ 都有 $d_{H}(f(\boldsymbol{x}),A)<\epsilon$. 记为 $\lim\limits_{\boldsymbol{x}\rightarrow \boldsymbol{x}^0} f(\boldsymbol{x})=A$. 称区间值函数 $f$ 在点 $\boldsymbol{x}^0\in \mathbb{R}^{n}$ 是连续的, 如果 $\lim\limits_{\boldsymbol{x}\rightarrow \boldsymbol{x}^{0}} f(\boldsymbol{x})=f(\boldsymbol{x}^{0})$.

由定义 2.1, 有如下命题.

命题 2.1^{[19, 命题3.3]} 给定区间值函数 $f:\mathbb{R}^{n}\rightarrow \mathcal{I}_{(\mathbb{R})}$ 和 $A=[a^{L}, a^{U}]\in \mathcal{I}_{(\mathbb{R})}$. 则 $\lim\limits_{\boldsymbol{x}\rightarrow \boldsymbol{x}^{0}} f(\boldsymbol{x})=A$ 当且仅当 $\lim\limits_{\boldsymbol{x}\rightarrow \boldsymbol{x}^{0}} f^L(\boldsymbol{x})=a^{L}$, $\lim\limits_{\boldsymbol{x}\rightarrow \boldsymbol{x}^{0}} f^U(\boldsymbol{x})=a^{U}$ 同时成立. 从而, $f$ 在点 $\boldsymbol{x}^{0}\in \mathbb{R}^{n}$ 连续, 当且仅当 $f^{L}$ 和 $f^{U}$ 在点 $\boldsymbol{x}^{0}$ 连续.

称闭区间 $C=[c^{L},c^{U}]\in \mathcal{I}_{(\mathbb{R})}$ 是闭区间 $A$ 与 $B$ 的 Hukuhara差, 如果 $A=B+C$. 记为 $C=A\ominus_H B$. 由 $A=B+C$ 可知 $a^{L}=b^{L}+c^{L}$ 和 $a^U=b^{U}+c^{U}$. 因此, 如果 $a^{U}-a^{L}\geq b^{U}-b^{L}$, 那么 Hukuhara 差 $C$ 存在, 且 $C=[a^{L}-b^{L},a^{U}-b^{U}]$. 我们回顾 Hukuhara 导数 (简记为 H-导数) 的概念.

定义 2.2^{[19, 定义4.2]} 设 $T$ 是 $\mathbb{R}$ 的开集. 称区间值函数 $f:T\rightarrow \mathcal{I}_\mathbb{R}$ 在点 $x^{0}$ 是 H-可微的, 如果存在闭区间 $A(x^{0})\in\mathcal{I}_\mathbb{R}$ 使得

这时, 称 $A(x^{0})$ 是 $f$ 在点 $x^{0}$ 的 H-导数.

定义 2.3^{[19, 定义4.4]} 设 $f$ 是 $T\subseteq\mathbb{R}^{n}$ 上的区间值函数, 给定 ${\boldsymbol{x}}^{0}=(x_{1}^{0},\cdots,x_{n}^{0})\in T$.

(i) 称 $f$ 在点 $\boldsymbol{x}^{0}$ 是弱可微的, 如果 $f^{L}$ 和 $f^{U}$ 在点 $\boldsymbol{x}^{0}$ 可微(这蕴含对每一个 $i=1,\cdots,n$, 在点 $\boldsymbol{x}^{0}$ 的所有偏导数 $\partial f^{L}/\partial x_{i}$ 和 $\partial f^{U}/\partial x_{i}$ 存在). 称 $f$ 在 $T$ 上是弱可微的, 如果它在每一点 $\boldsymbol{x}\in T$ 是弱可微的.

(ii) 称 $f$ 在点 $\boldsymbol{x}^{0}$ 是弱连续可微的, 如果 $f^{L}$ 和 $f^{U}$ 在点 $\boldsymbol{x}^{0}$ 连续可微(这蕴含在点 $\boldsymbol{x}^{0}$ 的某个邻域内, $f^{L}$ 和 $f^{U}$ 的所有偏导数都存在, 且在点 $\boldsymbol{x}^{0}$ 连续). 称 $f$ 在 $T$ 上是弱连续可微的, 如果它在每一点 $\boldsymbol{x}\in T$ 是弱连续可微的.

(iii) 称 $f$ 在点 $\boldsymbol{x}^{0}$ 存在第 $i$ 个 H-偏导数$A_{i}(\boldsymbol{x}^{0})=[a_{i}^{L}(\boldsymbol{x}^{0}),a_{i}^{U}(\boldsymbol{x}^{0})]$, 如果区间值函数 $g(x_{i})=f(x_{1}^{0},\cdots,x_{i-1}^{0},x_{i},x_{i+1}^{0},\cdots,x_{n}^{(0)})$ 在点 $x_{i}^{0}$ 是 H-可微的, 且 H-导数是 $A_{i}(\boldsymbol{x}^{0})$. 这时也记为 $(\partial f/{\partial x_{i}})_H(\boldsymbol{x}^{0})=A_i(\boldsymbol{x}^{0})$.

(iv) 称 $f$ 在点 $\boldsymbol {x}^{0}$ 是H-可微的, 如果在点 $\boldsymbol{x}^{0}$, H-偏导数 $(\partial f/{\partial x_{1}})_{H}$, $\cdots$, $(\partial f/{\partial x_n})_{H}$ 之一存在, 且余下的 $n-1$ 个 H-偏导数在点 $\boldsymbol{x}^{0}$ 的某个邻域内存在且在点 $\boldsymbol{x}^{0}$ 连续. 称 $f$ 在 $T$ 上是 H-可微的, 如果它在每一个点 $\boldsymbol{x}\in T$ 是 H-可微的.

(v) 称 $f$ 在点 $\boldsymbol {x}^{0}$ 是连续H-可微的, 如果在点 $\boldsymbol{x}^{0}$ 的某个邻域上, 所有 H-偏导数 $(\partial f/{\partial x_{1}})_{H},$ $\cdots, (\partial f/{\partial x_{n}})_{H}$ 都存在并且在点 $\boldsymbol{x}^{0}$ 连续. 称 $f$ 在 $T$ 上是连续 H-可微的, 如果它在每一个点 $\boldsymbol{x}\in T$ 是连续 H-可微的.

由定义 2.3 容易得到如下结果.

命题 2.2^{[19, 命题4.6]} 设 $f$ 是定义在 $T\subseteq \mathbb{R}^n$ 上的区间值函数. 如果 $f$ 在点 $\boldsymbol{x}^{0}\in T$ 是 H-可微的, 那么 $f$ 在点 $\boldsymbol{x}^{0}$ 是弱可微的. 如果 $f$ 在点 $\boldsymbol{x}^{0}\in T$ 是连续 H-可微的, 那么 $f$ 在点 $\boldsymbol{x}^{0}$ 是弱连续可微的.

设 $f:\mathbb{R}^n\rightarrow \mathcal{I}_\mathbb{R}$ 是一个区间值函数. 设 $g_{i}:\mathbb{R}^{n}\to\mathbb{R}$ $(i=1,\cdots,m)$ 和 $h_{j}:\mathbb{R}^{n}\to\mathbb{R}$ $(j=1,\cdots,p)$ 是连续可微函数. 本文考虑如下的区间值优化问题, 记为 IVOP($f,g,h$)

称 $\Omega(g,h):=\{\boldsymbol{x}\in \mathbb{R}^{n}| g_{i}(\boldsymbol{x})\leq0, i=1,\cdots,m, h_{j} (\boldsymbol{x}) =0, j=1,\cdots,p\}$ 是问题 IVOP$(f, g,h$) 的可行集. 记 $I(\boldsymbol{x}^{0})=\{i\in(1,\cdots,m)\mid g_{i}(\boldsymbol{x}^{0})=0\}$. 在模型 IVOP($f,g,h$) 中若不考虑等式约束, 则该模型及可行集分别记为 IVOP($f,g$) 和 $\Omega(g)$.

类似于 IVOP($f,g$) 第 I 型解[定义5.1]和 IVOP($f,g,h$) 局部 LU-解[定义3.1] 的概念, 我们引入 IVOP($f,g,h$) 局部 LU-解的概念. 局部 LU-解概念通过偏序 $\preceq_{LU}$ 引入.

定义 2.4 称问题 IVOP($f,g,h$) 的可行点 $\boldsymbol{x}^{0}\in\Omega$ 是局部 LU-解, 如果存在 $\delta>0$ 使得不存在点$\bar{\boldsymbol{x}}\in B(\boldsymbol{x}^{0},\delta)\cap\Omega(g,h)$ 满足 $f(\bar{\boldsymbol{x}})\prec_{LU}f(\boldsymbol {x}^{0})$.

我们回顾一下文献 [19] 引入的区间值函数的凸性概念 (也可参考文献 [3]).

定义 2.5^{[3, 定义2.1]} 设 $T\subseteq\mathbb{R}^n$ 是非空凸集, $f:T\rightarrow\mathcal{I}_\mathbb{R}$ 是区间值函数. 称 $f$ 在 $T$ 上是 (严格) LU-凸的, 如果对于所有的 $\lambda\in[0,1]$ 和任意的 $\boldsymbol{x},\boldsymbol{y}\in T$, 都有不等式

成立.

由定义 2.5, 容易得到如下命题.

命题 2.3^{[19, 命题6.1(i)]} 区间值函数 $f$ 在 $T\subseteq\mathbb{R}^{n}$ 上是 (严格) LU-凸的, 当且仅当 $f^{L}$ 和 $f^{U}$ 在 $T$ 上是 (严格) 凸的.

这一节, 我们把实值优化问题的 KKT 必要条件推广到区间值优化问题. 为此, 我们首先给出如下引理, 其证明与文献 [3, 命题2.14] 的证明类似.

引理 3.1 如果 IVOP($f,g,h$) 的可行点 $\boldsymbol{x}^{0}$ 是局部 LU-解, 那么 $\boldsymbol{x}^{0}$ 是问题 (OP1) 和 (OP2) 的局部极小点, 其中

证 设 $\boldsymbol{x}^{0}\in\Omega(g,h)$ 是 IVOP($f,g,h)$ 的局部 LU-解, 则存在实数 $\delta>0$ 使得不存在 $\bar{\boldsymbol{x}}\in B(\boldsymbol{x}^{0},\delta)\cap\Omega(g,h)$ 满足$f(\boldsymbol{\bar{x}})\prec_{LU}f(\boldsymbol{x}^{0})$. 这意味着, 不存在 $\boldsymbol{\bar{x}}\in B(\boldsymbol{x}^{0},\delta)\cap\Omega(g,h)$ 使得

假设点 $\boldsymbol{x}^{0}$ 不是问题 (OP1) 的局部极小值点, 则对任意 $\delta>0$ 存在 $\boldsymbol{x}^{*}\in B(\boldsymbol{x}^{0},\delta)\cap\Omega(g,h)$ 使得

这与 (3.1) 式矛盾, 故 $\boldsymbol{x}^{0}$ 是问题 (OP1) 的局部极小值点. 同理可证, $\boldsymbol{x}^{0}$ 也是问题 (OP2) 的局部极小值点.

定义 3.1 称约束函数 $g_{i}\ (i=1,\cdots,m)$ 和 $h_{j}\ (j=1,\cdots,p)$ 在点 $\boldsymbol{x}^{0}$ 满足 Mangasarian-Fromovitz 约束规范 (简记为 MFCQ), 如果 $\nabla h_{j}(\boldsymbol{x}^{0})\ (j=1,\cdots,p)$ 线性无关, 且存在 $\boldsymbol{d}\in \mathbb{R}^{n}$ 使得对每一个 $i\in I(\boldsymbol{x}^{0})$ 有 $\langle \nabla g_{i}(\boldsymbol{x}^{0}),\boldsymbol{d}\rangle<0$ 和每一个 $j=1,\cdots,p$ 有 $\langle \nabla h_{j}(\boldsymbol{x}^{0}), \boldsymbol{d}\rangle=0$, 其中 $\langle \cdot,\cdot\rangle$ 是欧几里德内积.

注 3.1 对于 MFCQ, 我们指出

(i) 若不含等式约束, 则 MFCQ 变为问题 IVOP$(f,g)$ 的 Cottle 约束规范 (简记为 CCQ), 即存在 $\boldsymbol{d}\in \mathbb{R}^{n}$ 使得对每一个 $i\in I(\boldsymbol{x}^{0})$ 有 $\langle \nabla g_{i}(\boldsymbol{x}^{0}),\boldsymbol{d}\rangle<0$.

(ii) CCQ 不是 MFCQ 的特例. 因为当 $h_j(\boldsymbol{x})\equiv0$ ($j=1,\cdots,p$) 时, 有 $\nabla h_j(\boldsymbol{x}^0)\equiv\boldsymbol{0}$, 那么 $\langle \nabla h_{j}(\boldsymbol{x}^{0}), \boldsymbol{d}\rangle=0$ ($j=1,\cdots,p$). 然而 $\nabla h_{j}(\boldsymbol{x}^{0})$ ($j=1,\cdots,p$) 是线性相关, MFCQ 不成立.

(iii) 例 3.1 说明 MFCQ 对问题 IVOP($f,g,h$) 是合理的.

引理 3.2^[5] 设 $\boldsymbol{x}^{*}$ 是如下问题的局部极小值点

其中 $f, g_{i}, h_{j}: \mathbb{R}^{n}\rightarrow\mathbb{R}$ 是连续可微函数, 则存在 $\mu_{0}^{*}$、 $\mu_{1}^{*},\cdots,\mu_{m}^{*}$ 和 $\lambda_{1}^{*},\cdots,\lambda_{p}^{*}$ 满足如下条件

(i) $\mu_{0}^{*}\nabla f(\boldsymbol{x}^{*})+\sum\limits_{i=1}^{m}\mu_{i}^{*} \nabla g_{i}(\boldsymbol{x}^{*})+\sum\limits_{j=1}^p\lambda_{j}^{*}\nabla h_j(\boldsymbol{x}^{*})= \boldsymbol{0};$

(ii) $\mu_{i}^{*}\geq 0,\ i=0,1,\cdots,m$;

(iii) $\mu_{0}^{*}, \mu_{1}^{*},\cdots,\mu_{m}^{*},\lambda_{1}^{*},\cdots,\lambda_{p}^{*}$ 不全为零;

(iv) 对 $\boldsymbol{x}^{*}$ 的每一个邻域 $U$, 存在 $\boldsymbol{x}\in U$ 使得满足 $\lambda_{j}^{*}\neq0$ 的每一个 $j$ 都有$\lambda_{j}^{*}h_j(\boldsymbol{x})>0$, 满足 $\mu_{i}^{*}\neq0$ 的每一个 $i$ 都有 $\mu_{i}^{*}g_{i}(\boldsymbol{x})>0$.

定理 3.1 设 $f$ 是 $\mathbb{R}^{n}$ 上的弱连续可微的区间值函数, 函数 $g_{i}$ $(i=1,\cdots,m)$, $h_{j}$ $(j=1,\cdots,p)$ 是$\mathbb{R}^{n}$ 上的连续可微函数. 如果可行点 $\boldsymbol{x}^{0}$ 是 IVOP($f,g,h$) 的局部 LU-解, 且在点 $\boldsymbol{x}^{0}$ 满足 MFCQ, 则存在 $(\beta_{L},\beta_{U},\boldsymbol{\mu}, \boldsymbol{\lambda}) \in\mathbb{R}_{+} \times \mathbb{R}_{+}\times \mathbb{R}^{m}_{+}\times \mathbb{R}^{p}$ 使得

(K1) $\beta_{L}\nabla f^{L}(\boldsymbol{x}^{0})+\beta_{U}\nabla f^{U}(\boldsymbol{x}^{0})+\sum\limits_{i=1}^{m} \mu_{i} \nabla g_{i}(\boldsymbol{x}^{0} )+\sum\limits_{j=1}^p\lambda_{j} \nabla h_{j}(\boldsymbol{x}^{0})= \boldsymbol{0},$ 其中 $\beta_{L},\beta_{U}$ 不全为零;

(K2) $g_{i}(\boldsymbol{x}^0)\mu_{i}=0, i=1,\cdots,m$.

证 因为 $\boldsymbol{x}^{0}$ 是 IVOP($f,g,h$) 的局部 LU-解, 由引理 3.1 可知, $\boldsymbol{x}^{0}$ 是问题 (OP1) 的局部极小值点. 根据引理 3.2, 存在 $\beta_{L}\in \mathbb{R}_{+}, \beta_{U}\in \mathbb{R}_{+}$, $\mu_{i}\in\mathbb{R}_{+}$ $(i=1,\cdots,m)$ 和 $\lambda_{j}\in\mathbb{R}$ $(j=1,\cdots,p)$ 使得

其中$\beta_{L},\beta_{U},\mu_{1},\cdots,\mu_{m}, \lambda_{1},\cdots,\lambda_{p}$ 不全为零, 并且存在 $\boldsymbol{x}\in U$ 使得满足 $\lambda_{j}\neq0$ 的每一个 $j$ 都有 $\lambda_{j}h_{j}(\boldsymbol{x})>0$, 满足 $\mu_{i}\neq0$ 的每一个 $i$ 都有 $\mu_{i}g_{i}(\boldsymbol{x})>0$, 其中 $U$ 是点 $\boldsymbol{x}^{0}$ 任意邻域.

接着, 证明对每一个 $i=1,\cdots,m$, $\mu_{i} g_{i}(\boldsymbol{x}^0 )=0$. 事实上, 由于 $\boldsymbol{x}^{0}$ 是可行点, 且 $\boldsymbol{\mu} \in \mathbb{R}^{m}_{+}$, 可得 $\mu_{i}g_{i}(\boldsymbol{x}^0)\leq0$ $(i=1,\cdots,m)$. 关于 $\mu_{i}$, 我们考虑两个情形. (情形1: $\mu_{i}=0$) 容易得到 $\mu_{i}g_{i}(\boldsymbol{x}^0)=0$. (情形2: $\mu_{i}>0$) 我们声明 $\mu_{i}g_{i}(\boldsymbol{x}^{0})=0$. 否则, 我们有 $\mu_{i}g_{i}(\boldsymbol{x}^{0})<0$, 从而由 $g_{i}$ 的连续性可得 $\lim\limits_{\boldsymbol{x}\rightarrow\boldsymbol{x}^{0}}\mu_{i}g_{i}(\boldsymbol{x})=\mu_{i}g_{i}(\boldsymbol{x}^{0})<0$. 这样, 有极限的保号性知存在 $\delta>0$ 使得对于满足 $\|\boldsymbol{x}-\boldsymbol{x}^{0}\|<\delta$ 的每一个 $\boldsymbol{x}$ 都有 $\mu_{i}g_{i}(\boldsymbol{x})<0$. 这与引理 3.2 的条目 (iv) 矛盾. 因此 $\mu_i g_{i}(\boldsymbol{x}^{0})=0$.

最后, 证明 $\beta_{L}$ 和 $\beta_{U}$ 不全为零. 事实上, 若 $\beta_{L}=\beta_{U}=0$, 由 (3.2) 式可得

对任意的 $i\notin I(\boldsymbol{x}^{0})$, 由 $\mu_{i} g_{i}(\boldsymbol{x}^{0})=0$ 可得 $\mu_{i}=0$. 进而, 得到$\sum\limits_{i\notin I(\boldsymbol{x}^{0})}\mu_{i} \nabla g_{i}(\boldsymbol{x}^{0})=0$. 这使得 (3.3) 式变成

由于 $\beta_{L},\beta_{U},\mu_{1},\cdots,\mu_{m}, \lambda_{1},\cdots,\lambda_{p}$ 不全为零, 则至少存在一个 $i\in I(\boldsymbol{x}^{0})$ 使得 $\mu_{i}>0$. 否则, 我们有 $\sum\limits_{j=1}^{p}\lambda_j\nabla h_{j}(\boldsymbol{x}^{0})= \boldsymbol{0}$, 且 $\lambda_{1},\cdots,\lambda_{p}$ 不全为零. 另一方面, 由点 $\boldsymbol{x}^{0}$ 满足MFCQ可知, $\nabla h_{1}(\boldsymbol{x}^{0}),\cdots,$ $\nabla h_{p}(\boldsymbol{x}^{0})$ 线性无关, 因此产生矛盾. 根据在点 $\boldsymbol{x}^{0}$ 满足MFCQ 可知, 存在$\boldsymbol{d}\in\mathbb{R}^{n}$ 使得对每一个 $i\in I(\boldsymbol{x}^{0})$ 都有 $\langle \nabla g_{i}(\boldsymbol{x}^{0}),\boldsymbol{d}\rangle<0$, 且对每一个 $j=1,\cdots,p$, 都有 $\langle \nabla h_{j}(\boldsymbol{x}^{0}), \boldsymbol{d}\rangle=0$. 由于$\boldsymbol{\mu}\in\mathbb{R}_{+}^{m}$, $\boldsymbol{\lambda}\in\mathbb{R}^{p}$, 每一个 $i\notin I(\boldsymbol{x}^0)$ 都有$\mu_{i}=0$, 且至少存在一个 $i\in I(\boldsymbol{x}^0)$ 使得 $\mu_{i}>0$, 可得

另一方面, 由 (3.3) 式可得 $\Big\langle\sum\limits_{i=1}^{m} \mu_{i} \nabla g_{i}(\boldsymbol{x}^{0})+\sum\limits_{j=1}^{p}\lambda_{j}\nabla h_{j}(\boldsymbol{x}^{0}),\boldsymbol{d}\Big\rangle=0.$ 矛盾. 所以 $\beta_{L}$ 和 $\beta_{U}$ 不全为零. 证毕.

如下例子说明定理 3.1.

例 3.1 设 ${\boldsymbol{x}\in \mathbb{R}^{3}}$. 考虑如下区间值优化问题

其中

易知 $\Omega(g,h)=\{\boldsymbol{x}\in\mathbb{R}^{3}| g_{i}(\boldsymbol{x})\leq0, i=1,\cdots,6; h_{j}(\boldsymbol{x})=0, j=1,2,3\}=\{\boldsymbol{x}=(x_{1},x_{2},x_{3})^{\top}$ $\in\mathbb{R}^{3}| x_{1}=x_{2}=x_{3}, 0\leq x_{1}\leq 1\}$, $f^{L}(\boldsymbol{x})$, $f^{U}(\boldsymbol{x})$, $g_{i}(\boldsymbol{x})\ (i=1,\cdots,6)$ 和 $h_{j}(\boldsymbol{x})\ (j=1,2,3)$ 是连续可微的凸函数, 因此 $f$ 是弱连续可微的.

我们声明点 $\boldsymbol{x}^{0}=(1,1,1)^{\top}$ 是问题的一个LU-解. 事实上, 显然 $\boldsymbol{x}^{0}$ 是可行点, $f^{L}(\boldsymbol{x}^{0})=-3$ 和 $f^{U}(\boldsymbol{x}^{0})=4$. 此外, 不存在可行点 $\boldsymbol{x}=(x_{1},x_{2},x_{3})\in \Omega(g,h)$ 使得

即不存在可行点 $\boldsymbol{x}=(x_{1},x_{2},x_{3})\in\Omega(g,h)$ 使得 $f(\boldsymbol{x})\prec_{LU}f(\boldsymbol{x}^{0})$. 因此, 点 $\boldsymbol{x}^{0}$ 是问题的一个LU-解.

接着, 在点 $\boldsymbol{x}^{0}$ 满足 MFCQ. 事实上, 易知

因此, 矩阵 $(\nabla h_{1}(\boldsymbol{x}^{0}), \nabla h_{2}(\boldsymbol{x}^{0}), \nabla h_{3}(\boldsymbol{x}^{0}))$ 的秩等于$3$, 这意味着 $\nabla h_{1}(\boldsymbol{x}^{0})$, $\nabla h_{2}(\boldsymbol{x}^{0})$ 和 $\nabla h_{3}(\boldsymbol{x}^{0})$ 线性无关. 另外, 取向量 $\boldsymbol{d}=(-1,-1,-1)^T$, 可得 $\langle\nabla h_{j}(\boldsymbol{x}^{0}),\boldsymbol{d}\rangle=0,$ $j=1,2,3$ 和 $\langle\nabla g_{i}(\boldsymbol{x}^{0}),\boldsymbol{d}\rangle<0,$ $i=2,4,6$. 这说明在点 $\boldsymbol{x}^{0}$ 满足 MFCQ.

因此, 由定理 3.1 可知, 存在乘子 $\boldsymbol{\mu} \in \mathbb{R}^{6}_{+}$, $\boldsymbol{\lambda} \in \mathbb{R}^{3}$, $\beta_{L}\in \mathbb{R}_{+}$, $\beta_{U}\in \mathbb{R}_{+}$ 使得

(E1-1) $\beta_{L}\nabla f^{L}(\boldsymbol{x}^{0})+\beta_{U}\nabla f^{U}(\boldsymbol{x}^{0})+\sum\limits_{i=1}^{6} \mu_{i} \nabla g_{i}(\boldsymbol{x}^{0})+\sum\limits_{j=1}^{3}\lambda_{j} \nabla h_{j}(\boldsymbol{x}^{0})= \boldsymbol{0}$, 其中 $\lambda_{L},\lambda_{U}$ 不同时为 0;

(E1-2) $g_{i}(\boldsymbol{x}^{0})\mu_{i}=0, i=1,\cdots,6$.

事实上, 取 $\beta_{L}=7$, $\beta_{U}=3$, $\mu_{1}=\mu_{3}=\mu_{5}=0$, $\mu_{2}=\mu_{4}=1$, $\mu_{6}=7$ 和 $\lambda_{1}=\lambda_{2}=\lambda_{3}=1$, 容易验证 (E1-1) 和 (E1-2) 成立.

类似定理 3.1 的证明, 我们得到问题 IVOP($g$) 局部 LU-解的必要条件. 结合 MFCQ 和 CCQ 的区别, 如下定理并不能看作定理 3.1 的一个特例.

定理 3.2 设 $f$ 是 $\mathbb{R}^n$ 上的弱连续可微的区间值函数. 如果可行点 $\boldsymbol{x}^{0}$ 是问题 IVOP($g$)的一个局部 LU-解, 且在点 $\boldsymbol{x}^{0}$上满足 CCQ, 那么存在乘子 $(\beta_{L},\beta_{U},\boldsymbol{\mu}) \in \mathbb{R}_{+} \times \mathbb{R}_{+}\times \mathbb{R}^{m}_{+}$ 使得

(K1') $\beta_{L}\nabla f^{L}(\boldsymbol{x}^{0})+\beta_{U}\nabla f^{U}(\boldsymbol{x}^{0})+\sum\limits_{i=1}^{m} \mu_{i} \nabla g_{i}(\boldsymbol{x}^{0} )= \boldsymbol{0}$, 其中 $\beta_{L},\beta_{U}$ 不同时为 0;

(K2') $g_{i}(\boldsymbol{x}^0)\mu_{i}=0, i=1,\cdots,m$.

注 3.2 定理 3.2 与文献 [18, 定理 3.6] 作比较, 虽然他们考虑了更一般的模型, 其中的目标函数和约束函数可能是不可微的, 当 Slater 型约束规范 (简记为 SCQ) 不满足, 则文献 [18, 定理 3.6] 就无法使用. 如下例子说明这一点.

例 3.2 设 $\boldsymbol{x}\in\mathbb{R}^{2}$, 考虑如下问题

容易验证可行点 $(1,1)^{\top}$ 是一个 LU-解. 由于函数 $f^{L}=x_{1}-x_{2}^{2}$ 和 $f^{U}=x_{1}-x_{2}^{2}+2$ 是非凸的, 那么 SCQ 不满足. 因此我们无法通过文献 [18, 定理 3.6] 来获得问题的 LU-解的必要条件.

然而, 易知 $f$ 是弱连续可微的. 此外, 我们有 $\nabla g((1,1)^{\top})=(-2,4)^{\top}$. 取 $\boldsymbol{d}=(d_{1},d_{2})^{\top}(d_{1}>0, d_{2}<0)$, 可得 $\langle \nabla g((1,1)^{\top}),\boldsymbol{d}\rangle<0$, 这意味在点 $(1,1)^{\top}$ 满足 CCQ. 因此, 由定理 3.2 可知, 存在乘子$(\beta_{L},\beta_{U},\boldsymbol{\mu}) \in \mathbb{R}_{+} \times \mathbb{R}_{+}\times \mathbb{R}^{m}_{+}$使得

(E2-1) $\beta_{L}\nabla f^{L}((1,1)^{\top})+\beta_{U}\nabla f^{U}((1,1)^{\top})+\mu\nabla g((1,1)^{\top})= \boldsymbol{0}$, 其中 $\beta_{L},\beta_{U}$ 不同时为 0;

(E2-2) $g((1,1)^{\top})\mu=0$.

事实上, 取 $\beta_{L}=1$, $\beta_{U}=1$, $\mu=1$, 容易验证 (E2-1) 和 (E2-2) 成立.

上一节讨论了, 当模型满足适当的约束规范时, KKT 条件是模型的可行点成为局部 LU-解的必要条件. 然而, 当约束规范不满足时, 则不能保证 KKT 条件还是必要条件. 例如, 设 ${\boldsymbol{x}\in \mathbb{R}^{3}}$, 我们考虑问题

其中

令$\boldsymbol{x}^{0}=(1,1,1)^{\top}$. 易知 $\boldsymbol{x}^{0}$ 是一个可行点, $f^L(\boldsymbol{x}^{0})=-3$, $f^U(\boldsymbol{x}^{0})=3$ 和 $I(\boldsymbol{x}^{0})=\{2,4,5\}$. 又因为 $\nabla g_{2}(\boldsymbol{x}^{0})=(1,0,0)^{\top}$, $\nabla g_{4}(\boldsymbol{x}^{0})=(0,1,0)^{\top}$ 和 $\nabla g_{5}(\boldsymbol{x}^{0})=(0,0,0)^{\top}$, 易知不存在向量 $\boldsymbol{d}\in \mathbb{R}^{3}$ 使得 $\langle \nabla g_{i}(\boldsymbol{x}^{0}), \boldsymbol{d}\rangle<0$ $(i\in I(\boldsymbol{x}^{0})=\{2,4,5\})$. 因此, 在点 $\boldsymbol{x}^{0}$ 不满足 CCQ. 很显然, $f^{L}$ 是一个非凸函数, 所以在点$\boldsymbol{x}^{0}$ 也不满足 SCQ. 为了应对解决当约束规范不满足时的问题, Lai-Singh-Mishra^[13]引入了区间值优化问题的近似 KKT (简记为 AKKT) 条件, 并证明了 AKKT 条件不需要约束规范就成为 LU-解的必要条件. 例子 4.2 说明了 AKKT 条件在 $(0,-1)^{\top}$ 成立, 但是 $(0,-1)^{\top}$ 不是 LU-解. 因此, 我们引进 IVOP($f,g,h$) 的弱互补近似 KKT (简记为 W-CAKKT) 条件.

定义 4.1 设 $f$ 是 $\mathbb{R}^{n}$ 上的弱连续可微的区间值函数. 称问题(IVOP)的可行点 $\boldsymbol{x}^{0}$ 满足 W-CAKKT 条件, 如果存在序列 $\{\boldsymbol{x}^{k}\}\subset \mathbb{R}^{n}$ 和 $\{(\beta_{L}^{k},\beta_{U}^{k},\boldsymbol{\mu}^{k}, \boldsymbol{\lambda}^{k})\} \subset \mathbb{R}_{+} \times \mathbb{R}_{+}\times \mathbb{R}^{m}_{+}\times \mathbb{R}^{p}$ 使得

(A1) $\lim\limits_{k\rightarrow\infty}\boldsymbol{x}^{k} =\boldsymbol{x}^{0}$;

(A2) $\beta^{k}_{L}+\beta^{k}_{U}=1$;

(A3) $\lim\limits_{k\rightarrow\infty}\Big(\sum\limits_{i=1}^{m}|\mu_{i}^{k}g_{i}(\boldsymbol{x}^{k})|+\sum\limits_{j=1}^{p}|\lambda_{j}^{k}h_{j}(\boldsymbol{x}^{k})|\Big)=0;$

(A4) $\lim\limits_{k\rightarrow \infty}\Big\|\beta^{k}_{L}\nabla f^{L}(\boldsymbol{x}^{k})+\beta^{k}_{U}\nabla f^{U}(\boldsymbol{x}^{k})+\sum\limits_{i=1}^{m} \mu_{i}^{k} \nabla g_{i}(\boldsymbol{x}^{k})+ \sum\limits_{j=1}^{p} \lambda_{j}^{k} \nabla h_{j}(\boldsymbol{x}^{k} )\Big\|=0.$

注 4.1 当目标区间值函数中的 $f^{L}=f^{U}$, 则 IVOP($f,g,h$) 的 W-CAKKT 条件退化为 Andreani-Martínez-Svaiter^[2] 引入的实值优化问题 OP($f,g,h$) 的 CAKKT 条件.

在证明 W-CAKKT 条件是 LU-解的必要性条件之前, 先回顾一些必要的概念.

定义 4.2^[4] 设函数 $\varphi:\mathbb{R}^n\rightarrow\mathbb{R}$ 是局部 Lipschitz 连续函数, $\boldsymbol{x}\in\mathbb{R}^{n},\ \boldsymbol{d}\in \mathbb{R}^{n}$

(i) $\varphi$ 在点 $\boldsymbol{x}$ 沿方向 $\boldsymbol{d}\in\mathbb{R}^{n}$ 的 Clarke 方向导数为

(ii) $\varphi$ 在点 $\boldsymbol{x}$ 处 Clarke 次微分为

定义 4.3^[4] 称函数 $\varphi:\mathbb{R}^{n}\rightarrow \mathbb{R}$ 在点 $\boldsymbol{x}\in\mathbb{R}^{n}$ 次可微正则, 若 $\varphi$ 在$\boldsymbol{x}$ 局部 Lipschitz 连续, 且对所有的 $\boldsymbol{d}\in\mathbb{R}^{n}$, $\varphi ^{\prime}(\boldsymbol{x},\boldsymbol{d})$ 存在且满足 $\varphi^{\prime}(\boldsymbol{x},\boldsymbol{d})= \varphi^{\circ}(\boldsymbol{x},\boldsymbol{d})$.

引理 4.1^[4] 有如下性质成立

(i) 若 $\varphi:\mathbb{R}^{n}\rightarrow \mathbb{R}$ 在点 $\boldsymbol{x}\in\mathbb{R}^{n}$ 连续可微, 则 $\varphi$ 在 $\boldsymbol{x}$ 局部 Lipschitz 连续, 且 $\partial \varphi(\boldsymbol{x})=\{\nabla \varphi(\boldsymbol{x})\}$.

(ii) 设 $\varphi:\mathbb{R}^{n}\rightarrow \mathbb{R}$ 是凸函数, 对任意的 $\boldsymbol{x}\in\mathbb{R}^{n}$, $\varphi$ 在 $\boldsymbol{x}$ 局部 Lipschitz 连续.

(iii) 设 $\varphi_{i}:\mathbb{R}^{n}\rightarrow \mathbb{R}$ $(i =1,\cdots,m)$ 均为局部 Lipschitz 连续函数. 定义函数 $\varphi:\mathbb{R}^{n}\rightarrow \mathbb{R}$ 为 $\varphi(\boldsymbol{x}):=\sum\limits_{i=1}^{m}\alpha_{ i}\varphi_{i}(\boldsymbol{x})$, 则 $\varphi$ 是局部 Lipschitz 连续函数, 且对任意的 $\boldsymbol{x}\in\mathbb{R}^{n}$ 和 $\alpha_{i}\in\mathbb{R}$ 均有 $\partial \varphi(\boldsymbol{x})\subseteq \sum\limits_{i=1}^m\alpha_{i} \partial \varphi_{i}(\boldsymbol{x})$.

(iv) 设 $\varphi:\mathbb{R}^{n}\rightarrow \mathbb{R}$ 是局部 Lipschitz 连续函数, 则函数 $\varphi^{2}$ 也是局部 Lipschitz 连续函数

注 4.2 设 $\varphi:\mathbb{R}^{n}\rightarrow \mathbb{R}$ 是凸函数, 则 $\varphi^{2}$ 局部 Lipschitz 连续函数. 事实上, 由函数$\varphi$ 的凸性容易得到 $\varphi^{2}$ 也是凸函数, 由引理 4.1 的条目 (ii), 结论显然成立.

引理 4.2^[4] 设函数 $\varphi:\mathbb{R}^{n}\rightarrow\mathbb{R}$ 局部 Lipschitz 连续. 如果 $\varphi$ 在点 $\boldsymbol{x}\in\mathbb{R}^{n}$ 达到极值, 则 $\boldsymbol{0}\in \partial \varphi (\boldsymbol{x})$.

引理 4.3^[4] 有如下性质成立

(i) 若 $\varphi:\mathbb{R}^{n}\rightarrow \mathbb{R}$ 在点 $\boldsymbol{x}\in\mathbb{R}^{n}$ 是连续可微的, 则 $\varphi$ 在点 $\boldsymbol{x}\in\mathbb{R}^{n}$ 是次可微正则的.

(ii) 设 $\varphi_{i}:\mathbb{R}^{n}\rightarrow \mathbb{R}$ ($i=1,\cdots,m$) 在点 $\boldsymbol{x}\in\mathbb{R}^{n}$ 是次可微正则的. 那么由 $\varphi(\boldsymbol{x})=\max\{\varphi_{i}(\boldsymbol{x}): i=1,\cdots,m\}$ 定义的函数 $\varphi:\mathbb{R}^{n}\rightarrow \mathbb{R}$ 在点 $\boldsymbol{x}$ 也是次可微正则的, 且 $\partial \varphi (\boldsymbol{x})={\rm conv}\{\partial \varphi_i(\boldsymbol{x})|i\in\mathcal{I}(\boldsymbol{x})\}$, 其中 $\mathcal{I}(\boldsymbol{x}):=\{i\in\{1,\cdots,m\}|\varphi_i(\boldsymbol{x})=\varphi(\boldsymbol{x})\}$.

注 4.3 假设函数 $\varphi_{i}:\mathbb{R}^{n}\rightarrow \mathbb{R}$ $(i=1, 2)$ 在 $\boldsymbol{x}\in\mathbb{R}^{n}$ 连续可微, 根据引理 4.3 和定义 4.3, 由 $\varphi(\boldsymbol{x}):=\max\{\varphi_{1}(\boldsymbol{x}),\varphi_{2}(\boldsymbol{x})\}$ 定义的函数 $\varphi: \mathbb{R}^{n}\rightarrow\mathbb{R}$ 在 $\boldsymbol{x}$ 处局部 Lipschitz 连续. 特别地, 如果区间值函数 $f$ 在 $\mathbb{R}^{n}$ 弱连续可微, 则由 $\theta(\boldsymbol{x}):=\max\{f^{L}(\boldsymbol{x})-f^{L}(\boldsymbol{x}^{0}),f^{U}(\boldsymbol{x})-f^{U}(\boldsymbol{x}^{0})\}$ 定义的函数 $\theta: \mathbb{R}^{n}\rightarrow\mathbb{R}$ 在 $\mathbb{R}^{n}$ 上局部 Lipschitz 连续.

引理 4.4 如果可行点 $\boldsymbol{x}^{0}$ 是问题 IVOP($f,g,h$) 的一个局部 LU-解, 那么 $\boldsymbol{x}^{0}$ 是问题 (OP) 的局部极小值点, 其中 $(OP)\quad \min\limits_{\boldsymbol{x}\in \Omega}\theta(\boldsymbol{x}),$ 这里 $\theta(\cdot)$ 由注 4.3 给出.

证 设 $\boldsymbol{x}^{0}$ 是问题 IVOP($f,g,h$) 的一个局部 LU-解. 那么存在 $\delta_{0}>0$ 使得不存在 $\boldsymbol{\bar{x}}\in B(\boldsymbol{x}^{0},\delta_{0})\cap\Omega$ 满足 $f(\boldsymbol{\bar{x}})\prec_{LU}f(\boldsymbol{x}^0)$. 这意味着不存在 $\boldsymbol{\bar{x}}\in B(\boldsymbol{x}^{0},\delta_{0})\cap\Omega(g,h)$ 使得

假设 $\boldsymbol{x}^{0}$ 不是问题 (OP) 的局部极小值点. 则对任意的 $\delta>0$, 存在 $\boldsymbol{x}^{*}\in B(\boldsymbol{x}^{0},\delta)\cap\Omega(g,h)$ 使得 $\theta(\boldsymbol{x}^{*})<\theta(\boldsymbol{x}^{0})$, 因此 $\left\{\begin{array}{l} f^{L}({\boldsymbol{x}}^{*})<f^{L}\left(\boldsymbol{x}^{0}\right) \\ f^{U}({\boldsymbol{x}}^{*}) < f^{U}\left(\boldsymbol{x}^{0}\right). \end{array}\right.$ 这与 (4.1) 式矛盾. 证毕.

定理 4.1(W-CAKKT 必要条件) 设$f$是弱连续可微的区间值函数, $g_{i}:\mathbb{R}^{n}\to\mathbb{R}$ $(i=1,\cdots,m)$, $h_{j}:\mathbb{R}^{n}\to\mathbb{R}$ $(j=1,\cdots,p)$ 在 $\mathbb{R}^{n}$ 上连续可微. 设 $\boldsymbol{x}^{0}$ 是问题 IVOP($f,g,h$) 的一个局部 LU-解. 那么在点 $\boldsymbol{x}^{0}$ 满足 W-CAKKT 条件.

证 由引理 4.4 可知, $\boldsymbol{x}^{0}$ 是最优化问题 (OP) 的一个局部极小点. 从而存在 $\delta>0$, 使得对任意的 $\boldsymbol{x}\in\Omega(g,h)\cap \bar{B}(\boldsymbol{x}^{0},\delta)$ 都有 $\theta(\boldsymbol{x}^{0})\leq \theta(\boldsymbol{x})$. 因此, $\boldsymbol{x}^{0}$是最优化问题

的唯一全局最小值点.

定义函数 $\Phi_{k}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ 为

对于最优化问题

我们声明函数 $\Phi_{k}$ 是集合 $\bar{B}(\boldsymbol{x}^{0},\delta)$ 上的局部 Lipschitz 连续函数. 事实上, 由注 4.3 可知, $\theta$ 是集合 $\bar{B}(\boldsymbol{x}^{0},\delta)$ 上的局部 Lipschitz 连续函数. 由注释 4.3 可知, 函数 $g_{i}(\cdot)_{+}$ 是局部 Lipschitz 连续的. 从而由引理 4.1 的条目 (iv) 可知, 函数 $g_{i}(\cdot)_{+}^{2}$ ($i=1,\cdots,m$)在集合$\bar{B}(\boldsymbol{x}^{0},\delta)$ 上也是局部 Lipschitz 连续的. 由引理 4.1 的条目 (i) 和条目 (iv) 可知, 函数 $h_{j}^{2}$ ($j=1,\cdots,p$) 在集合 $\bar{B}(\boldsymbol{x}^{0},\delta)$ 上也是局部 Lipschitz 连续的. 因为范数 $\|\cdot\|$ 是凸的, 由注 4.2 可知, 函数 $\|\cdot- \boldsymbol{x}^{0}\|^{2}_{2}$ 也是局部 Lipschitz 连续的. 这样, 由引理 4.1 的条目 (iii) 可知, 函数 $\Phi_{k}$ 在集合 $\bar{B}(\boldsymbol{x}^{0},\delta)$ 上是局部 Lipschitz 连续的. 这意味着 $\Phi_{k}$ 在集合 $\bar{B}(\boldsymbol{x}^{0},\delta)$ 上是连续的. 因为集合 $\bar{B}(\boldsymbol{x}^{0},\delta)$ 是非空紧的, 所以对每一个$k\in\mathbb{N}$, 最优化问题 (4.3) 存在最优解 $\boldsymbol{x}^{k}$.

接着, 我们证明 $\{\boldsymbol{x}^{k}\}$ 收敛于 $\boldsymbol{x}^{0}$. 事实上, 设 $\boldsymbol{z}$ 是序列 $\{\boldsymbol{x}^{k}\}$ 的一个聚点, 这意味着存在无穷指标集 $\mathcal{K}\subset \mathbb{N}$ 使得 $\lim\limits_{k\in\mathcal{K}}\boldsymbol{x}^{k} =\boldsymbol{z}$. 由 $\boldsymbol{x}^{k}$ 的定义和 $\boldsymbol{x}^{0}\in \Omega(g,h)$ 可得 $\Phi_{k}(\boldsymbol{x}^{k})\leq \Phi_{k}(\boldsymbol{x}^{0})$, 即

因此, 对充分大的 $k\in\mathcal{K}$ 可得

由 $\sum\limits_{i=1}^{m} kg_{i}( \boldsymbol{z})^2_++\sum\limits_{j=1}^{p}k h_{j}(\boldsymbol{z})^{2}\geq0$ 可得

接着, 我们声明 $\boldsymbol{z}$ 是最优化问题 (4.2) 的一个可行点. 事实上, 由 $\|\boldsymbol{x}^{k}-\boldsymbol{x}^{0}\|\leq\delta$ 可知 $\| \boldsymbol{z}-\boldsymbol{x}^{0}\|\leq\delta$. 假设 $\boldsymbol{z}\notin \Omega(g,h)$, 那么可得 $\sum\limits_{i=1}^{m}g_{i}(\boldsymbol{z})_{+}^{2}+\sum\limits_{j=1}^{p} h_{j}(\boldsymbol{z})^{2}>0.$ 因此, 存在 $b>0$ 使得对于足够大的 $k\in\mathcal{K}$, 有

由 $\boldsymbol{x}^{0}\in \Omega(g,h)$ 可知对每一个 $i=1,\cdots,m$, 有 $g_{i}(\boldsymbol{x}^{0})_{+}=0$, 和每一个 $j=1,\cdots,p$, 有 $h_{j}(\boldsymbol{x}^{0})=0$, 从而

由 (4.6) 和 (4.7) 式可得

由 $\theta(\cdot)$ 的连续性, $\lim\limits_{k\in\mathcal{K}}\boldsymbol{x}^{k} =\boldsymbol{z}$ 和 $b>0$ 可知对足够大的 $k\in\mathcal{K}$ 有 $kb+\theta(\boldsymbol{x}^{k})-\theta(\boldsymbol{x}^{0})>0$. 这样, 我们有 $\theta(\boldsymbol{x}^{k})+\sum\limits_{i=1}^{m}kg_{i}(\boldsymbol{x}^{k})_{+}^{2}+\sum\limits_{j=1}^{p}k h_{j}(\boldsymbol{x}^{k})^{2} >\theta(\boldsymbol{x}^0)+\sum\limits_{i=1}^mkg_i(\boldsymbol{x}^{0})_+^2+\sum\limits_{j=1}^pk h_j(\boldsymbol{x}^0)^2,$ 从而 $\Phi_{k}(\boldsymbol{x}^{k})> \Phi_{k}(\boldsymbol{x}^{0})$. 根据 $\boldsymbol{x}^0\in\bar{B}(\boldsymbol{x}^0,\delta)$, 这与 $\boldsymbol{x}^k$ 的定义矛盾. 因此, $z\in \Omega(g,h)$, 从而 $\boldsymbol{z}$ 是最优化问题 (4.2) 的可行点. 这样可推知 $\sum\limits_{i=1}^{m} kg_{i}(\boldsymbol{z})_+^2+\sum\limits_{j=1}^{p}k h_j(\boldsymbol{z})^2=0$. 由于 $\boldsymbol{x}^{0}$ 是最优化问题 (4.2) 的唯一全局极小点, 所以

由 (4.5) 和 (4.8) 式可得

从而 $\theta(\boldsymbol{z})\leq \theta(\boldsymbol{x}^0)$. 另一方面, 由前面所证的 $z\in \Omega(g,h)\cap\bar{B}(\boldsymbol{x}^{0},\delta)$ 可知 $\theta(\boldsymbol{x}^0)\leq\theta(\boldsymbol{z})$. 这样, 我们得到 $\theta(\boldsymbol{z})=\theta(\boldsymbol{x}^0)$. 结合 (4.9) 式可推出 $\boldsymbol{z}=\boldsymbol{x}^0$.

注意到 $\boldsymbol{z}$ 是序列 $\{\boldsymbol{x}^{k}\}$ 的任一个聚点, 故 $\lim\limits_{k \rightarrow\infty}\boldsymbol{x}^{k} =\boldsymbol{x}^0$. 这蕴含对足够大的 $k\in\mathbb{N}$ 有 $\|\boldsymbol{x}^k-\boldsymbol{x}^0\|<\delta$.

由 $\boldsymbol{x}^k$ 的定义和引理 4.2 可知 $\boldsymbol{0}\in\partial\Phi_{k}(\boldsymbol{x}^{k})$. 由引理 4.1 和引理 4.3 可得

因此, 存在 $\beta_{L}^{k}\geq 0$, $\beta_{U}^{k}\geq0$ 满足 $\beta_{L}^{k}+\beta_{U}^{k}=1$ 和

令

由 (4.10), (4.11) 式和 $\lim\limits_{k\rightarrow\infty}\boldsymbol{x}^{k} =\boldsymbol{x}^{0}$ 可得

由 $\theta(\cdot)$ 的连续性, $\lim\limits_{k\rightarrow\infty}\boldsymbol{x}^{k} =\boldsymbol{x}^{0}$ 和 (4.4) 式可知

由 $\mu_{i}^{k}g_{i}(\boldsymbol{x}^{k})=2kg_{i}( \boldsymbol{x}^{k})_{+}g_{i}( \boldsymbol{x}^{k})=2kg_{i}(\boldsymbol{x}^{k})_{+}^{2}$ 和 $\lambda_{j}^{k} h_{j}(\boldsymbol{x}^{k})= 2k h_{j}( \boldsymbol{x}^{k})^{2}$ 可得

因此, 由 (4.13) 和 (4.12) 式可分别得到 (A3) 和 (A4). 证毕.

注 4.4 若区间值函数 $f$ 中的 $f^{L}=f^{U}$, 那么定理 4.1 退化为文献 [2, 定理 3.3].

如下例 4.1 说明定理 4.1, 该例子的约束函数不满足 SCQ 和 MFCQ.

例 4.1 设 $\boldsymbol{x}=(x_{1},x_{2})\in\mathbb{R}^{2}$. 考虑最优化问题

易知 $f^{L}, f^{U}$, $g_{i}$ $(i=1,2,3)$ 和 $h_{j}$ $(j=1,2)$ 是连续可微的, 其中 $f^L(x_{1},x_{2})=x_{1}+x_{2}^{2}+1$, $f^U(x_{1},x_{2})=x_{1}+x_{2}^{2}+2$. 令 $\boldsymbol{x}^{0}=(x^{0}_{1},x^{0}_{2})=(0,0)$ 可得 $f^L(\boldsymbol{x}^{0})=1$, $f^U(\boldsymbol{x}^{0})=2$. 容易验证不存在可行点 $\boldsymbol{x}=(x_{1},x_{2})$ 使得

即不存在可行点 $\boldsymbol{x}$ 使得 $f(\boldsymbol{x})\prec_{LU}f(\boldsymbol{x}^{0})$. 因此, 点 $(0,0)$ 是一个 LU-解. 由于$g_{3}(x_{1},x_{2})=-x_{1}^{2}-x_{2}$ 是一个非凸函数, 故在点 $(0,0)$ 不满足 SCQ. 显然在点 $(0,0)$ 不满足 MFCQ.

然而, 在点 $\boldsymbol{x}^{0}=(0,0)$ 上满足 W-CAKKT 条件. 事实上, 取 $\beta^{k}_{L}=\frac{1}{2}$, $\beta^{k}_{U}=\frac{1}{2}$, $\mu^k_{1}=0$, $\mu_{2}^{k}=1$, $\mu_{3}^{k}=1$, $\lambda_{1}^{k}=-1$, $\lambda_{2}^{k}=1$ 和 $\boldsymbol{x}^{k}=(\frac{1}{k},\frac{1}{k})$, 则有 $\boldsymbol{x}^{k}\rightarrow (0,0)$,

和

因此, 在点 $\boldsymbol{x}^{0}=(0,0)$ 满足 W-CAKKT 条件.

如下是定理 4.1 的等价形式.

推论 4.1 设 $f$, $g_{i}$ $(i=1,2,\cdots,m)$ 和 $h_{j}$ $(j=1,2,\cdots,p)$ 与定理 4.1 的相同. 如果在可行点 $\boldsymbol{x}^{0}$ 不满足 W-CAKKT 条件, 那么点 $\boldsymbol{x}^{0}$ 不是问题 IVOP($f,g,h$) 的局部 LU-解.

如下例 4.2 说明推论 4.1.

例 4.2 设 $\boldsymbol{x}=(x_{1},x_{2})\in\mathbb{R}^{2}$. 考虑区间值优化问题

易知 $f^L$, $f^U$ 和 $h_{j}$ $j=1,2$ 是连续可微的. 取可行点 $\boldsymbol{x}^{0}=(0,-1)$, 则有 $f^L(\boldsymbol{x}^{0})=4.5$ 和 $f^U(\boldsymbol{x}^{0})=6.5$. 经计算可得 $\nabla h_{1}(\boldsymbol{x}^{0})=(1,0)^{\top},\nabla h_{2}(\boldsymbol{x}^{0})=(-1,0){\top}$, 从而 $\nabla h_{1}(\boldsymbol{x}^{0}),\nabla h_{2}(\boldsymbol{x}^{0})$ 线性无关. 故在点 $\boldsymbol{x}^{0}$ 不满足 MFCQ.

令 $\lambda^{k}_{L}=\frac{1}{3}$, $\lambda^{k}_{U}=\frac{2}{3}$, $\lambda_{1}^{k}=3k$, $\lambda_{2}^{k}=3k$ 和 $\boldsymbol{x}^{k}=(\frac{1}{k},-1)\rightarrow (0,-1)$, 则有

因此, 在点 $\boldsymbol{x}^{0}$ 满足 Lai-Singh-Mishra^[13] 引入的 AKKT 条件.

我们声明, 在点 $\boldsymbol{x}^{0}$ 不满足 W-CAKKT 条件. 事实上, 反之假设存在序列 $\boldsymbol{x}^{k}=(x_{1}^{k},x_{2}^{k})^{\top}$, $\lambda_{1}^{k}$, $\lambda_{2}^{k}$ 和 $\lambda_{L}^{k}\geq0$, $\lambda_{U}^{k}\geq0$ 满足 $\lambda_{L}^{k}+\lambda_{U}^{k}=1$ 和

由 (A4) 可得

由 (A3) 可得

和

由 (4.16) 式可得

和

由 (4.20) 式和 $\lambda_{L}^{k}+\lambda_{U}^{k}=1$ 可得 $\lim\limits_{k\rightarrow\infty}\lambda_{2}^{k}x_{1}^{k}=3$. 再结合 $\lim\limits_{k\rightarrow\infty}x_{2}^{k}=-1$ 可知 $\lim\limits_{k\rightarrow\infty}\lambda_{2}^{k}x_{1}^{k}x_{2}^{k}=-3$. 这与 4.18 式矛盾. 因此, 在点 $\boldsymbol{x}^{0}$ 不满足 W-CAKKT 条件. 这样, 应用推论 4.1 可推知点 $\boldsymbol{x}^{0}=(0,-1)$ 不是原问题的LU-解.

接着, 我们将证明在LU-凸的情形下, W-CAKKT 条件也是可行点成为问题 IVOP($f,g,h$) 的LU-解的充分性条件.

定理 4.2 设区间值函数 $f$ 是弱连续可微且 LU-凸的, $g_i\ (i=1,\cdots,m)$ 是连续可微的凸函数, $h_{j}\ (j=1,\cdots,p)$ 是 $\mathbb{R}^{n}$ 连续可微的仿射函数. 设问题 IVOP($f,g,h$) 的可行点 $\boldsymbol{x}^0$ 满足 W-CAKKT 条件. 那么点 $\boldsymbol{x}^0$ 是问题 IVOP($f,g,h$) 的一个LU-解.

证 由于问题 IVOP($f,g,h$) 的可行点 $\boldsymbol{x}^0$ 满足 W-CAKKT 条件, 设序列 $\{\boldsymbol{x}^{k}\}\subset \mathbb{R}^{n}$ 和 $\{(\beta_L^k,\beta_U^k,\boldsymbol{\mu}^{k}, \boldsymbol{\lambda}^{k})\} \subset \mathbb{R}^{*}_{+} \times \mathbb{R}^{*}_+\times \mathbb{R}^{m}_{+}\times \mathbb{R}^{p}$ 如定义 4.1 给出.

由于区间值函数 $f$ 是弱连续可微且 LU-凸的, 由定义 2.3 的条目 (ii) 和命题 2.3, 可知 $f^L$ 和 $f^U$ 是连续可微的凸函数. 由 $f^L,f^U$ 和 $g_i\ (i=1,\cdots,m)$ 的凸性以及$h_j\ (j=1,\cdots,p)$ 的仿射性, 对任意的$\boldsymbol{x}\in\Omega$, 有

从而

其中

由 (A4) 可得

由 (A3) 可得

由 (A2) 可知 $\{(\beta_{L}^{k},\beta_{U}^{k})^{\top}\}$ 是有界的. 令 $(\beta_{L},\beta_{U})^{\top}$ 是序列 $\{(\beta_{L}^{k},\beta_{U}^{k})^{\top}\}$ 的一个据点. 对 (4.22) 式的两边取极限可得

假设点 $\boldsymbol{x}^0$ 不是问题 IVOP($f,g,h$) 的一个LU-解. 那么存在 $\overline{\boldsymbol{x}}\in\Omega(g,h)$ 使得 $f(\overline{\boldsymbol{x}})\prec_{LU} f(\boldsymbol{x}^0)$, 即

因此, 可得

这与 (4.23) 式矛盾. 因此点 $\boldsymbol{x}^{0}$ 是问题 IVOP($f,g,h$) 的一个 LU-解. 证毕.

注 4.5 如果区间值函数 $f$ 中的 $f^{L}=f^{U}$, 那么定理 4.2 退化为文献 [2, 定理 4.2].

接着, 我们探讨 W-CAKKT 条件与问题 IVOP($f,g,h$) 其它最优性条件之间的关系.

定理 4.3 如果问题 IVOP($f,g,h$) 的可行点 $\boldsymbol{x}^{0}$ 是 W-CAKKT 点, 且在点 $\boldsymbol{x}^{0}$ 满足 MFCQ, 那么点$\boldsymbol{x}^0$ 满足条件 (K1)-(K2).

证 设 $\{\boldsymbol{x}^k\}$ 和 $\{(\beta_{L}^{k}, \beta_{U}^{k}, \boldsymbol{\mu^{k}}, \boldsymbol{\lambda}^{k})\}$ 满足 (A1)-(A4) 的序列. 令

和

我们声称 $\{t_{k}\}$ 是有界的. 事实上, 如果 $\{t_{k}\}$ 无界, 不失一般性, 假设当 $k\rightarrow\infty$ 时 $t_{k}\rightarrow\infty$. 易知 $\{\frac{(\boldsymbol{\mu^{k}},\boldsymbol{\lambda}^{k})}{t^{k}}\}$ 是有界的. 不失一般性, 令

易知 $\|(\hat{\boldsymbol{\mu}}, \hat{\boldsymbol{\lambda}})\|=1$, 其中 $\hat{\boldsymbol{\mu}}=(\hat{\mu}_{1},\cdots,\hat{\mu}_{m})\in \mathbb{R}^{m}_{+}$ 和 $\hat{\boldsymbol{\lambda}}=(\hat{\lambda}_{1},\cdots,\hat{\lambda}_{p})\in \mathbb{R}^{p}$. 由 (A2) 可知 $\{\beta_{L}^{k}, \beta_{U}^{k}\}$ 是有界的, 从而

由 (A4) 和 $t_{k}\rightarrow\infty$ 可得

再结合 (4.25), (4.26) 式, (A1) 以及 $f^{L}$, $f^{U}$, $g_{i}$ 和 $h_{j}$ 的连续可微性可得

由 (A3) 和 $t_{k}\rightarrow\infty$ 可得

同时, 由 (4.25) 式, (A1)和 $g_{i}$ 的连续性可得

由极限的唯一性可得 $\hat{\mu}_{i}|g_{i}(\boldsymbol{x}^{0})|=0$. 如果 $i\notin I(\boldsymbol{x}^0)$, 那么 $g_{i}(\boldsymbol{x}^{0})<0$, 从而 $\hat{\mu}_{i}=0$. 这样, 由 (4.27) 式可得

由 $\|(\hat{\boldsymbol{\mu}},\hat{\boldsymbol{\lambda}})\|=1$ 可推知至少存在一个 $i_{0}\in I(\boldsymbol{x}^{0})$ 使得$\hat{\mu}_{i_{0}}>0$. (否则, 我们有 $\sum\limits_{j=1}^{p}\hat{\lambda}_{j}\nabla h_{j}(\boldsymbol{x}^{0})= \boldsymbol{0}$, 其中$\hat{\lambda}_{1},\cdots,\hat{\lambda}_{p}$ 不全为 0. 另一方面, 由 MFCQ 可知 $\nabla h_{1}(\boldsymbol{x}^{0}),\cdots,\nabla h_{p}(\boldsymbol{x}^{0})$ 线性无关. 矛盾.) 由于在点 $\boldsymbol{x}^{0}$ 满足 MFCQ, 故存在向量 $\boldsymbol{d}\in\mathbb{R}^{n}$ 使得对每一个 $i\in I(\boldsymbol{x}^{0})$, 有 $\langle \nabla g_{i}(\boldsymbol{x}^{0}),\boldsymbol{d}\rangle<0$ 和对每一个 $j=1,\cdots,p$, 有 $\langle \nabla h_{j}(\boldsymbol{x}^{0}), \boldsymbol{d}\rangle=0$. 再结合 $\hat{\mu}_{i_{0}}>0$ 可得

与 (4.28) 式矛盾. 这样, 可推出 $(\boldsymbol{\mu^{k}},\boldsymbol{\lambda}^{k})$ 是有界的. 结合 (A2), 可推出 $\{\boldsymbol{x}^k\}$ 和 $\{(\beta_{L}^{k}, \beta_{U}^{k}, \boldsymbol{\mu^{k}}, \boldsymbol{\lambda}^{k})\}$ 的有界性. 不失一般性, 令 $(\beta_{L}^{k}, \beta_{U}^{k}, \boldsymbol{\mu^{k}}, \boldsymbol{\lambda}^{k})\rightarrow(\beta_{L}, \beta_{U}, \boldsymbol{\mu}, \boldsymbol{\lambda})\in \mathbb{R}_{+} \times \mathbb{R}_{+}\times \mathbb{R}^{m}_{+}\times \mathbb{R}^{p}$. 再结合 (A1) 以及 $f^{L}$, $f^{U}$, $g_{i}$ 和 $h_{j}$ 的连续可微性, 可得

同时, 由 (A4) 可得

由极限的唯一性可得 (K1). 由 (A2) 可知 $\beta_{L}$ 和 $\beta_{U}$ 不全为 0. 类似地, 由 (A3) 可得 (K2).

对于等式与不等式约束的区间值优化问题, 本文引入并研究了 KKT 与 W-CAKKT 最优性条件. 证明了如果满足 MFCQ, 那么 KKT 条件是问题 IVOP($f,g,h$) 的 LU-解的必要条件; 如果不满足任何约束规范, 那么 W-CAKKT 条件是问题 IVOP($f,g,h$) 的 LU-解的必要条件. 此外, 如果问题 IVOP($f,g,h$) 的所有函数都是凸函数, 那么 W-CAKKT 条件也是问题 IVOP($f,g,h$) 的 LU-解的充分条件. 另外, 如果满足 MFCQ, 那么W-CAKKT 必要条件由于 KKT 必要条件. 本文的主要结果都通过一些例子进行了说明. 据我们所知, 作为序列最优性条件, W-CAKKT 条件是首次从实值最优化问题推广到了区间值优化问题.