凸分析

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

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

凸集

主条目：凸集

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

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

区间上的凸函数

主条目：凸函数

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

${\displaystyle f(rx+(1-r)y)\leq rf(x)+(1-r)f(y)}$（凸性${\displaystyle \leq }$）

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

${\displaystyle f(rx+(1-r)y)<rf(x)+(1-r)f(y)}$（凸性${\displaystyle <}$）

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

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

二元凸函数${\displaystyle x^{2}+xy+y^{2}}$的图像

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

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

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

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

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

${\displaystyle \forall x,\ f(x)\geq x\cdot b-r}$

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

凸共轭

主条目：凸共轭

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

${\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 }$表示规范对偶性${\displaystyle \left\langle x^{*},z\right\rangle :=x^{*}(z)}$。f的双共轭是映射${\displaystyle f^{**}=\left(f^{*}\right)^{*}:X\to [-\infty ,\infty ]}$，定义为${\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值函数记作${\displaystyle \operatorname {Func} (X;Y)}$，则${\displaystyle f\mapsto f^{*}}$定义的映射${\displaystyle \operatorname {Func} (X;[-\infty ,\infty ])\to \operatorname {Func} \left(X^{*};[-\infty ,\infty ]\right)}$乘坐勒让德-芬切尔变换。

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

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

${\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}}}$

例如，在${\displaystyle f=\|\cdot \|}$是X上的范数这一重要特例中，可以证明^{[proof 1]}

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

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

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

双共轭

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

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

凸最小化

主条目：凸最小化

凸最小化（主）问题形如

给定凸函数${\displaystyle f:X\to [-\infty ,\infty ]}$与凸子集${\displaystyle M\subseteq X}$，求${\displaystyle \inf _{x\in M}f(x)}$

对偶问题

主条目：对偶性 (最佳化)

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

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

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

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

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

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

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

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

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

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

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

拉格朗日对偶性

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

${\displaystyle \min {}_{x}f(x)}$ subject to ${\displaystyle g_{i}(x)\leq 0}$，其中${\displaystyle i=1,\ldots ,m.}$

其拉格朗日对偶问题是

${\displaystyle \sup {}_{u}\inf {}_{x}L(x,u)}$ subject to ${\displaystyle u_{i}(x)\geq 0}$，其中${\displaystyle i=1,\ldots ,m.}$

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

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

另见

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