优化理论-基础

优化理论基础

证明链条：凸集与超平面->凸集分离定理->Farkas引理>Gordan定理和择一性定理->Kuhn-Tucker条件

• 凸集的定义和性质
• 性质
• 凸集的极点
• 凸集的方向
• 射线
• 方向的定义
• 极方向
• 凸集的极射线
• 多面集的表示定理
• 多面集表示定理
• 锥与凸锥
• 凸集分离定理
• Farkas引理
• Gordan定理
• 附录

凸集的定义和性质

设\(S⊆R^n\)，若对\(∀x_1,x_2∈S\)及\(∀λ∈[0,1]\)，都有\(λx_1+(1−λ)x_2∈S\)，则称\(S\)为凸集。

性质

设\(S_1和S_2\)是两个凸集，\(β\)实数，则

• \(\beta S_1=\{\beta x|x \in S_1\}\)是凸集
• \(S_1+S_2= \{x_1+x_2|x_1 \in S_1, x_2 \in S_2\}\)是凸集
• \(S_1-S_2=\{x_1-x_2|x_1 \in S_1, x_2 \in S_2\}\)是凸集
• \(S_1 \cap S_2\)是凸集

凸集的极点

设\(S\)是非空集合，\(x∈S\)，若\(x\)不能表示成\(S\)中两个不同点的凸组合，即若假设\(x=λx_1+(1−λ)x_2\)，必推出\(x=x_1=x_2\)，则称\(x\)是凸集\(S\)的极点。从图形的角度来看，\(x\)是多边形的顶点或曲边的点。

凸集的方向

射线

\(∀α_0,\vec{d}\in R^n,\vec{d}≠0\)称集合 \(S=\{α_0+k\vec{d}|k∈R,k≥0\}\)为一条射线。称\(α_0\)为射线的顶点，\(\vec{d}\)为射线的方向。

射线\(S=\{\alpha_0+k\vec{d}|k \in R,k\geq 0\}\)是凸集。

证明：\(\forall \alpha,\beta \in S,\exist k_1 \in R,k_1\geq 0,\)使得\(\alpha = \alpha_0+k_1\vec{d};\exist k_2 \in R,k_2\geq 0,\)使得\(\beta = c\)。对于\(\forall \lambda \in [0,1],\lambda k_1+(1-\lambda)k_2 \geq 0\)，于是\(\lambda\alpha+(1-\lambda)\beta=\lambda(\alpha_0+k_1\vec{d})+(1-\lambda)(\alpha_0+k_2\vec{d})=\alpha_0+[\lambda k_1+(1-\lambda)k_2]\vec{d}\in S\)。即射线\(S\)为凸集。

方向的定义

对于任意一个凸集\(S\)，\(\forall \vec{d}\in R^n,d \neq 0,若\forall \alpha_0 \in S,\forall k \in R,k \geq 0,都有\alpha_0+k\vec{d} \in S\)，则称\(\vec{d}\)为\(S\)的一个方向。

comment： 方向能够无限延伸，说明在此方向上所有的点都在凸集内。方向是射线，起点是任意的，在方向上无界。

设\(S=\{x∣Ax=b,x≥0\}≠∅\)，\(\vec{d}\)是非零向量，则\(\vec{d}\)是\(S\)的方向 ⟺ \(\vec{d}≥0且A\vec{d}=0\)。

极方向

对于任意一个凸集\(S\),对于 \(S\)中的任意两个方向\(\vec{d}_1,\vec{d}_2\), 若\(\forall k>0,\vec{d}_1\neq k \vec{d}_2\),则称这两个方向是不同的。

若\(\vec{d}\)是S的一个方向，且不是S的任意两个不同方向的正线性组合。即：对于S的任意两个方向\(\vec{d}_1,\vec{d}_2\)，若存在\(k_1>0,k_2>0\)，使得\(k_1\vec{d}_1+k_2\vec{d}_2=\vec{d}\)，则\(\vec{d}_1,\vec{d}_2\)必是相同的方向，则称\(\vec{d}\)是S的一个极方向。

凸集的极射线

凸集S中的任意一条射线，若它的方向是极方向，则称这条射线为极射线。

多面集的表示定理

多面集：在空间\(\mathbb{R}^n\)中，由有限个闭半空间相交组成的集合： \[S=\{x \in \mathbb{R}^n:P_i^T x \leq \alpha_i,i=1,2,\dotsb,m\}\]

多面锥：在空间\(\mathbb{R}^n\)中，由有限个包含原点的半空间相交而成： \[S=\{x \in \mathbb{R}^n:P_i^T x \leq 0,i=1,2,\dotsb,m\}\]

多面体：有界的多面集。

• 多面体是有限个点集的凸包。
• 凸锥可以有有限个向量生成（凸锥组合）
• 多面集是闭集
• 多面集是凸集

多面集表示定理

设\(S=\{X∈\mathbb{R}^n:AX≤\vec{b},X≥\vec{0}\}\)为非空多面集，其中 \[A=\begin{pmatrix} a_1 \\ a_2 \\ \vdots\\ a_m \end{pmatrix} \in \mathbb{R}^{m\times n}, b=\begin{pmatrix} b_1 \\ b_2 \\ \vdots\\ b_m \end{pmatrix} \in \mathbb{R}^{m}\] 则有：

• 极点集非空，且存在有限个极点\(\{X(1),⋯,X(k)\}, k \in N,k \geq 1\)
• 极方向集合为空集 ⟺ \(S\)有界。若\(S\)无界，则存在有限个极方向\(\{d(1),d(2),⋯,d(l)\},l \in N ,l \geq 0\)
• \(∀X∈R_n,X∈S\)当且仅当\(X\) 可以被表示成\(X_1,⋯,X_k\)的凸组合加上\(d_1,⋯,d_l\)的非负线性组合，即存在集合 \[\{λ_i∈R:\sum_{i=1}^k λ_i=1,λ_i≥0,i∈N,1≤i≤k\}与 \\ \{ \mu_i \in \mathbb R: \mu_i \ge 0, i \in \mathbb N, 1 \le i \le l \} \\ 使得：X = \sum\limits_{i = 1}^{k} \lambda_i X_i + \sum\limits_{i = 1}^{l} \mu_i d_i\]

锥与凸锥

锥(cone) 定义：对于集合\(C⊆R_n,∀x∈C,θ≥0\)，有\(θx⊆C\)则\(x\)构成的集合称为锥。说明一下，锥不一定是连续的（可以是数条过原点的射线的集合）。

凸锥（convex cone）定义：凸锥包含了集合内点的所有凸锥组合。若锥\(C⊆R_n,x_1,x_2...x_n∈C,θ_i≥0\)，则凸锥组合\(θ_1 x_1+θ_2 x_2+...+θ_n x_n\)也属于凸锥集合\(C\)。这里说明一下，就是说一个集合既是凸集又是锥，那么就是凸锥。

凸锥包（convex cone hull）定义：凸锥包是包含集合\(C\)的最小的凸锥，假设\(x_1,x2_...x_n∈C\)，凸锥包表示为： \[\{θ_1x_1+θ_2x_2+...+θ_nx_n|x_1,x_2...x_n∈C，θ_i≥0\}\]

另见常见的凸集，凸锥，仿射集:https://www.cnblogs.com/saysei/p/10124314.html

凸集分离定理

凸集分离定理（超平面分离定理）是应用凸集到最优化理论中的重要结果，这个结果在最优化理论中有重要的位置。所谓两个凸集分离，直观地看是指两个凸集合没有交叉和重合的部分，因此可以用一张超平面将两者隔在两边。需要注意的是，凸集分离定理研究n维欧式空间，所以“紧”的概念等同于闭合+有界。

设\(S_1,S_2\subseteq R^n\)为两个非空集合,且\(S_1\cap S_2=\emptyset\)，如果存在非零向量\(\vec{p}\in R^n\)及\(\alpha \in R\)使得 \[S_1 \subseteq H^-=\{x\in R^n|\vec{p}^Tx\leq \alpha\}\] \[S_2 \subseteq H^+=\{x\in R^n|\vec{p}^Tx\geq \alpha\}\] 则称超平面\(H=\{x \in R^n |\vec{p}^T x=\alpha\}\)分离了集合\(S_1与S_2\)。

证明： 首先我们需要证明一个引理。

引理 \(K\subset R^n\)，且K是非空闭凸集。那么在K种存在唯一一个向量具有最小范数（长度）。

引理证明：令\(\delta=\inf\{|x|\mid x\in K\}\)。令\(x_j\)为K中的一个序列，且\(|x_j|\to\delta\)。注意到K是一个凸集，且\((x_i+x_j)/2\)也会在K中。所以\((x_i+x_j)/2\)的范数大于\(\delta\)。 \[|(x_i+x_j)/2|\geq|\delta|\Rightarrow |x_i+x_j|^2 \geq 4\delta^2 \\ |x_i-x_j|^2=2|x_i|^2+2|x_j|^2-|x_i+x_j|^2\\ \leq 2|x_i|^2+2|x_j|^2-4\delta^2 \to 0\] 由于\(i,j\to\infty\)，并且\(x_i\)是柯西序列，因此x的极限在K中。唯一性是由于y也在K中有范数，而\(|x-y|^2 \leq 2|x_i|^2+2|x_j|^2-4\delta^2=0\)，根据范数定义\(x=y\)。

接下来继续超平面分离定理证明。考虑两个不相交的分控凸集\(A，B\)，令\(K=A+(-B)=\{x-y|x\in A,y\in B\}\)。由于\(-B\)也是凸集，所以\(K\)也是凸集。由于K可能是开集，我们考虑K的闭包\(\overline{K}\)（闭集），有一个最小范数的向量\(v\)。由于\(\overline{K}\)是凸的，所以对于\(\forall n \in K\)，线段 \[v+t(n-v),0\leq t \leq 1\] 也在\(\overline{K}\)中，所以 \[|v|^2\leq |v+t(n-v)^2|=|v|^2+2t<v,n-v>+t^2|n-v|^2\] 上式是因为\(v\)是唯一最小范数。对于\(0<t \leq 1\)，我们有 \[0\leq 2<v,n>-2|v|^2+t|n-v|^2\\ |v|^2-0.5t|n-v|^2\leq <v,n>\] 当\(t\to 0\)时，\(<n,v>\geq |v|^2\)。因此对于任意\(x \in A\)和\(y \in B\),有\(<x-y,v> \geq |v|^2\)。所以，如果\(v\)时非零的。那么： \[\inf_{x \in A}\langle x,v \rangle \geq |v|^2+\sup_{y \in B}\langle y,v \rangle\] 即存在一个平面分隔了凸集\(A,B\)。更广泛的\(v=0\)说明可见维基百科。

另一个证明：https://www.cnblogs.com/szqfreiburger/p/11573936.html

Farkas引理

令\(A\in \mathbb{R}^{m\times n},\mathbf{b}\in \mathbb{R}^m\)，那么下面两个陈述只有一个成立：

1. 存在\(\mathbf{x}\in \mathbb{R}^n，使得Ax=b,且x \geq 0\)
2. 存在\(y \in \mathbb{R}^m,使得A^Ty\geq 0，且b^Ty<0\).

需要注意的时，\(\mathbf{x}\geq 0\)是指向量\(\mathbf{x}\)的所有组成元素都非负。

先从几何角度了解一下这个引理的含义。我们认为矩阵\(A\)是由\(n\)个\(m\)维的向量组成的向量组，由于在(1)中\(x\)的每一个元素大于0，所以\(Ax\)为\(n\)个向量的非负线性组合，即凸锥组合。它们张成的是凸锥（或者说包含这\(n\)个向量的凸锥包），长成下图所示。

凸锥包

每一条棱表示\(A\)中的一个向量。而（1）结果\(Ax=b\)，表示\(b\)在凸锥中，如下左图。

对于情形（2），则是凸集分离定理的推广。单点也是凸集。特别的，如果\(C\)不仅是凸集，还是事实一中所提到的凸锥，我们可以找到一个过原点的平面，分开凸锥和它外面的一个点，也就是说如果\(C\)是一个凸锥，\(x \notin C\)，存在非零 \(d\in R^n\)满足对于所有的 \(y in C\)，有\(d^Tx<0\)，且\(d^Ty>0\)。上面右图所示。

严格证明可以参考:https://lijiancheng0614.github.io/2015/09/17/2015_09_17_Optimization%20Methods/

Gordan定理

设\(A\)为\(m×n\)矩阵，则\(Ax<0\)有解，⟺ \(A^Ty=0,y≥0(y≠0)\)无解。

附录

在\(R^n\)中，下面三个条件等价：

• “有界闭”（bounded and closed）；
• “紧”（compact）；
• “列紧”（sequentially compact）。