凸分析 是研究凸函數 與凸集 性質的數學 分支,其應用稱作凸優化 ,是最優化 理論的子分支。
3維凸多面體。凸分析不僅包括歐氏空間凸子集的研究,還包含抽象空間上凸函數的研究。
某向量空間 X 的子集
C
⊆
X
{\displaystyle C\subseteq X}
,若滿足下列任意一條等價條件,就稱其是凸 的(convex):
若
0
≤
r
≤
1
{\displaystyle 0\leq r\leq 1}
是實數,
x
,
y
∈
C
{\displaystyle x,y\in C}
,則
r
x
+
(
1
−
r
)
y
∈
C
.
{\displaystyle rx+(1-r)y\in C.}
[ 1]
若
0
<
r
<
1
{\displaystyle 0<r<1}
是實數,
x
,
y
∈
C
,
x
≠
y
,
{\displaystyle x,y\in C,\ x\neq y,}
則
r
x
+
(
1
−
r
)
y
∈
C
.
{\displaystyle rx+(1-r)y\in C.}
區間上的凸函數
f
:
X
→
[
−
∞
,
∞
]
{\displaystyle f:X\to [-\infty ,\infty ]}
始終是以擴展實數線
[
−
∞
,
∞
]
=
R
∪
{
±
∞
}
{\displaystyle [-\infty ,\infty ]=\mathbb {R} \cup \{\pm \infty \}}
為值域、以某向量空間的凸子集
domain
f
=
X
{\displaystyle \operatorname {domain} f=X}
為定義域 的映射。
映射
f
:
X
→
[
−
∞
,
∞
]
{\displaystyle f:X\to [-\infty ,\infty ]}
,若
f
(
r
x
+
(
1
−
r
)
y
)
≤
r
f
(
x
)
+
(
1
−
r
)
f
(
y
)
{\displaystyle f(rx+(1-r)y)\leq rf(x)+(1-r)f(y)}
(凸性
≤
{\displaystyle \leq }
)
對所有實數
0
<
r
<
1
{\displaystyle 0<r<1}
、所有
x
,
y
∈
X
,
x
≠
y
{\displaystyle x,y\in X,\ x\neq y}
都成立,稱映射f 是凸函數 。若此不等式被替換為嚴格不等式
f
(
r
x
+
(
1
−
r
)
y
)
<
r
f
(
x
)
+
(
1
−
r
)
f
(
y
)
{\displaystyle f(rx+(1-r)y)<rf(x)+(1-r)f(y)}
(凸性
<
{\displaystyle <}
)
對f 仍成立,則稱f 是嚴格凸 的。[ 1]
凸函數與凸集有關。特別地,當且僅當函數f 的上圖(epigraph)
當且僅當函數(黑色)的上圖(即函數圖像 上方區域,綠色)是凸集 時,函數是凸的。
二元凸函數
x
2
+
x
y
+
y
2
{\displaystyle x^{2}+xy+y^{2}}
的圖像
epi
f
:=
{
(
x
,
r
)
∈
X
×
R
:
f
(
x
)
≤
r
}
{\displaystyle \operatorname {epi} f:=\left\{(x,r)\in X\times \mathbb {R} ~:~f(x)\leq r\right\}}
是凸集時,函數f 是凸的。擴展實值函數的上圖在凸分析中的作用類似於實值函數圖像 在實分析 中的作用。特別地,擴展實值函數的上圖提供了幾何直覺,可用於形式化或證明猜想。
函數
f
:
X
→
[
−
∞
,
∞
]
{\displaystyle f:X\to [-\infty ,\infty ]}
的定義域記作
domain
f
{\displaystyle \operatorname {domain} f}
,有效域 則是集合
dom
f
:=
{
x
∈
X
:
f
(
x
)
<
∞
}
.
{\displaystyle \operatorname {dom} f:=\{x\in X~:~f(x)<\infty \}.}
函數
f
:
X
→
[
−
∞
,
∞
]
{\displaystyle f:X\to [-\infty ,\infty ]}
,當且僅當
∀
x
∈
domain
f
,
f
(
x
)
>
−
∞
,
dom
f
≠
∅
{\displaystyle \forall x\in \operatorname {domain} f,\ f(x)>-\infty ,\ \operatorname {dom} f\neq \varnothing }
,稱函數是真凸函數 。這意味着在f 的定義域中存在x 使
f
(
x
)
∈
R
{\displaystyle f(x)\in \mathbb {R} }
,f 也永遠不等於
f
{\displaystyle f}
−
∞
{\displaystyle -\infty }
。換句話說,若函數的定義域非空、永遠不取
−
∞
{\displaystyle -\infty }
、不等於
+
∞
{\displaystyle +\infty }
,則就是真凸函數。若
f
:
R
n
→
[
−
∞
,
∞
]
{\displaystyle f:\mathbb {R} ^{n}\to [-\infty ,\infty ]}
是真凸函數 ,則存在向量
b
→
∈
R
n
{\displaystyle {\vec {b}}\in \mathbb {R} ^{n}}
、實數
r
∈
R
{\displaystyle r\in \mathbb {R} }
使得
∀
x
,
f
(
x
)
≥
x
⋅
b
−
r
{\displaystyle \forall x,\ f(x)\geq x\cdot b-r}
其中
x
⋅
b
{\displaystyle x\cdot b}
表示向量的點積 。
擴展實值函數
f
:
X
→
[
−
∞
,
∞
]
{\displaystyle f:X\to [-\infty ,\infty ]}
(不必凸)的凸共軛是來自X 的(連續)對偶空間 函數
f
∗
:
X
∗
→
[
−
∞
,
∞
]
{\displaystyle f^{*}:X^{*}\to [-\infty ,\infty ]}
f
∗
(
x
∗
)
=
sup
z
∈
X
{
⟨
x
∗
,
z
⟩
−
f
(
z
)
}
{\displaystyle f^{*}\left(x^{*}\right)=\sup _{z\in X}\left\{\left\langle x^{*},z\right\rangle -f(z)\right\}}
其中,括號
⟨
⋅
,
⋅
⟩
{\displaystyle \left\langle \cdot ,\cdot \right\rangle }
表示規範對偶性
⟨
x
∗
,
z
⟩
:=
x
∗
(
z
)
{\displaystyle \left\langle x^{*},z\right\rangle :=x^{*}(z)}
。f 的雙共軛是映射
f
∗
∗
=
(
f
∗
)
∗
:
X
→
[
−
∞
,
∞
]
{\displaystyle f^{**}=\left(f^{*}\right)^{*}:X\to [-\infty ,\infty ]}
,定義為
∀
x
∈
X
,
f
∗
∗
(
x
)
:=
sup
z
∗
∈
X
∗
{
⟨
x
,
z
∗
⟩
−
f
(
z
∗
)
}
{\displaystyle \forall x\in X,\ f^{**}(x):=\sup _{z^{*}\in X^{*}}\left\{\left\langle x,z^{*}\right\rangle -f\left(z^{*}\right)\right\}}
將X 上的Y 值函數記作
Func
(
X
;
Y
)
{\displaystyle \operatorname {Func} (X;Y)}
,則
f
↦
f
∗
{\displaystyle f\mapsto f^{*}}
定義的映射
Func
(
X
;
[
−
∞
,
∞
]
)
→
Func
(
X
∗
;
[
−
∞
,
∞
]
)
{\displaystyle \operatorname {Func} (X;[-\infty ,\infty ])\to \operatorname {Func} \left(X^{*};[-\infty ,\infty ]\right)}
乘坐勒讓德-芬切爾變換。
若
x
∈
X
,
f
:
X
→
[
−
∞
,
∞
]
{\displaystyle x\in X,\ f:X\to [-\infty ,\infty ]}
,則次微分集(subdifferential set)為
∂
f
(
x
)
:
=
{
x
∗
∈
X
∗
:
f
(
z
)
≥
f
(
x
)
+
⟨
x
∗
,
z
−
x
⟩
for all
z
∈
X
}
(
“
z
∈
X
''
can be replaced with:
“
z
∈
X
such that
z
≠
x
''
)
=
{
x
∗
∈
X
∗
:
⟨
x
∗
,
x
⟩
−
f
(
x
)
≥
⟨
x
∗
,
z
⟩
−
f
(
z
)
for all
z
∈
X
}
=
{
x
∗
∈
X
∗
:
⟨
x
∗
,
x
⟩
−
f
(
x
)
≥
sup
z
∈
X
⟨
x
∗
,
z
⟩
−
f
(
z
)
}
The right hand side is
f
∗
(
x
∗
)
=
{
x
∗
∈
X
∗
:
⟨
x
∗
,
x
⟩
−
f
(
x
)
=
f
∗
(
x
∗
)
}
Taking
z
:=
x
in the
sup
gives the inequality
≤
.
{\displaystyle {\begin{alignedat}{4}\partial f(x):&=\left\{x^{*}\in X^{*}~:~f(z)\geq f(x)+\left\langle x^{*},z-x\right\rangle {\text{ for all }}z\in X\right\}&&({\text{“}}z\in X{\text{''}}{\text{ can be replaced with: }}{\text{“}}z\in X{\text{ such that }}z\neq x{\text{''}})\\&=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle -f(x)\geq \left\langle x^{*},z\right\rangle -f(z){\text{ for all }}z\in X\right\}&&\\&=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle -f(x)\geq \sup _{z\in X}\left\langle x^{*},z\right\rangle -f(z)\right\}&&{\text{ The right hand side is }}f^{*}\left(x^{*}\right)\\&=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle -f(x)=f^{*}\left(x^{*}\right)\right\}&&{\text{ Taking }}z:=x{\text{ in the }}\sup {}{\text{ gives the inequality }}\leq .\\\end{alignedat}}}
例如,在
f
=
‖
⋅
‖
{\displaystyle f=\|\cdot \|}
是X 上的範數這一重要特例中,可以證明[ proof 1]
若
0
≠
x
∈
X
{\displaystyle 0\neq x\in X}
,則此定義可簡化為:
∂
f
(
x
)
=
{
x
∗
∈
X
∗
:
⟨
x
∗
,
x
⟩
=
‖
x
‖
and
‖
x
∗
‖
=
1
}
{\displaystyle \partial f(x)=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle =\|x\|{\text{ and }}\left\|x^{*}\right\|=1\right\}}
;
∂
f
(
0
)
=
{
x
∗
∈
X
∗
:
‖
x
∗
‖
≤
1
}
.
{\displaystyle \partial f(0)=\left\{x^{*}\in X^{*}~:~\left\|x^{*}\right\|\leq 1\right\}.}
∀
x
∈
X
,
x
∗
∈
X
∗
,
f
(
x
)
+
f
∗
(
x
∗
)
≥
⟨
x
∗
,
x
⟩
,
{\displaystyle \forall x\in X,\ x^{*}\in X^{*},\ f(x)+f^{*}\left(x^{*}\right)\geq \left\langle x^{*},x\right\rangle ,}
這就是芬切爾-揚不等式,當且僅當
x
∗
∈
∂
f
(
x
)
{\displaystyle x^{*}\in \partial f(x)}
時是等式。正是通過這種方式,次微分集
∂
f
(
x
)
{\displaystyle \partial f(x)}
與凸共軛
f
∗
(
x
∗
)
{\displaystyle f^{*}\left(x^{*}\right)}
直接相關。
函數
f
:
X
→
[
−
∞
,
∞
]
{\displaystyle f:X\to [-\infty ,\infty ]}
的雙共軛是共軛的共軛,一般寫作
f
∗
∗
:
X
→
[
−
∞
,
∞
]
{\displaystyle f^{**}:X\to [-\infty ,\infty ]}
。雙共軛有助於顯示強對偶 或弱對偶 何時成立(通過擾動函數 )。
∀
x
∈
X
,
{\displaystyle \forall x\in X,}
不等式
f
∗
∗
(
x
)
≤
f
(
x
)
{\displaystyle f^{**}(x)\leq f(x)}
符合芬切爾-揚不等式。對緊合(proper)的函數 ,當且僅當 f 是凸的下半連續 函數時,
f
=
f
∗
∗
{\displaystyle f=f^{**}}
(芬切爾–莫羅定理 )。[ 4]
凸最小化(主)問題形如
給定凸函數
f
:
X
→
[
−
∞
,
∞
]
{\displaystyle f:X\to [-\infty ,\infty ]}
與凸子集
M
⊆
X
{\displaystyle M\subseteq X}
,求
inf
x
∈
M
f
(
x
)
{\displaystyle \inf _{x\in M}f(x)}
優化理論中,對偶原則(duality principle)指出,優化問題可以從兩個角度分別視作主問題與對偶問題。
一般來說,給定一對分離的局部凸空間
(
X
,
X
∗
)
{\displaystyle \left(X,X^{*}\right)}
、
(
Y
,
Y
∗
)
{\displaystyle \left(Y,Y^{*}\right)}
,以及函數
f
:
X
→
[
−
∞
,
∞
]
{\displaystyle f:X\to [-\infty ,\infty ]}
,可以把主問題定義為求x 使得
inf
x
∈
X
f
(
x
)
.
{\displaystyle \inf _{x\in X}f(x).}
可令
f
=
f
+
I
c
o
n
s
t
r
a
i
n
t
s
{\displaystyle f=f+I_{\mathrm {constraints} }}
(其中I 是示性函數 )將約束嵌入f 。那麼讓
F
:
X
×
Y
→
[
−
∞
,
∞
]
{\displaystyle F:X\times Y\to [-\infty ,\infty ]}
是擾動函數 ,使得
F
(
x
,
0
)
=
f
(
x
)
{\displaystyle F(x,0)=f(x)}
。[ 5]
關於所選擾動函數的對偶問題由下式給出:
sup
y
∗
∈
Y
∗
−
F
∗
(
0
,
y
∗
)
{\displaystyle \sup _{y^{*}\in Y^{*}}-F^{*}\left(0,y^{*}\right)}
其中
F
∗
{\displaystyle F^{*}}
是F 兩個變量的凸共軛。
對偶間隙 是不等式左右兩式的差[ 5] [ 7]
sup
y
∗
∈
Y
∗
−
F
∗
(
0
,
y
∗
)
≤
inf
x
∈
X
F
(
x
,
0
)
.
{\displaystyle \sup _{y^{*}\in Y^{*}}-F^{*}\left(0,y^{*}\right)\leq \inf _{x\in X}F(x,0).}
此原理同弱對偶 。若兩側相等,則問題滿足強對偶 。
強對偶成立的條件有很多,如
對不等式約束的凸最小化問題,
min
x
f
(
x
)
{\displaystyle \min {}_{x}f(x)}
subject to
g
i
(
x
)
≤
0
{\displaystyle g_{i}(x)\leq 0}
,其中
i
=
1
,
…
,
m
.
{\displaystyle i=1,\ldots ,m.}
其拉格朗日對偶問題是
sup
u
inf
x
L
(
x
,
u
)
{\displaystyle \sup {}_{u}\inf {}_{x}L(x,u)}
subject to
u
i
(
x
)
≥
0
{\displaystyle u_{i}(x)\geq 0}
,其中
i
=
1
,
…
,
m
.
{\displaystyle i=1,\ldots ,m.}
其中目標函數
L
(
x
,
u
)
{\displaystyle L(x,u)}
是如下定義的拉格朗日對偶函數:
L
(
x
,
u
)
=
f
(
x
)
+
∑
j
=
1
m
u
j
g
j
(
x
)
{\displaystyle L(x,u)=f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)}
^ 1.0 1.1 Rockafellar, R. Tyrrell . Convex Analysis. Princeton, NJ: Princeton University Press. 1997 [1970]. ISBN 978-0-691-01586-6 .
^ Borwein, Jonathan; Lewis, Adrian. Convex Analysis and Nonlinear Optimization: Theory and Examples 2. Springer. 2006: 76 –77. ISBN 978-0-387-29570-1 .
^ 5.0 5.1 Boţ, Radu Ioan; Wanka, Gert; Grad, Sorin-Mihai. Duality in Vector Optimization. Springer. 2009. ISBN 978-3-642-02885-4 .
^ Csetnek, Ernö Robert. Overcoming the failure of the classical generalized interior-point regularity conditions in convex optimization. Applications of the duality theory to enlargements of maximal monotone operators. Logos Verlag Berlin GmbH. 2010. ISBN 978-3-8325-2503-3 .
^ Borwein, Jonathan; Lewis, Adrian. Convex Analysis and Nonlinear Optimization: Theory and Examples 2. Springer. 2006. ISBN 978-0-387-29570-1 .
^ Boyd, Stephen; Vandenberghe, Lieven. Convex Optimization (PDF) . Cambridge University Press. 2004 [2011-10-03 ] . ISBN 978-0-521-83378-3 . (原始內容存檔 (PDF) 於2021-05-09).
^
X
=
{
0
}
{\displaystyle X=\{0\}}
則結論是直接的(平凡),所以假設不這樣(非平凡)。固定
x
∈
X
{\displaystyle x\in X}
,將f 換成範數,給出
∂
f
(
x
)
=
{
x
∗
∈
X
∗
:
⟨
x
∗
,
x
⟩
−
‖
x
‖
≥
⟨
x
∗
,
z
⟩
−
‖
z
‖
∀
z
∈
X
}
{\displaystyle \partial f(x)=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle -\|x\|\geq \left\langle x^{*},z\right\rangle -\|z\|\forall z\in X\right\}}
。若
x
∗
∈
∂
f
(
x
)
,
r
≥
0
{\displaystyle x^{*}\in \partial f(x),\ r\geq 0}
是實數,則
z
:=
r
x
{\displaystyle z:=rx}
給出
⟨
x
∗
,
x
⟩
−
‖
x
‖
≥
⟨
x
∗
,
r
x
⟩
−
‖
r
x
‖
=
r
[
⟨
x
∗
,
x
⟩
−
‖
x
‖
]
,
{\displaystyle \left\langle x^{*},x\right\rangle -\|x\|\geq \left\langle x^{*},rx\right\rangle -\|rx\|=r\left[\left\langle x^{*},x\right\rangle -\|x\|\right],}
特別地取
r
:=
2
{\displaystyle r:=2}
則有
x
∗
(
x
)
≥
‖
x
‖
{\displaystyle x^{*}(x)\geq \|x\|}
,而取
r
:=
1
2
{\displaystyle r:={\frac {1}{2}}}
則有
x
∗
(
x
)
≤
‖
x
‖
{\displaystyle x^{*}(x)\leq \|x\|}
於是
x
∗
(
x
)
=
‖
x
‖
{\displaystyle x^{*}(x)=\|x\|}
;若還
x
≠
0
{\displaystyle x\neq 0}
則因
x
∗
(
x
‖
x
‖
)
=
1
,
{\displaystyle x^{*}\left({\frac {x}{\|x\|}}\right)=1,}
由對偶範數 的定義可知
‖
x
∗
‖
≥
1.
{\displaystyle \left\|x^{*}\right\|\geq 1.}
由於
∂
f
(
x
)
⊆
{
x
∗
∈
X
∗
:
x
∗
(
x
)
=
‖
x
‖
}
,
{\displaystyle \partial f(x)\subseteq \left\{x^{*}\in X^{*}~:~x^{*}(x)=\|x\|\right\},}
其等價於
∂
f
(
x
)
=
∂
f
(
x
)
∩
{
x
∗
∈
X
∗
:
x
∗
(
x
)
=
‖
x
‖
}
,
{\displaystyle \partial f(x)=\partial f(x)\cap \left\{x^{*}\in X^{*}~:~x^{*}(x)=\|x\|\right\},}
可知
∂
f
(
x
)
=
{
x
∗
∈
X
∗
:
x
∗
(
x
)
=
‖
x
‖
and
‖
z
‖
≥
⟨
x
∗
,
z
⟩
for all
z
∈
X
}
,
{\displaystyle \partial f(x)=\left\{x^{*}\in X^{*}~:~x^{*}(x)=\|x\|{\text{ and }}\|z\|\geq \left\langle x^{*},z\right\rangle {\text{ for all }}z\in X\right\},}
於是
‖
x
∗
‖
≤
1
,
∀
x
∗
∈
∂
f
(
x
)
.
{\displaystyle \left\|x^{*}\right\|\leq 1,\ \forall x^{*}\in \partial f(x).}
從這些事實,可以得到結論。∎