凸集分离定理_对偶定理_鞍点定理

目录

• 凸优化
• • • 定理
• 凸集分离定理
• • • 定理1
    • 定理2
    • 定理3
    • 分离定理
    • Farkas定理
    • Gordan定理
• 对偶定理
• • • 原问题
    • 对偶问题
    • 弱对偶定理
    • • 推论1
      • 推论2
      • 推论3
      • 推论4
    • 引理
    • 强对偶定理
  • 鞍点定理
  • • 原问题
    • 对偶问题
    • 鞍点定义
    • 鞍点定理

凸优化

min ⁡ f ( x ) s . t . g i ( x ) ≥ 0 i = 1 , ⋯ m h j ( x ) = 0 j = 1 , ⋯ l \begin{aligned} &\min &&f(\boldsymbol x)\\ &s.t. &&\boldsymbol{g_i(x)\geq 0} &&i=1,\cdots m\\ &&&\boldsymbol{h_j(x)=0} &&j=1,\cdots l\\ \end{aligned} ​mins.t.​​f(x)gi​(x)≥0hj​(x)=0​​i=1,⋯mj=1,⋯l​
\quad 其中$f(\mathbf{x})$是凸函数， g i ( x ) g_i(\boldsymbol x) gi​(x)是凹函数, h j ( x ) h_j(x) hj​(x)是线性函数。

定理

\quad 设$S$是 R n R^n Rn中非空凸集，$f$是定义在$S$上的凸函数，则$f$在$S$上的局部极小点是全局极小点，且极小点的集合为凸集。

凸集分离定理

定理1

\quad 设$S$为 R n R^n Rn中的闭凸集,$\mathbf{y}\notin S$,使得 x ˉ ∈ S \boldsymbol{\bar{x}}\in S xˉ∈S,使得: ∥ y − x ˉ ∥ = inf ⁡ x ∈ S ∥ y − x ∥ \parallel \boldsymbol y- \boldsymbol{\bar{x}} \parallel=\inf_{x\in S}\parallel \boldsymbol y-\boldsymbol x\parallel ∥y−xˉ∥=x∈Sinf​∥y−x∥

定理2

\quad 设$S$是 R n R^n Rn中的非空闭凸集，$\mathbf{y}\notin S$，则存在非零向量$\mathbf{p}$及数$\xi >0$，使得对每个点$\mathbf{x}\in S$，成立 p T y ≥ ξ + p T x \boldsymbol{p^Ty}\geq \xi+\boldsymbol{p^Tx} pTy≥ξ+pTx。

定理3

\quad 设$S$是 R n R^n Rn中的非空凸集，$\mathbf{y}\in \partial S$，则存在非零向量$\mathbf{p}$，使得对每个点$\mathbf{x}\in clS$，成立 p T y ≥ p T x \boldsymbol{p^Ty}\geq \boldsymbol{p^Tx} pTy≥pTx。其中$\partial S$表示$S$集合边界，$clS$表示$S$集合的闭包（由$S$的内点和边界点组成）。

分离定理

\quad 设 S 1 S_1 S1​和 S 2 S_2 S2​是 R n R^n Rn中两个非空凸集， S 1 ∩ S 2 = ∅ S_1\cap S_2=\emptyset S1​∩S2​=∅，则存在非零向量$\mathbf{p}$，使 inf ⁡ { p T x ∣ x ∈ S 1 } ≥ sup ⁡ { p T x ∣ x ∈ S 2 } \inf\{\boldsymbol{p^Tx} |\boldsymbol x\in S_1\} \geq \sup\{\boldsymbol{p^Tx}|\boldsymbol x\in S_2\} inf{pTx∣x∈S1​}≥sup{pTx∣x∈S2​}

Farkas定理

\quad 设$\mathbf{A}$为$m\times n$矩阵，$\mathbf{c}$为$n$维向量，则 A x ≤ 0 , c T x > 0 \boldsymbol{Ax}\leq \boldsymbol 0,\boldsymbol {c^Tx}\gt0 Ax≤0,cTx>0有解的充分条件是 A T y = c , y ≥ 0 \boldsymbol{A^Ty=c},\boldsymbol y\geq\boldsymbol 0 ATy=c,y≥0无解。

Gordan定理

\quad 设$\mathbf{A}$为$m\times n$矩阵，那么$\mathbf{A}\mathbf{x}<0$有解的充要条件是不存在非零向量$\mathbf{y}\ge 0$，使 A T y = 0 \boldsymbol{A^Ty=0} ATy=0。

对偶定理

原问题

min ⁡ f ( x ) s . t . g ( x ) ≥ 0 h ( x ) = 0 x ∈ D \begin{aligned} &\min &&f(\boldsymbol x)\\ &s.t. &&\boldsymbol{g(x)\geq 0}\\ &&&\boldsymbol{h(x)=0}\\ &&&\boldsymbol x\in D \end{aligned} ​mins.t.​​f(x)g(x)≥0h(x)=0x∈D​

对偶问题

max ⁡ θ ( w , v ) s . t . w ≥ 0 \begin{aligned} &\max &&\theta(\boldsymbol {w,v})\\ &s.t. &&\boldsymbol{ w\geq 0} \end{aligned} ​maxs.t.​​θ(w,v)w≥0​
\quad 其中对偶函数 θ ( w , v ) = inf ⁡ { f ( x ) − w T g ( x ) − v T h ( x ) ∣ x ∈ D } \theta(\boldsymbol{w,v})=\inf\{f(\boldsymbol x)-\boldsymbol{w^Tg(x)-v^Th(x)}|\boldsymbol x\in D\} θ(w,v)=inf{f(x)−wTg(x)−vTh(x)∣x∈D}。

弱对偶定理

\quad 设$\mathbf{x}$和$(\mathbf{w},\mathbf{v})$分别是原问题和对偶问题的可行解，则:
$$f(\mathbf{x})\ge \theta (\mathbf{w},\mathbf{v})$$

推论1

\quad 对于原问题和对偶问题，必有:
inf ⁡ { f ( x ) ∣ g ( x ) ≥ 0 , h ( x ) = 0 , x ∈ D } ≥ sup ⁡ { θ ( w , v ) ∣ w ≥ 0 } \inf \{f(\boldsymbol x)|\boldsymbol{g(x)\geq0,h(x)=0,x\in}D\}\geq\sup\{\theta\boldsymbol{(w,v)}|\boldsymbol{w \geq 0}\} inf{f(x)∣g(x)≥0,h(x)=0,x∈D}≥sup{θ(w,v)∣w≥0}

推论2

\quad 如果 f ( x ˉ ) ≤ θ ( w ˉ , v ˉ ) f(\boldsymbol{\bar{x}}) \leq\theta\boldsymbol{(\bar{w},\bar{v})} f(xˉ)≤θ(wˉ,vˉ)，其中:
x ˉ ∈ { x ∣ g ( x ) ≥ 0 , h ( x ) = 0 , x ∈ D } , w ˉ ≥ 0 \boldsymbol{\bar{x}}\in \{\boldsymbol x|\boldsymbol{g(x)\geq0,h(x)=0,x\in}D\},\quad \boldsymbol{\bar{w}}\geq\boldsymbol0 xˉ∈{x∣g(x)≥0,h(x)=0,x∈D},wˉ≥0
\quad 则 x ˉ \boldsymbol{\bar{x}} xˉ和 ( w ˉ , v ˉ ) \boldsymbol{(\bar{w}, \bar{v})} (wˉ,vˉ)分别是原问题和对偶问题的最优解。

推论3

\quad 如果
inf ⁡ { f ( x ) ∣ g ( x ) ≥ 0 , h ( x ) = 0 , x ∈ D } = − ∞ \inf \{f(\boldsymbol x)|\boldsymbol{g(x)\geq0,h(x)=0,x\in}D\}=-\infty inf{f(x)∣g(x)≥0,h(x)=0,x∈D}=−∞
\quad 则对每一个$\mathbf{w}\ge 0$，有
$$\theta (\mathbf{w},\mathbf{v})=-\infty$$.

推论4

\quad 如果
sup ⁡ { θ ( w , v ) ∣ w ≥ 0 } = ∞ \sup\{\theta\boldsymbol{(w,v)}|\boldsymbol{w \geq 0}\}=\infty sup{θ(w,v)∣w≥0}=∞
\quad 则原问题没有可行解。

引理

\quad 设$D$是 R n R^n Rn中一个非空凸集， φ ( x ) 和 g i ( x ) ( i = 1 , ⋯ m ) 分 别 是 \varphi(\boldsymbol x)和g_i(\boldsymbol x)(i=1,\cdots m)分别是 φ(x)和gi​(x)(i=1,⋯m)分别是 R n R^n Rn上的凸函数和凹函数， h j ( x ) ( j = 1 , ⋯ l ) h_j(\boldsymbol x)(j=1,\cdots l) hj​(x)(j=1,⋯l)是 R n R^n Rn上的线性函数，即假设：$$\mathbf{h}(\mathbf{x})=\mathbf{A}\mathbf{x}-\mathbf{b}$$
\quad 那么下列两个系统中，若系统1无解，则系统2必有解 ( w 0 , w , v ) (w_0,\boldsymbol w,\boldsymbol v) (w0​,w,v)；反之，若系统2有解 ( w 0 , w , v ) (w_0,\boldsymbol w,\boldsymbol v) (w0​,w,v), w 0 > 0 w_0\gt0 w0​>0，则系统1无解。
\quad 系统1 \quad 存在$\mathbf{x}\in D$，使得$\phi (\mathbf{x})<0,\mathbf{g}(\mathbf{x})\ge 0,\mathbf{h}(\mathbf{x})=0$；
\quad 系统2 \quad w 0 φ ( x ) − w T g ( x ) − v T h ( x ) ≥ 0 , ∀ x ∈ D , ( w 0 , w ) ≥ 0 , ( w 0 , w , v ) ≠ 0 w_0\varphi(\boldsymbol x)-\boldsymbol{w^Tg(x)-v^Th(x)}\ge0,\forall\boldsymbol x\in D,(w_0,\boldsymbol w)\ge\boldsymbol0,(w_0\boldsymbol{,w, v})\neq\boldsymbol 0 w0​φ(x)−wTg(x)−vTh(x)≥0,∀x∈D,(w0​,w)≥0,(w0​,w,v)​=0

强对偶定理

\quad 设$D$是 R n R^n Rn中一个非空凸集，$f$和 g i ( i = 1 , ⋯ m ) g_i(i=1,\cdots m) gi​(i=1,⋯m)分别是 R n R^n Rn上的凸函数和凹函数， h j ( j = 1 , ⋯ l ) h_j(j=1,\cdots l) hj​(j=1,⋯l)是 R n R^n Rn上的线性函数，即$\mathbf{h}(\mathbf{x})=\mathbf{A}\mathbf{x}-\mathbf{b}$，又设存在点 x ^ ∈ D \hat{\boldsymbol x}\in D x^∈D，使得
g ( x ^ ) > 0 , h ( x ^ ) = 0 , 0 ∈ i n t H ( D ) H ( D ) = { h ( x ) ∣ x ∈ D } \boldsymbol{g(\hat{x})\gt0,h(\hat{x})=0,0\in }int H(D)\quad H(D)=\{\boldsymbol{h(x)}|\boldsymbol x\in D\} g(x^)>0,h(x^)=0,0∈intH(D)H(D)={h(x)∣x∈D}
\quad 则：
inf ⁡ { f ( x ) ∣ g ( x ) ≥ 0 , h ( x ) = 0 , x ∈ D } = sup ⁡ { θ ( w , v ) ∣ w ≥ 0 } \inf \{f(\boldsymbol x)|\boldsymbol{g(x)\geq0,h(x)=0,x\in}D\}= \sup\{\theta\boldsymbol{(w,v)}|\boldsymbol{w \geq 0}\} inf{f(x)∣g(x)≥0,h(x)=0,x∈D}=sup{θ(w,v)∣w≥0}
\quad 而且，若式中$inf$为有限值，则:
sup ⁡ { θ ( w , v ) ∣ w ≥ 0 } \sup\{\theta\boldsymbol{(w,v)}|\boldsymbol{w \geq 0}\} sup{θ(w,v)∣w≥0}
\quad 在 ( w ˉ , v ˉ ) \boldsymbol{(\bar{w},\bar{v})} (wˉ,vˉ)（在证明过程中得到的变量）达到， x ˉ ≥ 0 \boldsymbol{\bar{ x}\ge0} xˉ≥0。如果$inf$在点 x ˉ \boldsymbol{\bar{x}} xˉ达到，则 w ˉ T g ( x ˉ ) = 0 \boldsymbol{\bar{w}^Tg(\bar{x})}=0 wˉTg(xˉ)=0。

鞍点定理

原问题

min ⁡ f ( x ) , x ∈ R n s . t . g ( x ) ≥ 0 h ( x ) = 0 \begin{aligned} &\min &&f(\boldsymbol x) , \quad \boldsymbol x\in R^n \\ &s.t. &&\boldsymbol{g(x)\geq 0}\\ &&&\boldsymbol{h(x)=0} \end{aligned} ​mins.t.​​f(x),x∈Rng(x)≥0h(x)=0​

对偶问题

max ⁡ θ ( w , v ) s . t . w ≥ 0 \begin{aligned} &\max &&\theta(\boldsymbol {w,v})\\ &s.t. &&\boldsymbol{ w\geq 0} \end{aligned} ​maxs.t.​​θ(w,v)w≥0​
\quad 其中对偶函数 θ ( w , v ) = inf ⁡ { f ( x ) − w T g ( x ) − v T h ( x ) ∣ x ∈ R n } \theta(\boldsymbol{w,v})=\inf\{f(\boldsymbol x)-\boldsymbol{w^Tg(x)-v^Th(x)}|\boldsymbol x\in R^n\} θ(w,v)=inf{f(x)−wTg(x)−vTh(x)∣x∈Rn}。

鞍点定义

\quad 设$L(\mathbf{x},\mathbf{w},\mathbf{v})$为$Lagrange$函数, x ˉ ∈ R n , w ˉ ∈ R m , w ˉ ≥ 0 , v ˉ ∈ R l \bar{\boldsymbol x}\in R^n,\bar{\boldsymbol w}\in R^m,\boldsymbol{\bar{ w}\ge0},\boldsymbol{\bar{v}}\in R^l xˉ∈Rn,wˉ∈Rm,wˉ≥0,vˉ∈Rl，如果对每个 x ∈ R n , w ∈ R m , w ≥ 0 及 v ∈ R l \boldsymbol x\in R^n,\boldsymbol w\in R^m,\boldsymbol{w\ge0}及\boldsymbol v \in R^l x∈Rn,w∈Rm,w≥0及v∈Rl，都有
L ( x ˉ , w , v ) ≤ L ( x ˉ , w ˉ , v ˉ ) ≤ L ( x , w ˉ , v ˉ ) L(\boldsymbol{\bar{x}, w, v})\le L(\boldsymbol{\bar{x}, \bar{w}, \bar{v}})\le L(\boldsymbol{x, \bar{w}, \bar{v}}) L(xˉ,w,v)≤L(xˉ,wˉ,vˉ)≤L(x,wˉ,vˉ)
\quad 则称 ( x ˉ , w ˉ , v ˉ ) (\boldsymbol{\bar{x}, \bar{w}, \bar{v}}) (xˉ,wˉ,vˉ)为$L(\mathbf{x},\mathbf{w},\mathbf{v})$的鞍点。

鞍点定理

\quad 设 ( x ˉ , w ˉ , v ˉ ) (\boldsymbol{\bar{x},\bar{w},\bar{v}}) (xˉ,wˉ,vˉ)是原问题的$lagrange$函数$L(\mathbf{x},\mathbf{w},\mathbf{v})$的鞍点，则 x ˉ \boldsymbol{\bar{x}} xˉ和 ( w ˉ , v ˉ ) \boldsymbol{(\bar{w}, \bar{v})} (wˉ,vˉ)分别是原问题和对偶问题的最优解。
\quad 反之，假设$f$是凸函数， g i ( i = 1 , ⋯ , m ) g_i(i=1, \cdots,m) gi​(i=1,⋯,m)是凹函数， h j ( j = 1 , ⋯ l ) h_j(j=1, \cdots l) hj​(j=1,⋯l)是线性函数，即$\mathbf{h}(\mathbf{x})=\mathbf{A}\mathbf{x}-\mathbf{b}$，且$A$满秩，又设存在 x ^ \boldsymbol{\hat{x}} x^，使 g ( x ^ ) > 0 , h ( x ^ ) = 0 \boldsymbol{g(\hat{x})\gt0,h(\hat{x})=0} g(x^)>0,h(x^)=0。如果 x ˉ \boldsymbol{\bar{x}} xˉ是原问题的最优解，则存在 ( w ˉ , v ˉ ) , w ˉ ≥ 0 (\boldsymbol{\bar{w}, \bar{v}}),\boldsymbol{\bar{w}\ge0} (wˉ,vˉ),wˉ≥0,使得 ( x ˉ , w ˉ , v ˉ ) (\boldsymbol{\bar{x},\bar{w},\bar{v}}) (xˉ,wˉ,vˉ)是$lagrange$函数$L(\mathbf{x},\mathbf{w},\mathbf{v})$的鞍点。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！