一类可变盒子上投影算子的几何性质研究

Study on the Geometric Properties of Projection Operators on a Class of Variable Boxes

摘要: 闭凸锥投影算子几何性质对增广拉格朗日方法，投影算子几何性质的研究以及优化问题的灵敏性分析有着至关重要的作用。本文研究一类可变盒子的对偶锥、切锥、极锥与临界锥为进一步研究这一类可变盒子上投影算子的几何性质以及相关优化问题的灵敏度分析奠定了基础。

Abstract: The geometric properties of closed convex cone projection operators are very important for the study of Lagrangian, the geometric properties of projection operators and the sensitivity analysis of optimization problems. In this paper, we study the dual cone, tangent cone, polar cone and critical cone of a class of variable box, which lays a foundation for the further study of the geometric properties of projection operators on this class of variable box and the sensitivity analysis of related optimization problems.

1. 引言

闭凸锥的投影几何性质以及投影的几何性质在优化问题理论分析与算法设计中有非常重要的作用。凸集上的投影算子的插入 [1] [2] 在算法设计和理论研究中也有着非常关键的作用，例如最优化问题、增广拉格朗日方法的应用与收敛性分析、最优化问题的灵敏性分析均涉及到投影算子的性质 [3]。我们研究其中一类可变盒子 $\left\{\left(y,\tau \right)\in R^n\times R:0\le y\le \tau e\right\}$ 的几何性质，它是欧式空间 $R^n\times R$ 的非空闭凸锥。文献 [4] [5] [6] 研究了由投影算子对应的凸二次优化的条件，给出的可变盒子集合投影算子显示解的计算方法，Han等 [7] 研究了凸优化问题的求解，提出并详细阐述了某类凸锥投影算子显示表达式的计算方法。而对这些集合的刻画，离不开集合的几何性质。在这里我们对此研究的应用问题将在以后的研究中进行进一步的阐述。

2. 预备知识

由Liu等 [4] 研究的二阶锥上投影算子的Clarke广义Jacobian的具体表达式如下：

令K为 $n+1$ 维欧式空间 $R^n\times R$ 的闭凸锥。对 $\forall \left(x,t\right)\in R^n\times R$，我们用 $x^{\downarrow }$ 以表示一类向量组，x按降序排列 $x^{\downarrow }:x_1^{\downarrow }\ge x_2^{\downarrow }\ge \cdots \ge x_n^{\downarrow }$，

规定 $\left[x_0^{\downarrow }\right]=+\infty$， $s_0=0$， $m=\left|\left\{x_i|x_i\ge 0\right\}\right|$， $s_k={\displaystyle \underset{i=1}{\overset{k}{\sum }}{x}_k^{\downarrow }},k=1,\cdots ,n$，

使 $\left[x_{k+1}^{\downarrow }\right]<\frac{s_k+t}{k+1}\le \left[x_k^{\downarrow }\right]$ 的最小整数k为 $\lambda$，

否则 $\lambda =m$。

令 $\theta =\frac{s_{\lambda }+t}{\lambda +1}$，则 $\{\begin{array}{l}\theta \ge 0,\lambda <m\\ \theta 不变,\lambda =m\end{array}$。

则 $\left(x,t\right)$ 在K上的投影 ${\displaystyle {\prod }_K\left(x,t\right)}$ 可以计算为

${\displaystyle {\prod }_K\left(x,t\right)}=\left(\bar{x},\bar{t}\right)$ (1.1)

其中 $\overline{x_i}=\{\begin{array}{ll}\bar{t},\hfill & x_i\ge \bar{t}\hfill \\ x_i,\hfill & 0<x_i<\bar{t}\hfill \\ 0,\hfill & x_i\le 0\hfill \end{array}$， $i=1,\cdots ,n$， $\bar{t}\in R_{+}$， $\bar{x}\in R^n$。

令 $\alpha =\left\{i|x_i\le 0\right\}$，

则 $\theta =\frac{{\displaystyle \underset{i\in r}{\sum }{x}_i}+t}{\left|r\right|+1}$。

我们用 $\text{int}\left(K\right)$ 表示K的内部。K的对偶锥和极锥的定义分别为

$K^{\text{*}}=\left\{\left(y,\tau \right)\in R^n\times R:\langle \left(x,t\right),\left(y,\tau \right)\rangle \ge 0,\forall \left(x,t\right)\in E\right\}$ (1.2)

和

$K^o=\left\{\left(y,\tau \right)\in R^n\times R:\langle \left(x,t\right),\left(y,\tau \right)\rangle \le 0,\forall \left(x,t\right)\in E\right\}$ (1.3)

当 $K=\left\{\left(y,\tau \right)\in R^n\times R:f\left(y,\tau \right)\le 0\right\}$ 时，K的切锥为

$T_K=\left(\bar{x},\bar{t}\right)=\left\{\left(d,\eta \right):f^{\prime }\left(\left(\bar{x},\bar{t}\right);\left(d,\eta \right)\right)\le 0\right\}$ (1.4)

K的临界锥的定义为

$\bar{K}\left(x,t\right)=T_K\left(\bar{x},\bar{t}\right)\cap {\left(\left(x,t\right)-\left(\bar{x},\bar{t}\right)\right)}^{\perp }$ (1.5)

3. 集合K的几何性质

对偶锥、切锥、极锥与临界锥在研究投影算子的方向导数以及在求最优化问题的临界锥时应用十分广泛。下面，主要从集合K的表达式以及对偶锥、切锥、极锥与临界锥定义出发，分别推导K的对偶锥、切锥、极锥与临界锥。

3.1. 集合K的对偶锥

取 $\left(x,t\right)\in K^{*}$，对 $\forall \left(y,\tau \right)\in K$，有

$\langle x,y\rangle +t\tau \ge 0$ (2.1)

则 $t\ge 0$。

由(2.1)可知， $x^{\text{T}}y+t\tau \ge 0$，进而可得 $-t\le x^{\text{T}}\left(\frac{y}{\tau }\right)$。

令 $z=\frac{y}{\tau }$，则 $z\in \Omega$， $\Omega =\left\{z\in R^n,0\le z\le e\right\}$，则 $-t\le x^{\text{T}}z$，对 $\forall z\in \Omega$，则只需 $-t\le \underset{z\in \Omega }{\min }{x}^{\text{T}}z$ 即可。

引理1：对 $\forall x\in R^n$， $\forall z\in \Omega$， $z^{\ast }$ 为 $\underset{z\in \Omega }{\min }{x}^{\text{T}}z$ 的最优解。则

$\{\begin{array}{l}{z}_i^{*}=0,x_i>0\\ z_i^{*}=1,x_i<0\\ 0\le z_i^{*}\le 1,x_i=0\end{array}$

记当 $I_{<}=\{i:x_i<0\}$， $I_{>}=\{i:x_i>0\}$， $I_{=}=\{i:x_i=0\}$ 时，

$\begin{array}{c}-t\le x^{\text{T}}{z}^{*}\\ ={\displaystyle \underset{i\in I_{>}}{\sum }{x}_i}{z}_i^{*}+{\displaystyle \underset{i\in I_{=}}{\sum }{x}_i}{z}_i^{*}+{\displaystyle \underset{i\in I_{<}}{\sum }{x}_i}{z}_i^{*}\\ =0+0+{\displaystyle \underset{i\in I_{<}}{\sum }{x}_i},\end{array}$

即 ${\displaystyle \underset{i\in I_{<}}{\sum }{x}_i}+t\ge 0$， $t\ge 0$。

引理2：对 $\forall x\in R^n$， $\forall z\in \Omega$， $z^{*}$ 为 $\underset{z\in \Omega }{\max }{x}^{\text{T}}z$ 的最优解。则

$\{\begin{array}{l}{z}_i^{*}=0,x_i>0\\ z_i^{*}=1,x_i<0\\ 0\le z_i^{*}\le 1,x_i=0\end{array}$

记 $I_{<}=\{i:x_i>0\}$， $I_{>}=\{i:x_i<0\}$， $I_{=}=\{i:x_i=0\}$。

我们有如下定理。

定理1：集合K的对偶锥为 $K^{*}=\left\{\left(x,t\right)\in R^n\times R:t+{\displaystyle \underset{i\in I_{<}}{\sum }{x}_i\ge 0}\right\}$

证明：令 $B=\left\{\left(x,t\right)\in R^n\times R:t\ge -{\displaystyle \underset{i\in I_{<}}{\sum }{x}_i},t\ge 0\right\}$，要证 $B=K^{*}$ ；首先要证 $\left(x,t\right)\in K^{*}$ 对任意的 $\left(x,t\right)\in B$，由对偶锥的定义，对任意的 $\left(y,\tau \right)\in K$，都有下式成立

$\langle x,y\rangle +t\tau =x^{\text{T}}y+t\tau$ (2.2)

若 $\tau >0$，则(2.2)变为

$\langle x,y\rangle +t\tau =x^{\text{T}}y+t\tau =\tau \left(x^{\text{T}}\frac{y}{\tau }+t\right)=\tau \left(x^{\text{T}}z+t\right)\ge \tau \left(\underset{z\in \Omega }{\min }\left(x^{\text{T}}z\right)+t\right)=\tau \left(x^{\text{T}}{z}^{*}+t\right)=\tau \left(\underset{i\in I_{<}}{\min }{x}_i+t\right)\ge 0$ (2.3)

若 $\tau =0$，则 $y=0$，则 $\langle x,y\rangle +t\tau \ge 0$ 显然成立。

因此 $B\subset K^{*}$。

反过来，对 $\forall \left(x,t\right)\in K^{*}$，则对 $\forall \left(y,\tau \right)$ 有 $x^{\text{T}}y+t\tau \ge 0$，若 $\tau >0$，则

$\tau \left(t+x^{\text{T}}z\right)\ge \tau \left(t+\underset{z\in \Omega }{\min }{x}^{\text{T}}z\right)=\tau \left(t+{\displaystyle \underset{i\in I_{<}}{\sum }{x}_i}\right)\ge 0，$

由于 $\tau \left(t+{\displaystyle \underset{i\in I_{<}}{\sum }{x}_i}\right)\ge 0$ 且 $t\ge 0$ 则 $\left(x,t\right)\in B$，即 $K^{*}\subset B$。

由于对任意的 $\left(x,t\right)\in K^{*}$， $K^0\subseteq K^{*}$，反过来对任意的 $\left(x,t\right)\in K^{*}$，要证 $\left(x,t\right)\in K^0$。

3.2. 集合K的切锥

定理2：集合K的切锥为 $K^0=\left\{\left(x,t\right)\in R^n\times R:t+{\displaystyle \underset{i\in I_{<}}{\sum }{x}_i}\le 0\right\}$

证明：由于 $K^0=-K^{*}$，则该结论显然。

3.3. 集合K的极锥

定理3：集合K的极锥为 $T_K\left(\bar{x},\bar{t}\right)=\{\begin{array}{l}{R}^n\times R;\left(x,t\right)\in \mathrm{int}K\hfill \\ K;\left(x,t\right)\in K^0\hfill \\ \left\{\left(d,\eta \right):f^{\prime }\left(\left(\bar{x},\bar{t}\right),\left(d,\eta \right)\right)\le 0\right\};其他\hfill \end{array}$。

$f^{\prime }\left(\left(\bar{x},\bar{t}\right),\left(d,\eta \right)\right)\le 0$，则

$f^{\prime }\left(\left(\bar{x},\bar{t}\right),\left(d,\eta \right)\right)=\underset{l\downarrow 0}{\lim }\frac{f\left(\bar{x}+ld,\bar{t}+l\eta \right)-f\left(\bar{x},\bar{t}\right)}{l}$，此时 $f\left(\bar{x},\bar{t}\right)=0$

则

$\begin{array}{c}{f}^{\prime }\left(\left(\bar{x},\bar{t}\right),\left(d,\eta \right)\right)=\underset{l\downarrow 0}{\lim }\frac{f\left(\bar{x}+ld,\bar{t}+l\eta \right)}{l}\\ =\underset{l\downarrow 0}{\lim }\frac{\max \left\{-\bar{x}+ld,\bar{x}+ld-\bar{t}e+l\eta e\right\}}{l}\\ =\underset{l\downarrow 0}{\lim }\frac{\max \left\{-l{d}_{\alpha },l{d}_{\gamma }-l\eta e\right\}}{l}=\max \left\{-d_{\alpha },d_{\gamma }-\eta e\right\}\end{array}$

即 $T_K\left(\bar{x},\bar{t}\right)=\{\begin{array}{l}{R}^n\times R;\left(x,t\right)\in \mathrm{int}K\hfill \\ 0;\left(x,t\right)\in K^0\hfill \\ \left\{\left(d,\eta \right):-d_{\alpha }\le 0,d_{\gamma }\le \eta e\right\};其他\hfill \end{array}$。

3.4. 集合K的临界锥

定理4：满足 $\min \frac{1}{2}{\Vert y-x\Vert }^2+\frac{1}{2}{\left(\tau -t\right)}^2$，使得 $0\le y\le \tau e$ 的临界锥为 $\bar{K}\left(x,t\right)=T_K\left(\bar{x},\bar{t}\right)\cap {\left(\left(x,t\right)-\left(\bar{x},\bar{t}\right)\right)}^{\perp }$。

证明：i) 当 $\left(x,t\right)\in K$ 时， $\left(\bar{x},\bar{t}\right)=\left(x,t\right)$，则 $\bar{K}=T_K$ 即 $\{\begin{array}{l}{R}^n\times R;\left(x,t\right)\in \mathrm{int}K\hfill \\ K;\left(x,t\right)=\left(0,0\right)\hfill \\ \left\{\left(d,\eta \right):d_{\alpha }\ge 0,d_{\gamma }\le \eta e\right\};\left(x,t\right)\in bd\left(K\right)\hfill \end{array}$ ；

ii) 当 $\left(x,t\right)\in \mathrm{int}{K}^0$ 时， $\left(\bar{x},\bar{t}\right)=\left(0,0\right)$，则 $T_K=K$，则 $\bar{K}=K\cap {\left(x,t\right)}^{\perp }$，而 ${\displaystyle \underset{i\in I_{>}}{\sum }{x}_i}+t<0$ 且 $\forall \left(d,\eta \right)\in K\cap {\left(x,t\right)}^{\perp }$，则 $0\le d\le \eta e$， $x^{\text{T}}d+t\eta =0$，而

$\begin{array}{c}{x}^{\text{T}}d+t\eta =\eta \left(t+{\left(\frac{d}{\eta }\right)}^{\text{T}}x\right)\le \eta \left(t+\underset{z\in \Omega }{\max }{z}^{\text{T}}x\right)\\ =\eta \left(t+z_{*}^{\text{T}}x\right)\\ =\eta \left(t+{\displaystyle \underset{i\in I_{>}}{\sum }{x}_i}\right)\\ \le 0\end{array}$

则 $\eta =0$，即 $\bar{K}=\left\{\left(0,0\right)\right\}$ ；

iii) 当 $\left(x,t\right)\in bd\left(K^0\right)\backslash \left\{\left(0,0\right)\right\}$， $\left(\bar{x},\bar{t}\right)=\left(0,0\right)$ 时， $\bar{K}=K\cap {\left(x,t\right)}^{\perp }$，当 ${\displaystyle \underset{i\in I_{>}}{\sum }{x}_i}+t=0$ 时，对 $\forall \left(d,\eta \right)\in K\cap {\left(x,t\right)}^{\perp }$，有 $0\le d\le \eta e$， $0=x^{\text{T}}d+t\eta =\eta \left(x^{\text{T}}\left(\frac{d}{\eta }\right)+t\right)\le \eta \left(\underset{z\in \Omega }{\max }{x}^{\text{T}}z+t\right)=0$，这说明 $\frac{d}{\eta }=\arg \underset{z\in \Omega }{\max }{x}^{\text{T}}z$，即

${\left(\frac{d}{\eta }\right)}_i=\{\begin{array}{l}1,x_i>0\\ 0,x_i<0\\ \left[0,1\right],x_i=0\end{array}$,

$\bar{K}=\left\{\left(d,\eta \right):\eta \ge 0,{\left(\frac{d}{\eta }\right)}_{T_{>}}=e,{\left(\frac{d}{\eta }\right)}_{T_{<}}=0,0\le {\left(\frac{d}{\eta }\right)}_{T_{=}}\le e\right\}$,

其中 $I_{>}={\gamma }^{\ne }$， $I_{<}={\alpha }^{\ne }$， $I_{=}={\gamma }_{=}={\alpha }_{=}$ ；

iv) 其他情况， $T_K\left(\bar{x},\bar{t}\right)=\left\{\left(d,\eta \right):-d_{\alpha }\le 0,d_{\gamma }\le \eta e\right\}$

下面求 $\left(x,t\right)-\left(\bar{x},\bar{t}\right)$， $\bar{t}>0$， $L\left(y,\tau ,\upsilon ,\lambda \right)=\frac{1}{2}{\Vert y-x\Vert }^2+\frac{1}{2}{\left(\tau -t\right)}^2-\mp \langle y,\lambda \rangle -\langle \tau e-y,\upsilon \rangle$

$\{\begin{array}{l}y-x-\lambda +\upsilon =0(1)\\ \tau -t-e^{\text{T}}\upsilon =0(2)\\ 0\le y\perp \lambda \ge 0(3)\\ 0\le \left(\tau e-y\right)\perp \upsilon \ge 0(4)\end{array}$

令 $\left(y,\tau \right)=\left(\bar{x},\bar{t}\right)$ 代入，由于 ${\bar{x}}_{\alpha }=0$， ${\bar{x}}_{\beta }=x_{\beta }$， ${\bar{x}}_{\gamma }=\bar{t}e$，则由(3)(4)得 ${\lambda }_{\beta }={\lambda }_{\gamma }={\upsilon }_{\alpha }={\upsilon }_{\beta }=0$， ${\lambda }_{\alpha }\ge 0$， ${\upsilon }_{\gamma }\ge 0$ ；

由(1)得 $\{\begin{array}{l}{\bar{x}}_{\alpha }-x_{\alpha }-{\lambda }_{\alpha }+{\upsilon }_{\alpha }=0\Rightarrow {\lambda }_{\alpha }=-x_{\alpha }(5)\\ {\bar{x}}_{\gamma }-x_{\gamma }-{\lambda }_{\gamma }+{\upsilon }_{\gamma }=0\Rightarrow {\upsilon }_{\gamma }=x_{\gamma }-\bar{t}e(6)\end{array}$ ；

由(2)得 $t-\bar{t}=-e^{\text{T}}\upsilon =-e^{\text{T}}{\upsilon }_{\gamma }$。

下面求 $\bar{K}$，对 $\forall \left(d,\eta \right)\in T_K\left(\bar{x},\bar{t}\right)\cap \left(x-\bar{x},t-\bar{t}\right)$，有

$\begin{array}{c}0=\langle d,x-\bar{x}\rangle +\eta \left(t-\bar{t}\right)\\ =\langle d_{\alpha },x_{\alpha }-{\bar{x}}_{\alpha }\rangle +\langle d_{\beta },x_{\beta }-{\bar{x}}_{\beta }\rangle +\langle d_{\gamma },x_{\gamma }-{\bar{x}}_{\gamma }\rangle +\eta \left(t-\bar{t}\right)\\ =\langle d_{\alpha },-{\lambda }_{\alpha }\rangle +\langle d_{\gamma },{\upsilon }_{\gamma }\rangle -\pm \langle \eta e,{\upsilon }_{\gamma }\rangle \\ =-\langle d_{\alpha },-{\lambda }_{\alpha }\rangle -\langle \eta e-d_{\gamma },{\upsilon }_{\gamma }\rangle \le 0\end{array}$

其中 $\left(d,\eta \right)\in T_K\left(\bar{x},\bar{t}\right)$，由此可知 $\langle d_{\alpha },{\lambda }_{\alpha }\rangle =0$， $\langle \eta e-d_{\gamma },{\upsilon }_{\gamma }\rangle =0$

由(5)得 ${\lambda }_{\alpha }=0$， ${\lambda }_{{\alpha }^{\ne }}>0\Rightarrow d_{{\alpha }^{=}}\ge 0$， $d_{{\alpha }^{\ne }}=0$，由(6)得 ${\upsilon }_{{\gamma }^{=}}=0$， ${\upsilon }_{{\gamma }^{\ne }}>0$，由此可知 $\eta e-d_{{\gamma }^{=}}\ge 0$， $\eta e-d_{{\gamma }^{\ne }}=0$，即 $d_{{\gamma }^{=}}\le \eta e$， $d_{{\gamma }^{\ne }}=\eta e$。

则 $\bar{K}=\{\begin{array}{l}K;\left(x,t\right)\in K\\ \left\{\left(0,0\right)\right\};\left(x,t\right)\in \mathrm{int}{K}^0\\ \left\{\left(d,\eta \right):\eta \ge 0,{\left(\frac{d}{\eta }\right)}_{T_{>}}=e,{\left(\frac{d}{\eta }\right)}_{T_{<}}=0,0\le {\left(\frac{d}{\eta }\right)}_{T_{=}}\le e\right\};\left(x,t\right)\in bd\left(K^0\right)\backslash \left\{\left(0,0\right)\right\}\\ \left\{\left(d,\eta \right):d_{{\alpha }^{=}}\ge 0,d_{{\alpha }^{\ne }}=0,d_{{\gamma }^{=}}\le \eta e,d_{{\lambda }^{\ne }}=\eta e\right\};其他\end{array}$。

4. 结论

本文研究了集合K的对偶锥、切锥、极锥和临界锥，为进一步研究增广拉格朗日方法，投影算子微分性质的研究以及灵敏性分析等相关优化问题奠定了一定的理论基础。