半无限拟凸优化问题的最优性条件之研究

Optimality Conditions in Semi-Infinite Quasiconvex Optimization

摘要: 考虑目标函数和约束函数均是上半连续拟凸函数的半无限规划问题，通过引入弱Slater约束规范条件，刻画了该问题基于Greenberg-Pierskalla次微分及v-次微分的KKT类最优性条件。

Abstract: Considering semi-infinite programming problems where both the objective and constraint functions are upper semicontinuous quasiconvex, we characterize KKT-type optimality conditions for such problems based on the Greenberg-Pierskalla subdifferential and the v-subdifferential by introducing a weak Slater constraint qualification.

1. 引言

数学优化问题作为现代最优化理论的核心问题之一，广泛应用于国防，经济，运输等领域。许多问题在一定条件下都可以看作或者转化为如下带不等式约束优化问题

$\left(\text{P}\right)\begin{array}{ll}\text{inf}\hfill & f\left(x\right)\hfill \\ \text{s}.\text{t}.\hfill & g_i\left(x\right)\le 0,i\in I,x\in C,\hfill \end{array}$

其中$I$ 是指标集，$C$ 是n维Euclid空间${ℝ}^n$ 中的非空子集，$f$ ，$g_i$ ，$i\in I$ 是${ℝ}^n$ 上的广义实值函数。许多学者对问题(P)进行了深入研究，并得到了一系列有意义的结论(参看文[1]-[13])。例如，最优性条件，鞍点定理，对偶理论等。

在经典优化理论的框架下，针对凸优化问题的KKT最优性条件已经建立了完善的理论体系。然而，当目标函数或约束函数不具备凸性时，传统的最优性条件可能不再适用。为此，学者们提出了各种广义凸性概念(如拟凸，伪凸，均匀凸等)和相应的次微分工具，以扩展最优性条件的适用范围。近年来，关于拟凸优化问题的研究取得了重要进展。Penot在[14]中首次系统研究了拟凸函数的次微分性质及其在优化中的应用。Suzuki在[15]中基于Greenberg-Pierskalla次微分建立了拟凸规划的最优性条件。随后Suzuki在[16]中进一步研究了KKT类最优性条件在拟凸规划中的表现形式。这些工作为处理非凸优化问题提供了新的理论工具。在半无限规划方面，Jeyakumar在[5]中研究了无限维凸规划的对偶理论。Fang等人在[1] [2]中系统研究了凸无限规划的约束规范条件和Lgrange对偶理论。Kanzi等人在[17]中探讨了广义凸性下的半无限规划的最优性条件。这些研究为无限维优化问题奠定了理论基础。

受上述文献启发，本文将研究目标函数是上半连续本质拟凸函数，约束函数为上半连续拟凸函数的半无限规划问题，通过引入弱Slater约束规范条件，刻画该问题基于Greenberg-Pierskalla次微分及$\nu$ -次微分的KKT类最优性条件。

本文所研究的问题与文献[17]中考虑的广义凸半无限规划问题有一定的相似性，但在假设条件，所用工具和结论强度上存在显著差别。本文引入了弱Slater条件，放宽了可行性的要求，更适用于实际建模中的混合约束系统。此外，本文采用的Greenberg-Pierskalla次微分和$\nu$ -次微分作为分析工具，能更好地捕捉拟凸函数的非凸特性。特别是在拟凸函数非本质拟凸时，Greenberg-Pierskalla次微分仍能有效刻画最优性，这是传统次微分所不具备的优势。另一方面，本质拟凸性要求函数的任何局部极小点都是全局最小点。这一性质保证了最优性条件的有效性。

2. 符号与定义

设$\langle x^{*},x\rangle$ 表示n维Euclid空间${ℝ}^n$ 中向量$x$ 和$x^{*}$ 的内积，$A$ 是${ℝ}^n$ 的非空子集，$\overline{A}$ ，$\text{int}\left(A\right)$ ，$\text{co}\left(A\right)$ ，$\text{cone}\left(A\right)$ 分别表示$A$ 的闭包，内部，凸包，锥包。定义$A$ 的法锥，承托函数和示性函数分别为

$N_A\left(x_0\right):=\left\{x^{*}\in {ℝ}^n:\langle x^{*},y-x\rangle \le 0,\forall y\in A\right\},\forall x\in A,$

${\sigma }_A\left(x^{*}\right):=\underset{x\in A}{\text{sup}}\langle x^{*},x\rangle ,$

${\delta }_A\left(x\right):=\{\begin{array}{ll}0,\hfill & x\in A,\hfill \\ +\infty ,\hfill & x\in {ℝ}^n\backslash A.\hfill \end{array}$

设函数$f:{ℝ}^n\to \overline{ℝ}:=ℝ\cup \left\{+\infty \right\}$ 。$f$ 的有效定义域、Fenchel共轭函数和上图分别定义为

$\text{dom}f:=\left\{x\in {ℝ}^n:f\left(x\right)<+\infty \right\},$

$f^{*}\left(x^{*}\right):=\text{sup}\left\{\langle x^{*},x\rangle -f\left(x\right):x\in {ℝ}^n\right\},$

$\text{epi}f:=\left\{\left(x,r\right)\in {ℝ}^n\times ℝ:f\left(x\right)\le r\right\}.$

设$f$ 在$x_0\in {ℝ}^n$ 处有限，$f$ 在$x_0$ 处的上水平集，下水平集和严格下水平集分别定义为$L\left(f,\ge ,\alpha \right):=\left\{x\in {ℝ}^n:f\left(x\right)\ge \alpha \right\}$ ，$L\left(f,\le ,\alpha \right):=\left\{x\in {ℝ}^n:f\left(x\right)\le \alpha \right\}$ ，$L\left(f,<,\alpha \right):=\left\{x\in {ℝ}^n:f\left(x\right)<\alpha \right\}$ 。对任意的非空集合$T$ ，令${ℝ}^T$ 表示定义在$T$ 上的实值函数组成的空间并赋予乘积拓扑，即

${ℝ}^{\left(T\right)}:=\left\{\lambda ={\left({\lambda }_t\right)}_{t\in T}\in {ℝ}^{\left(T\right)}:最多只有有限�{\lambda }_t\ne 0\right\},$

记${ℝ}_{+}^{\left(T\right)}$ 为${ℝ}^{\left(T\right)}$ 的非负锥，即

${ℝ}_{+}^{\left(T\right)}:=\left\{\lambda ={\left({\lambda }_t\right)}_{t\in T}\in {ℝ}^{\left(T\right)}:{\lambda }_t\ge 0,\forall t\in T\right\}.$

设$\left\{A_t:t\in T\right\}$ 为${ℝ}^n$ 的一个子集系统，定义集合${\displaystyle \sum _{t\in T}{A}_t}$ 为

${\displaystyle \sum _{t\in T}{A}_t}:=\left\{{\displaystyle \sum _{t\in T_0}{a}_t}:a_t\in A_t,T_0\subseteq T是有限集合\right\}.$

定义 2.1 [18] [19]设$f:{ℝ}^n\to \overline{ℝ}$ 为真函数，且$f$ 在$x_0\in {ℝ}^n$ 处有限。

(i) $f$ 在$x_0$ 处的Greenberg-Pierskalla次微分定义为

${\partial }^{GP}f\left(x_0\right):=\left\{\xi \in {ℝ}^n:\langle \xi ,x-x_0\rangle <0,\forall x\in L\left(f,<,f\left(x_0\right)\right)\right\}.$

(ii) $f$ 在$x_0$ 处的$\nu$ -次微分定义为

${\partial }^{\nu }f\left(x_0\right):=\left\{\xi \in {ℝ}^n:\langle \xi ,x-x_0\rangle \le 0,\forall x\in L\left(f,\le ,f\left(x_0\right)\right)\right\},$

即，

${\partial }^{\nu }f\left(x_0\right):=N_A\left(x_0\right),x\in A=L\left(f,\le ,f\left(x_0\right)\right).$

定义 2.2 [16]设$f:{ℝ}^n\to \overline{ℝ}$ 为真函数。

(i) 若对任意的$x,y\in {ℝ}^n$ 和$\lambda \in \left[0,1\right]$ 都有

$f\left(\lambda x+\left(1-\lambda \right)y\right)\le \text{max}\left\{f\left(x\right),f\left(y\right)\right\},$

则称函数$f$ 是拟凸函数；

(ii) 若$f$ 是拟凸函数，且$f$ 在${ℝ}^n$ 上的任意局部最小点均是$f$ 在${ℝ}^n$ 上的全局最小点，则称函数$f$ 是本质拟凸函数。

3. 最优性条件

考虑以下半无限规划问题

$\left(\text{SIP}\right)\begin{array}{ll}\text{inf}\hfill & f\left(x\right)\hfill \\ \text{s}.\text{t}.\hfill & g_i\left(x\right)\le 0,\forall i\in I,\hfill \end{array}$

其中$I$ 是任意非空(可能无限)指标集，$f,g_i,i\in I$ 是定义在${ℝ}^n$ 上的广义实值拟凸函数。记(SIP)的可行解集$C$ 为

$C:=\left\{x\in {ℝ}^n:g_i\left(x\right)\le 0,\forall i\in I\right\}={\displaystyle \underset{i\in I}{\cap }{C}_i},$

其中$C_i:=\left\{x\in {ℝ}^n:g_i\left(x\right)\le 0\right\}$ ，对任意的$x_0\in C$ ，记

$I\left(x_0\right):=\left\{i\in I:g_i\left(x_0\right)=0\right\}.$

为方便起见，本文均假设$C\ne \varnothing$ 。

定义 3.1 [20]若存在点$x_0\in {ℝ}^n$ ，使得对任意的$i\in I$ 都有$g_i\left(x_0\right)<0$ ，则称系统$\left\{g_i,i\in I\right\}$ 满足Slater条件。

定义 3.2 [20]若存在点$x_0\in {ℝ}^n$ ，使得对任意的$i\in I$ 都有$g_i$ 是仿射函数或$g_i\left(x_0\right)<0$ ，则称系统$\left\{g_i,i\in I\right\}$ 满足弱Slater条件。

引理 3.1 [19]设任意函数族${\left(f_i\right)}_{i\in I}$ 在$x_0$ 处是有限的，$f:={\sup }_{i\in I}{f}_i$ 。假设$I\left(x\right):=\left\{i\in I:f_i\left(x\right)=f\left(x\right)\right\}$ 非空。则对于$\nu$ -次微分${\partial }^{\nu }f\left(x\right)$ ，有以下包含关系成立

$\text{conv}\left({\displaystyle \underset{i\in I\left(x\right)}{\cup }{\partial }^{\nu }{f}_i\left(x\right)}\right)\subseteq {\partial }^{\nu }f\left(x\right).$

引理 3.2 [15]设$x_0\in C$ 。若$f$ 是上半连续本质拟凸函数，则$x_0$ 是$f$ 在$C$ 上的全局最小点当且仅当

$0\in {\partial }^{GP}f\left(x_0\right)+N_A\left(x_0\right).$

引理 3.3 [21]设$x\in C$ 。对任意的$i\in I$ ，$g_i$ 是上半连续本质拟凸函数且系统$\left\{g_i,i\in I\right\}$ 满足Slater条件，则

$N_{{\displaystyle {\cap }_{i\in I}{C}_i}}\left(x\right)={\displaystyle \sum }_{i\in I}{N}_{C_i}\left(x\right).$

引理 3.4 [21]设$x_0\in C$ 。对任意的$i\in I$ ，$g_i$ 是实值凸函数且系统$\left\{g_i,i\in I\right\}$ 满足弱Slater条件，则

$N_C\left(x_0\right)=\text{co}\text{cone}{\displaystyle \underset{i\in I\left(x_0\right)}{\cup }\partial g_i}\left(x_0\right).$

定理 3.1设$x\in {ℝ}^n$ ，$g:{ℝ}^n\to \overline{ℝ}$ ，则${\partial }^{\nu }g\left(x\right)$ 是个闭凸锥。

证明 设$v\in {\partial }^{\nu }g\left(x\right),\lambda >0$ ，由定义2.1得对任意的$y\in L\left(g,\le ,g\left(x\right)\right)$ ，有$\langle v,y-x\rangle \le 0$ 。两边同乘$\lambda$ ，得

$\lambda \langle v,y-x\rangle =\langle \lambda v,y-x\rangle \le 0,\forall y\in L\left(g,\le ,g\left(x\right)\right).$

因此，$\lambda v\in {\partial }^{\nu }g\left(x\right)$ 。故由$v$ 和$\lambda$ 的任意性可知${\partial }^{\nu }g\left(x\right)$ 是个锥。接下来证明${\partial }^{\nu }g\left(x\right)$ 的凸性。取${\xi }_1,{\xi }_2\in {\partial }^{\nu }g\left(x\right)$ 和$\theta \in \left[0,1\right]$ ，令$\xi =\theta {\xi }_1+\left(1-\theta \right){\xi }_2$ 。由定义2.1得对任意的$y\in L\left(g,\le ,g\left(x\right)\right)$ ，有$\langle {\xi }_1,y-x\rangle \le 0$ 和$\langle {\xi }_2,y-x\rangle \le 0$ 。则

$\langle \xi ,y-x\rangle =\theta \langle {\xi }_1,y-x\rangle +\left(1-\theta \right)\langle {\xi }_2,y-x\rangle \le 0,\forall y\in L\left(g,\le ,g\left(x\right)\right).$

因此，$\xi \in {\partial }^{\nu }g\left(x\right)$ ，故${\partial }^{\nu }g\left(x\right)$ 是凸的。设序列$\left\{v_k\right\}\subset {\partial }^{\nu }g\left(x\right)$ 收敛于$v_0\in {ℝ}^n$ 。要证$v_0\in {\partial }^{\nu }g\left(x\right)$ ，即需证：

$\langle v_0,y-x\rangle \le 0,\forall y\in L\left(g,\le ,g\left(x\right)\right).$

假设结论不成立，则存在$\overline{y}\in L\left(g,\le ,g\left(x\right)\right)$ 使得$\langle v_0,\overline{y}-x\rangle >0$ 。由于$v_k\to v_0$ ，存在$K>0$ 使得当$k>K$ 时

$\langle v_k,\overline{y}-x\rangle >0.$ (3.1)

但$\overline{y}\in L\left(g,\le ,g\left(x\right)\right)$ 且$v_k\in {\partial }^{\nu }g\left(x\right)$ ，由定义2.1得$\langle v_k,\overline{y}-x\rangle \le 0$ 。这与(3.1)式矛盾，则有$v_0\in {\partial }^{\nu }g\left(x\right)$ ，即${\partial }^{\nu }g\left(x\right)$ 是闭集，故定理得证。

设$x\in C$ ，定义$\psi \left(x\right):=\underset{i\in I}{\text{sup}}{g}_i\left(x\right)$ ，则下面的定理成立。

定理 3.2 设$x_0\in C$ 。对任意的$i\in I$ ，$g_i$ 是上半连续拟凸函数，且在$x_0$ 处有限，$I\left(x_0\right)\ne \varnothing$ 。若系统$\left\{g_i,i\in I\right\}$ 满足弱Slater条件，则

${\partial }^{\nu }\psi \left(x_0\right)\subseteq \text{cone}\left({\displaystyle \underset{i\in I\left(x_0\right)}{\cup }{\partial }^{\nu }{g}_i\left(x_0\right)}\right).$ (3.2)

证明 由上述条件可知，$\psi \left(x_0\right)=0$ ，并且由假设$I\left(x_0\right)\ne \varnothing$ 可知，$C=\left[\psi \le \psi \left(x_0\right)\right]$ 。设$p\in {\partial }^{\nu }\psi \left(x_0\right)$ 。则

$\langle p,x-x_0\rangle \le 0,\forall x\in L\left(\psi ,\le ,\psi \left(x_0\right)\right),$

因此，$p\in N_C\left(x_0\right)$ ，故有

${\partial }^{\nu }\psi \left(x_0\right)\subseteq N_C\left(x_0\right).$ (3.3)

由于$g_i$ 是拟凸函数，故$C_i$ 为凸集。定义集合

$I_0:=\left\{i\in I:g_i是仿射函�\right\},I_0\left(x_0\right):=\left\{i\in I_0:g_i\left(x_0\right)=0\right\},$

$H_0:=\left\{x\in {ℝ}^n:g_i\left(x\right)\le 0,\forall i\in I_0\right\},H:=\left\{x\in {ℝ}^n:g_i\left(x\right)\le 0,\forall i\in I\backslash I_0\right\},$

则有

$H_0={\displaystyle \underset{i\in I_0}{\cap }{C}_i},H={\displaystyle \underset{i\in I\backslash I_0}{\cap }{C}_i},H={\displaystyle \underset{i\in I\backslash I_0}{\cap }{C}_i},C=H_0\cap H.$

对任意的$i\in I\backslash I_0$ ，由$g_i$ 的上半连续性可知$\left[g_i\left(x\right)\ge 0\right]$ 是闭集，故$\left[g_i\left(x\right)\ge 0\right]$ 的补集$\left[g_i\left(x\right)<0\right]$ 是开集。由于$\left\{g_i,i\in I\right\}$ 满足弱Slater条件，因此存在点$\overline{x}\in {ℝ}^n$ ，使得对任意的$i\in I\backslash I_0$ 都有$g_i\left(\overline{x}\right)<0$ ，即$\overline{x}\in L\left(g_i,<,0\right)$ 。显然，对任意的$i\in I\backslash I_0$ ，

$L\left(g_i,<,0\right)=\mathrm{int}L\left(g_i,<,0\right)\subset \mathrm{int}L\left(g_i,\le ,0\right)=\mathrm{int}{C}_i.$

因此

$\overline{x}\in {\displaystyle \underset{i\in I\backslash I_0}{\cap }\mathrm{int}{C}_i}=\mathrm{int}{\displaystyle \underset{i\in I\backslash I_0}{\cap }{C}_i}=\mathrm{int}H,$

即$\mathrm{int}H\ne \varnothing$ 。注意到$H_0$ 是多面体，故由文献[22]，命题2.3可知，对任意的$x_0\in C$ 有

$N_C\left(x_0\right)=N_{H_0}\left(x_0\right)+N_H\left(x_0\right).$ (3.4)

由引理3.3得

$N_H\left(x_0\right)={\displaystyle \underset{i\in I\left(x_0\right)\backslash I_0\left(x_0\right)}{\cup }{\partial }^{\nu }{g}_i}\left(x_0\right).$ (3.5)

同时，由于对任意的$i\in I_0$ ，$g_i$ 是仿射函数，不妨设$g_i\left(x\right)=\langle a_i,x\rangle -b_i$ ，其中$a_i\in {ℝ}^n,b_i\in ℝ$ ，故有

$\partial g_i\left(x_0\right)=\left\{a_i\right\},{\partial }^{\nu }{g}_i\left(x_0\right)=\left\{\lambda a_i:\lambda \ge 0\right\},\forall i\in I_0.$

进一步，由引理3.4可知，

$N_{H_0}\left(x_0\right)=\text{co}\text{cone}{\displaystyle \underset{i\in I_0\left(x_0\right)}{\cup }\partial g_i}\left(x_0\right).$

结合定理3.1可知，

$N_{H_0}\left(x_0\right)={\displaystyle \underset{i\in I_0\left(x_0\right)}{\cup }{\partial }^{\nu }{g}_i}\left(x_0\right).$ (3.6)

注意到，对任意的$i\in I\left(x_0\right)$ ，由定理3.1可得${\partial }^{\nu }{g}_i\left(x_0\right)$ 是闭凸锥。故由(3.4)~(3.6)式得

$N_C\left(x_0\right)={\displaystyle \underset{i\in I\left(x_0\right)}{\cup }{\partial }^{\nu }{g}_i\left(x_0\right)}=\text{cone}\left({\displaystyle \underset{i\in I\left(x_0\right)}{\cup }{\partial }^{\nu }{g}_i\left(x_0\right)}\right).$ (3.7)

结合(3.3)和(3.7)式可知(3.2)式成立，定理得证。

定理 3.3 设$x_0\in C$ 。在定理3.2的条件下，有以下等式

${ℝ}_{+}{\partial }^{\nu }\psi \left(x_0\right)=N_C\left(x_0\right)$ (3.8)

成立，其中${ℝ}_{+}:=\left\{\lambda \in ℝ:\lambda \ge 0\right\}$ 。

证明 由定理3.2的证明可以得到，${\partial }^{\nu }\psi \left(x_0\right)\subseteq N\left(C,x_0\right)$ ，则${ℝ}_{+}{\partial }^{\nu }\psi \left(x_0\right)\subseteq N\left(C,x_0\right)$ ，下面证明反包含。结合引理3.1可以推出

$\text{conv}\left({\displaystyle \underset{i\in I\left(x_0\right)}{\cup }{\partial }^{\nu }{g}_i\left(x_0\right)}\right)\subseteq {\partial }^{\nu }\psi \left(x_0\right).$

由(3.7)式可得

$\begin{array}{c}{N}_C\left(x_0\right)=\text{cone}\left({\displaystyle \underset{i\in I\left(x_0\right)}{\cup }{\partial }^{\nu }{g}_i\left(x_0\right)}\right)\\ ={ℝ}_{+}\text{conv}\left({\displaystyle \underset{i\in I\left(x_0\right)}{\cup }{\partial }^{\nu }{g}_i\left(x_0\right)}\right)\subseteq {ℝ}_{+}{\partial }^{\nu }\psi \left(x_0\right).\end{array}$

即(3.8)式成立。

定理 3.4 设$x_0$ 是问题(SIP)的最优解，$f$ 为上半连续函数本质拟凸函数，$g_i,i\in I$ 是上半连续拟凸函数，$I\left(x_0\right)\ne \varnothing$ 。设问题(SIP)在$x_0$ 处满足弱Slater条件，则存在有限指标集$\left\{i_1,i_2,\cdots ,i_p\right\}\subseteq I\left(x_0\right)$ 和正标量${\lambda }_{i_1},{\lambda }_{i_2},\cdots ,{\lambda }_{i_p}$ 使得

$0\in {\partial }^{GP}f\left(x_0\right)+{\displaystyle \sum }_{k=1}^p{\lambda }_{i_k}{\partial }^{\nu }{g}_{i_k}\left(x_0\right).$ (3.9)

证明 由引理3.2，定理3.2，定理3.3可以推出

$\begin{array}{c}0\in {\partial }^{GP}f\left(x_0\right)+N\left(C,x_0\right)\\ ={\partial }^{GP}f\left(x_0\right)+{ℝ}_{+}{\partial }^{\nu }\psi \left(x_0\right)\\ \subseteq {\partial }^{GP}f\left(x_0\right)+{ℝ}_{+}\text{cone}\left({\displaystyle \underset{i\in I\left(x_0\right)}{\cup }{\partial }^{\nu }{g}_i\left(x\right)}\right)\\ \subseteq {\partial }^{GP}f\left(x_0\right)+{\displaystyle \sum _{k=1}^p{\lambda }_{i_k}{\partial }^{\nu }{g}_{i_k}\left(x_0\right)}\end{array}$

因此，(3.9)式成立。

定理 3.5 假设$x_0\in C$ ，如果$f$ 在$x_0$ 处是有限的，并且存在有限指标集$\left\{i_1,i_2,\cdots ,i_p\right\}\subseteq I\left(x_0\right)$ 和正标量${\lambda }_{i_1},{\lambda }_{i_2},\cdots ,{\lambda }_{i_p}$ 使得

$0\in {\partial }^{GP}f\left(x_0\right)+{\displaystyle \sum }_{k=1}^p{\lambda }_{i_k}{\partial }^{\nu }{g}_{i_k}\left(x_0\right),$ (3.10)

那么$x_0$ 是问题(SIP)的最优解。

证明 假设存在$x^{*}\in C$ 使得

$f\left(x^{*}\right)<f\left(x_0\right).$ (3.11)

由(3.10)式，存在$\xi \in {\partial }^{GP}f\left(x_0\right),{\xi }_{i_k}\in {\partial }^{\nu }{g}_{i_k}\left(x_0\right),k=1,2,\cdots ,p$ 使得下列等式成立

$\xi +{\lambda }_{i_1}{\xi }_{i_1}+\cdots +{\lambda }_{i_p}{\xi }_{i_p}=0.$ (3.12)

因为$g_{i_k}\left(x^{*}\right)\le 0=g_{i_k}\left(x_0\right)$ ，故$x^{*}\in \left[g_{i_k}\le g_{i_k}\left(x_0\right)\right]$ ，所以由定义2.1 (ii)得

$\langle {\lambda }_{i_k}{\xi }_{i_k},x^{*}-x_0\rangle \le 0,\forall k=1,2,\cdots ,p.$ (3.13)

另一方面，由定义2.1 (i)得

$\langle \xi ,x^{*}-x_0\rangle <0.$ (3.14)

将(3.13)式和(3.14)式相加，可得

$\langle \xi +{\lambda }_{i_1}{\xi }_{i_1}+\cdots +{\lambda }_{i_p}{\xi }_{i_p},x^{*}-x_0\rangle <0.$

根据(3.12)式得$\langle \xi +{\lambda }_{i_1}{\xi }_{i_1}+\cdots +{\lambda }_{i_p}{\xi }_{i_p},x^{*}-x_0\rangle =0$ ，故假设不成立，那么$x_0$ 是问题(SIP)的最优解。