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).} 从这些事实,可以得到结论。∎ 基础概念 研究主题 映射 集合 主要成果 级数 对偶性 应用与相关