凸分析

凸分析是研究凸函数与凸集性质的数学分支，其应用称作凸优化，是最优化理论的子分支。

3维凸多面体。凸分析不仅包括欧氏空间凸子集的研究，还包含抽象空间上凸函数的研究。

凸集

某向量空间X的子集 $C\subseteq X$ ，若满足下列任意一条等价条件，就称其是凸的（convex）：

若 $0\leq r\leq 1$ 是实数， $x,y\in C$ ，则 $rx+(1-r)y\in C.$ [1]
若 $0<r<1$ 是实数， $x,y\in C,\ x\neq y,$ 则 $rx+(1-r)y\in C.$

区间上的凸函数

$f:X\to [-\infty ,\infty ]$ 始终是以扩展实数线 $[-\infty ,\infty ]=\mathbb {R} \cup \{\pm \infty \}$ 为值域、以某向量空间的凸子集 $\operatorname {domain} f=X$ 为定义域的映射。映射 $f:X\to [-\infty ,\infty ]$ ，若

f(rx+(1-r)y)\leq rf(x)+(1-r)f(y)

（凸性

\leq

）

对所有实数 $0<r<1$ 、所有 $x,y\in X,\ x\neq y$ 都成立，称映射f是凸函数。若此不等式被替换为严格不等式

f(rx+(1-r)y)<rf(x)+(1-r)f(y)

（凸性

<

）

对f仍成立，则称f是严格凸的。[1] 凸函数与凸集有关。特别地，当且仅当函数f的上图（epigraph）

当且仅当函数（黑色）的上图（即函数图像上方区域，绿色）是凸集时，函数是凸的。

二元凸函数

x^{2}+xy+y^{2}

的图像

\operatorname {epi} f:=\left\{(x,r)\in X\times \mathbb {R} ~:~f(x)\leq r\right\}

是凸集时，函数f是凸的。[2]扩展实值函数的上图在凸分析中的作用类似于实值函数图像在实分析中的作用。特别地，扩展实值函数的上图提供了几何直觉，可用于形式化或证明猜想。

函数 $f:X\to [-\infty ,\infty ]$ 的定义域记作 $\operatorname {domain} f$ ，有效域则是集合[2]

\operatorname {dom} f:=\{x\in X~:~f(x)<\infty \}.

函数 $f:X\to [-\infty ,\infty ]$ ，当且仅当 $\forall x\in \operatorname {domain} f,\ f(x)>-\infty ,\ \operatorname {dom} f\neq \varnothing$ ，称函数是真凸函数。[2]这意味着在f的定义域中存在x使 $f(x)\in \mathbb {R}$ ，f也永远不等于 $f$ $-\infty$ 。换句话说，若函数的定义域非空、永远不取 $-\infty$ 、不等于 $+\infty$ ，则就是真凸函数。若 $f:\mathbb {R} ^{n}\to [-\infty ,\infty ]$ 是真凸函数，则存在向量 ${\vec {b}}\in \mathbb {R} ^{n}$ 、实数 $r\in \mathbb {R}$ 使得

\forall x,\ f(x)\geq x\cdot b-r

其中 $x\cdot b$ 表示向量的点积。

凸共轭

扩展实值函数 $f:X\to [-\infty ,\infty ]$ （不必凸）的凸共轭是来自X的（连续）对偶空间函数 $f^{*}:X^{*}\to [-\infty ,\infty ]$ [3]

f^{*}\left(x^{*}\right)=\sup _{z\in X}\left\{\left\langle x^{*},z\right\rangle -f(z)\right\}

其中，括号 $\left\langle \cdot ,\cdot \right\rangle$ 表示规范对偶性 ${\displaystyle \left\langle x^{*},z\right\rangle$ 。f的双共轭是映射 $f^{**}=\left(f^{*}\right)^{*}:X\to [-\infty ,\infty ]$ ，定义为 $\forall x\in X,\ f^{**}(x):=\sup _{z^{*}\in X^{*}}\left\{\left\langle x,z^{*}\right\rangle -f\left(z^{*}\right)\right\}$ 将X上的Y值函数记作 $\operatorname {Func} (X;Y)$ ，则 $f\mapsto f^{*}$ 定义的映射 $\operatorname {Func} (X;[-\infty ,\infty ])\to \operatorname {Func} \left(X^{*};[-\infty ,\infty ]\right)$ 乘坐勒让德-芬切尔变换。

次微分集与芬切尔-扬不等式

若 $x\in X,\ f:X\to [-\infty ,\infty ]$ ，则次微分集（subdifferential set）为

{\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=\|\cdot \|$ 是X上的范数这一重要特例中，可以证明[proof 1]

若 $0\neq x\in X$ ，则此定义可简化为：

\partial f(x)=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle =\|x\|{\text{ and }}\left\|x^{*}\right\|=1\right\}

；

\partial f(0)=\left\{x^{*}\in X^{*}~:~\left\|x^{*}\right\|\leq 1\right\}.

$\forall x\in X,\ x^{*}\in X^{*},\ f(x)+f^{*}\left(x^{*}\right)\geq \left\langle x^{*},x\right\rangle ,$ 这就是芬切尔-扬不等式，当且仅当 $x^{*}\in \partial f(x)$ 时是等式。正是通过这种方式，次微分集 $\partial f(x)$ 与凸共轭 $f^{*}\left(x^{*}\right)$ 直接相关。

双共轭

函数 $f:X\to [-\infty ,\infty ]$ 的双共轭是共轭的共轭，一般写作 $f^{**}:X\to [-\infty ,\infty ]$ 。双共轭有助于显示强对偶或弱对偶何时成立（通过扰动函数）。

$\forall x\in X,$ 不等式 $f^{**}(x)\leq f(x)$ 符合芬切尔-扬不等式。对紧合（proper）的函数，当且仅当f是凸的下半连续函数时， $f=f^{**}$ （芬切尔–莫罗定理）。[3][4]

凸最小化

凸最小化（主）问题形如

给定凸函数

f:X\to [-\infty ,\infty ]

与凸子集

M\subseteq X

，求

\inf _{x\in M}f(x)

对偶问题

优化理论中，对偶原则（duality principle）指出，优化问题可以从两个角度分别视作主问题与对偶问题。

一般来说，给定一对分离的局部凸空间 $\left(X,X^{*}\right)$ 、 $\left(Y,Y^{*}\right)$ ，以及函数 $f:X\to [-\infty ,\infty ]$ ，可以把主问题定义为求x使得

\inf _{x\in X}f(x).

可令 $f=f+I_{\mathrm {constraints} }$ （其中I是示性函数）将约束嵌入f。那么让 $F:X\times Y\to [-\infty ,\infty ]$ 是扰动函数，使得 $F(x,0)=f(x)$ 。[5]

关于所选扰动函数的对偶问题由下式给出：

\sup _{y^{*}\in Y^{*}}-F^{*}\left(0,y^{*}\right)

其中 $F^{*}$ 是F两个变量的凸共轭。

对偶间隙是不等式左右两式的差[6][5][7]

\sup _{y^{*}\in Y^{*}}-F^{*}\left(0,y^{*}\right)\leq \inf _{x\in X}F(x,0).

此原理同弱对偶。若两侧相等，则问题满足强对偶。强对偶成立的条件有很多，如

$F=F^{**}$ ，其中F是连接主问题与对偶问题的扰动函数， $F^{**}$ 是F的双共轭；
主问题是线性规划问题；
凸优化问题的斯莱特条件。[8][9]

拉格朗日对偶性

对不等式约束的凸最小化问题，

\min {}_{x}f(x)

subject to

g_{i}(x)\leq 0

，其中

i=1,\ldots ,m.

其拉格朗日对偶问题是

\sup {}_{u}\inf {}_{x}L(x,u)

subject to

u_{i}(x)\geq 0

，其中

i=1,\ldots ,m.

其中目标函数 $L(x,u)$ 是如下定义的拉格朗日对偶函数：

L(x,u)=f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)

另见

凸性 (经济学)
- 非凸 (经济学)

注释

Rockafellar, R. Tyrrell. . Princeton, NJ: Princeton University Press. 1997 [1970]. ISBN 978-0-691-01586-6.
Rockafellar & Wets 2009，第1-28頁.
Zălinescu 2002，第75-79頁.
Borwein, Jonathan; Lewis, Adrian. 2. Springer. 2006: 76–77. ISBN 978-0-387-29570-1.
Boţ, Radu Ioan; Wanka, Gert; Grad, Sorin-Mihai. . Springer. 2009. ISBN 978-3-642-02885-4.
Zălinescu 2002，第106-113頁.
Csetnek, Ernö Robert. . Logos Verlag Berlin GmbH. 2010. ISBN 978-3-8325-2503-3.
Borwein, Jonathan; Lewis, Adrian. 2. Springer. 2006. ISBN 978-0-387-29570-1.
Boyd, Stephen; Vandenberghe, Lieven. (PDF). Cambridge University Press. 2004 [2011-10-03]. ISBN 978-0-521-83378-3.

$X=\{0\}$ 则结论是直接的（平凡），所以假设不这样（非平凡）。固定 $x\in X$ ，将f换成范数，给出 $\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^{*}\in \partial f(x),\ r\geq 0$ 是实数，则 $z:=rx$ 给出 $\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$ 则有 $x^{*}(x)\geq \|x\|$ ，而取 $r:={\frac {1}{2}}$ 则有 $x^{*}(x)\leq \|x\|$ 于是 $x^{*}(x)=\|x\|$ ；若还 $x\neq 0$ 则因 $x^{*}\left({\frac {x}{\|x\|}}\right)=1,$ 由对偶范数的定义可知 $\left\|x^{*}\right\|\geq 1.$ 由于 $\partial f(x)\subseteq \left\{x^{*}\in X^{*}~:~x^{*}(x)=\|x\|\right\},$ 其等价于 $\partial f(x)=\partial f(x)\cap \left\{x^{*}\in X^{*}~:~x^{*}(x)=\|x\|\right\},$ 可知 $\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\},$ 于是 $\left\|x^{*}\right\|\leq 1,\ \forall x^{*}\in \partial f(x).$ 从这些事实，可以得到结论。∎

参考文献

[1]
[2]
Hiriart-Urruty, J.-B.; Lemaréchal, C. . Berlin: Springer-Verlag. 2001. ISBN 978-3-540-42205-1.
Kusraev, A.G.; Kutateladze, Semen Samsonovich. . Dordrecht: Kluwer Academic Publishers. 1995. ISBN 978-94-011-0265-0.
[3]
[4]
Singer, Ivan. . Canadian Mathematical Society series of monographs and advanced texts. New York: John Wiley & Sons, Inc. 1997: xxii+491. ISBN 0-471-16015-6. MR 1461544.
Stoer, J.; Witzgall, C. 1. Berlin: Springer. 1970. ISBN 978-0-387-04835-2.
[5]

外部链接

维基共享资源上的相關多媒體資源：凸分析

参考资料

Bauschke & Combettes 2017，第1-2頁.
Boyd & Vandenberghe 2004，第1-2頁.
Rockafellar & Wets 2009.
Rudin 1991.
Zălinescu 2002，第1-2頁.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[Rockafellar-1] Rockafellar, R. Tyrrell. . Princeton, NJ: Princeton University Press. 1997 [1970]. ISBN 978-0-691-01586-6.

[FOOTNOTERockafellarWets20091-28-2] Rockafellar & Wets 2009，第1-28頁.

[FOOTNOTEZălinescu200275-79-3] Zălinescu 2002，第75-79頁.

[BorweinLewis-5] Borwein, Jonathan; Lewis, Adrian. 2. Springer. 2006: 76–77. ISBN 978-0-387-29570-1.

[BWG-6] Boţ, Radu Ioan; Wanka, Gert; Grad, Sorin-Mihai. . Springer. 2009. ISBN 978-3-642-02885-4.

[FOOTNOTEZălinescu2002106-113-7] Zălinescu 2002，第106-113頁.

[Csetnek_2010-8] Csetnek, Ernö Robert. . Logos Verlag Berlin GmbH. 2010. ISBN 978-3-8325-2503-3.

[borwein-9] Borwein, Jonathan; Lewis, Adrian. 2. Springer. 2006. ISBN 978-0-387-29570-1.

[boyd-10] Boyd, Stephen; Vandenberghe, Lieven. (PDF). Cambridge University Press. 2004 [2011-10-03]. ISBN 978-0-521-83378-3.

[4] $X=\{0\}$ 则结论是直接的（平凡），所以假设不这样（非平凡）。固定 $x\in X$ ，将f换成范数，给出 $\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^{*}\in \partial f(x),\ r\geq 0$ 是实数，则 $z:=rx$ 给出 $\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$ 则有 $x^{*}(x)\geq \|x\|$ ，而取 $r:={\frac {1}{2}}$ 则有 $x^{*}(x)\leq \|x\|$ 于是 $x^{*}(x)=\|x\|$ ；若还 $x\neq 0$ 则因 $x^{*}\left({\frac {x}{\|x\|}}\right)=1,$ 由对偶范数的定义可知 $\left\|x^{*}\right\|\geq 1.$ 由于 $\partial f(x)\subseteq \left\{x^{*}\in X^{*}~:~x^{*}(x)=\|x\|\right\},$ 其等价于 $\partial f(x)=\partial f(x)\cap \left\{x^{*}\in X^{*}~:~x^{*}(x)=\|x\|\right\},$ 可知 $\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\},$ 于是 $\left\|x^{*}\right\|\leq 1,\ \forall x^{*}\in \partial f(x).$ 从这些事实，可以得到结论。∎

[FOOTNOTEBauschkeCombettes20171-2-11] Bauschke & Combettes 2017，第1-2頁.

[FOOTNOTEBoydVandenberghe20041-2-12] Boyd & Vandenberghe 2004，第1-2頁.

[FOOTNOTERockafellarWets2009-13] Rockafellar & Wets 2009.

[FOOTNOTERudin1991-14] Rudin 1991.

[FOOTNOTEZălinescu20021-2-15] Zălinescu 2002，第1-2頁.