凸分析 是研究凸函數 與凸集 性質的數學 分支，其應用稱作凸優化 ，是最優化 理論的子分支。
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 ]}
∂
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)}
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)}
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 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
^
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).}
參考文獻
編輯
外部連結
編輯
參考資料
編輯
![{\displaystyle f:X\to [-\infty ,\infty ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb5b80b60f448c0542dc59fd71f22b8ce01e8bc7)
![{\displaystyle [-\infty ,\infty ]=\mathbb {R} \cup \{\pm \infty \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f784980f597dae36b4d32c2a89de0a449e99aca8)
![{\displaystyle f:\mathbb {R} ^{n}\to [-\infty ,\infty ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3ef5a82ad74366531ce71d6fe571255b18f1d29a)
![{\displaystyle f^{*}:X^{*}\to [-\infty ,\infty ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e13a90d630d56ab231b9102f8c606db82843f54)
![{\displaystyle f^{**}=\left(f^{*}\right)^{*}:X\to [-\infty ,\infty ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3229c63ee01e8790a85b9f288eddca1b70746688)
![{\displaystyle \operatorname {Func} (X;[-\infty ,\infty ])\to \operatorname {Func} \left(X^{*};[-\infty ,\infty ]\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e960704508725beb4b9514813c473cbdf955b5a)
![{\displaystyle x\in X,\ f:X\to [-\infty ,\infty ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/280c918a431cf422d4510515aaf1fba0cf68b095)
![{\displaystyle f^{**}:X\to [-\infty ,\infty ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f75a283b8a505414ded658aca363cd399a95d9ef)
![{\displaystyle F:X\times Y\to [-\infty ,\infty ]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4be0d8959e1b20e3299c0b75df57a15d0b809378)
2. Springer. 2006: 76–77. ISBN 978-0-387-29570-1.
![{\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],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1204d83ef8154fa2d3b747047d2804e35743fab1)
