凸分析 是研究凸函数 与凸集 性质的数学 分支，其应用称作凸优化 ，是最优化 理论的子分支。
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)
