网站快速建设视频,还有用的网站,网站开发 强制兼容模式,创建app平台需要多少钱目录 1. 凸函数基本概念2.可微函数的凸性判定2.1 函数凸性的微分判据2.2 可微凸函数的例子 3. 保凸运算3.1 复合函数的凸性3.2 几种保凸运算 1. 凸函数基本概念 记 R ‾ : R ∪ { ∞ } . 对函数 f : R n → R ‾ , 称 记\overline{\mathbb{R}}:\mathbb{R}\cup\{\pm\infty\}.… 目录 1. 凸函数基本概念2.可微函数的凸性判定2.1 函数凸性的微分判据2.2 可微凸函数的例子 3. 保凸运算3.1 复合函数的凸性3.2 几种保凸运算 1. 凸函数基本概念 记 R ‾ : R ∪ { ± ∞ } . 对函数 f : R n → R ‾ , 称 记\overline{\mathbb{R}}:\mathbb{R}\cup\{\pm\infty\}.\text{ 对函数 }f:\mathbb{R}^n\to\overline{\mathbb{R}},称 记R:R∪{±∞}. 对函数 f:Rn→R,称 d o m ( f ) : { x ∈ R n ∣ f ( x ) ∞ } \mathbf{dom}(f):\{x\in\mathbb{R}^n|f(x)\infty\} dom(f):{x∈Rn∣f(x)∞}为 f f f的有效定义域. 若 f ( x ) − ∞ ( ∀ x ∈ R n ) 且 dom ( f ) ≠ ∅ , 则称 f 是真的 (proper) . \text{若 }f(x)-\infty\text{ (}\forall x\in\mathbb{R}^n)\text{ 且 dom}(f)\neq\emptyset,\text{ 则称 }f\text{ 是真的 (proper)}. 若 f(x)−∞ (∀x∈Rn) 且 dom(f)∅, 则称 f 是真的 (proper).
定义 1.1凸函数称函数 f : R n → R ‾ f:\mathbb{R}^n\to\overline{\mathbb{R}} f:Rn→R是一个凸函数如果对于任意的 x , y ∈ d o m ( f ) x,y \in \mathbf{dom}(f) x,y∈dom(f)和 θ ∈ [ 0 , 1 ] \theta\in[0,1] θ∈[0,1]有 θ x ( 1 − θ ) y ∈ d o m ( f ) \theta x (1-\theta )y \in \mathbf{dom}(f) θx(1−θ)y∈dom(f)且有 f ( θ x ( 1 − θ ) y ) ≤ θ f ( x ) ( 1 − θ ) f ( y ) . f(\theta x(1-\theta)y)\leq\theta f(x)(1-\theta)f(y). f(θx(1−θ)y)≤θf(x)(1−θ)f(y).
当不等号对任意 x , y ∈ d o m ( f ) , x ≠ y x,y\in\mathbf{dom}(f),\quad x\neq y x,y∈dom(f),xy 和 0 θ 1 0\theta1 0θ1 严格成立时我们称 f f f 是严格凸的.若 − f -f −f 是凸的 (或严格凸的), 则称 f f f 是凹的 (或严格凹的).
定义 1.2函数的水平集 设 α ∈ R , 函数 f : R n → R ‾ 的 α -水平集定义为 \text{设 }\alpha\in\mathbb{R},\text{ 函数 }f:\mathbb{R}^n\to\overline{\mathbb{R}}\text{ 的 }\alpha\text{-水平集定义为} 设 α∈R, 函数 f:Rn→R 的 α-水平集定义为: l e v α ( f ) : { x ∈ R n ∣ f ( x ) ≤ α } . \mathbf{lev}_\alpha(f):\{x\in\mathbb{R}^n|f(x)\leq\alpha\}. levα(f):{x∈Rn∣f(x)≤α}.
命题 1.1凸函数的水平集是凸集 若函数 f : R n → R ‾ 是凸的, 则 ∀ α ∈ R , 其 α − 水平集 l e v α ( f ) 是凸集 \text{若函数 }f:\mathbb{R}^n\to\overline{\mathbb{R}}\text{ 是凸的, 则 }\forall\alpha\in\mathbb{R}, 其 α-水平集\mathbf{lev}_\alpha(f)是凸集 若函数 f:Rn→R 是凸的, 则 ∀α∈R,其α−水平集levα(f)是凸集
证 对任意的 α ∈ R . 根据 f 的凸性可知: ∀ x , y ∈ l e v α ( f ) , 有 x , y ∈ 有效域 d o m ( f ) , 从而 \text{对任意的 }\alpha\in\mathbb{R}.\text{ 根据 }f\text{的凸性可知: }\forall x,y\in\mathbf{lev}_\alpha(f),\text{有 }x,y\in有效域\mathbf{dom}(f),\text{从而} 对任意的 α∈R. 根据 f的凸性可知: ∀x,y∈levα(f),有 x,y∈有效域dom(f),从而 f ( θ x ( 1 − θ ) y ) ≤ 由凸函数的定义 θ f ( x ) ( 1 − θ ) f ( y ) ≤ θ α ( 1 − θ ) α α . f(\theta x(1-\theta)y)\leq由凸函数的定义\theta f(x)(1-\theta)f(y)\leq\theta\alpha(1-\theta)\alpha\alpha. f(θx(1−θ)y)≤由凸函数的定义θf(x)(1−θ)f(y)≤θα(1−θ)αα. 所以, θ x ( 1 − θ ) y ∈ lev α ( f ) . 即 lev α ( f ) 是凸集 . \text{所以,}\theta x(1-\theta)y\in\textbf{lev}_\alpha(f).\text{即 lev}_\alpha(f)\text{ 是凸集}. 所以,θx(1−θ)y∈levα(f).即 levα(f) 是凸集.
注命题 1.1 的逆命题不成立。一个函数的水平集是凸集不能够推出这个函数是凸函数。
此外函数的凸性可以通过集合的凸性来刻画。
定义 1.3上镜图(epigraph)对于函数 f : R n → R ‾ f:\mathbb{R}^n\to\overline{\mathbb{R}} f:Rn→R我们称 R n 1 \mathbb{R}^{n1} Rn1中集合 e p i ( f ) : { ( x , t ) ∈ R n × R ∣ f ( x ) ≤ t } \mathbf{epi}(f):\{(x,t)\in\mathbb{R}^n\times\mathbb{R}|f(x)\leq t\} epi(f):{(x,t)∈Rn×R∣f(x)≤t}为 f f f的上镜图。
命题 1.2函数凸性的上镜图刻画 函数 f : R n → R ‾ f:\mathbb{R}^n\to\overline{\mathbb{R}} f:Rn→R是凸函数当且仅当 e p i ( f ) \mathbf{epi}(f) epi(f)是凸集.
证对任意的 ( x , t ) , ( y , s ) ∈ e p i ( f ) (x,t),(y,s)\in\mathbf{epi}(f) (x,t),(y,s)∈epi(f) 和 θ ∈ [ 0 , 1 ] \theta\in[0,1] θ∈[0,1]利用不等式的传递性有 θ ( x , t ) ( 1 − θ ) ( y , s ) ∈ e p i ( f ) ⟺ f ( θ x ( 1 − θ ) y ) ≤ θ t ( 1 − θ ) s . \theta(x,t)(1-\theta)(y,s)\in\mathbf{epi}(f)\iff f(\theta x(1-\theta)y)\leq\theta t(1-\theta)s. θ(x,t)(1−θ)(y,s)∈epi(f)⟺f(θx(1−θ)y)≤θt(1−θ)s.由此式可以证明函数 f : R n → R ‾ f:\mathbb{R}^n\to\overline{\mathbb{R}} f:Rn→R是凸函数当且仅当 e p i ( f ) \mathbf{epi}(f) epi(f)是凸集.
2.可微函数的凸性判定
2.1 函数凸性的微分判据
命题 2.1(一阶微分判据) 对函数 f : R n → R ∪ { ∞ } , 若 d o m ( f ) 是一个凸集,且 f 在有效域 d o m ( f ) 上处处可微 , 则 f 是凸函数当且仅当 : \text{对函数 }f:\mathbb{R}^n\to\mathbb{R}\cup\{\infty\},若\mathrm{dom}(f)\text{ 是一个凸集,且}f在有效域\mathrm{dom}(f)\text{ 上处处可微},\text{则 }f\text{ 是凸函数当且仅当}: 对函数 f:Rn→R∪{∞},若dom(f) 是一个凸集,且f在有效域dom(f) 上处处可微,则 f 是凸函数当且仅当: f ( y ) ≥ f ( x ) ∇ f ( x ) T ( y − x ) , ∀ x , y ∈ d o m ( f ) . ( 1 ) f(y)\geq f(x)\nabla f(x)^T(y-x),\quad\forall x,y\in\mathbf{dom}(f).\quad(1) f(y)≥f(x)∇f(x)T(y−x),∀x,y∈dom(f).(1) 证 充分性 . 设 ( 1 ) 式成立 充分性.设(1)式成立 充分性.设(1)式成立 ∀ x , y ∈ d o m ( f ) , θ ∈ ( 0 , 1 ) , 记 z θ y ( 1 − θ ) x . \forall x,y\in\mathbf{dom}(f),\theta\in(0,1),\text{ 记 }z\theta y(1-\theta)x. ∀x,y∈dom(f),θ∈(0,1), 记 zθy(1−θ)x. 由于有效域是凸集 , 那么 z ∈ d o m ( f ) 由于有效域是凸集,\text{那么}z\in \mathbf{dom}( f) 由于有效域是凸集,那么z∈dom(f) 且 f ( y ) ≥ f ( z ) ∇ f ( z ) T ( y − z ) , f ( x ) ≥ f ( z ) ∇ f ( z ) T ( x − z ) . f(y)\geq f(z)\nabla f(z)^T(y-z),\quad f(x)\geq f(z)\nabla f(z)^T(x-z). f(y)≥f(z)∇f(z)T(y−z),f(x)≥f(z)∇f(z)T(x−z).于是 θ f ( y ) ( 1 − θ ) f ( x ) ≥ f ( z ) ∇ f ( z ) T [ θ ( y − z ) ( 1 − θ ) ( x − z ) ] f ( z ) . \begin{aligned}\theta f(y)(1-\theta)f(x)\geq f(z)\nabla f(z)^T[\theta(y-z)(1-\theta)(x-z)]f(z).\end{aligned} θf(y)(1−θ)f(x)≥f(z)∇f(z)T[θ(y−z)(1−θ)(x−z)]f(z). 所以 f 是凸函数 所以f是凸函数 所以f是凸函数 必要性 必要性 必要性. 设 f 是凸函数那么 ∀ x , y ∈ d o m ( f ) , θ ∈ ( 0 , 1 ) , 有 设f是凸函数那么\forall x,y\in\mathbf{dom}(f),\:\theta\in(0,1), 有 设f是凸函数那么∀x,y∈dom(f),θ∈(0,1),有 f ( θ y ( 1 − θ ) x ) ≤ θ f ( y ) ( 1 − θ ) f ( x ) f ( x ) θ [ f ( y ) − f ( x ) ] . f(\theta y(1-\theta)x)\leq\theta f(y)(1-\theta)f(x)f(x)\theta[f(y)-f(x)]. f(θy(1−θ)x)≤θf(y)(1−θ)f(x)f(x)θ[f(y)−f(x)]. 由泰勒公式 由泰勒公式 由泰勒公式 f ( θ y ( 1 − θ ) x ) f ( x ) θ ∇ f ( x ) T ( y − x ) o ( θ ) . f(\theta y(1-\theta)x)f(x)\theta\nabla f(x)^T(y-x)o(\theta). f(θy(1−θ)x)f(x)θ∇f(x)T(y−x)o(θ). 所以有 所以有 所以有 ∇ f ( x ) T ( y − x ) o ( θ ) θ ≤ f ( y ) − f ( x ) . \nabla f(x)^T(y-x)\frac{o(\theta)}{\theta}\leq f(y)-f(x). ∇f(x)T(y−x)θo(θ)≤f(y)−f(x). 令 令 令 θ → 0 \theta\to0 θ→0, 得 得 得 ∇ f ( x ) T ( y − x ) ≤ f ( y ) − f ( x ) \nabla f(x)^T(y-x)\leq f(y)-f(x) ∇f(x)T(y−x)≤f(y)−f(x). 即 ( 1 ) 成立 . 即(1)成立. 即(1)成立.
由此命题可以知道可微函数是凸函数当且仅当其图形总是在其切平面的上方.
命题 2.2 (二阶微分判据) 对 函数 f : R n → R ∪ { ∞ } , 若 d o m ( f ) 是一个凸集且 f 在 dom ( f ) 上二阶连续可微那么 ( 1 ) 是凸函数当且仅当对任意 x ∈ d o m ( f ) , ∇ 2 f ( x ) 是半正定的 ( 2 ) 若 ∇ 2 f ( x ) 是正定的则 f 是严格凸函数 . \begin{aligned}对函数f:\mathbb{R}^n\to\mathbb{R}\cup\{\infty\},若 dom(f)是一个凸集且f在\operatorname{dom}(f)上二阶连续可微那么\\ (1) 是凸函数当且仅当对任意x\in \mathbf{dom}(f) , \nabla^2 f(x)是半正定的\\ (2) 若\nabla^2f(x)是正定的则f是严格凸函数.\end{aligned} 对函数f:Rn→R∪{∞},若dom(f)是一个凸集且f在dom(f)上二阶连续可微那么(1)是凸函数当且仅当对任意x∈dom(f),∇2f(x)是半正定的(2)若∇2f(x)是正定的则f是严格凸函数.
证先证明(1)
必要性 设 f f f是凸函数则 ∀ x ∈ d o m ( f ) , h ∈ R n \forall x\in\mathbf{dom}(f),~h\in\mathbb{R}^n ∀x∈dom(f), h∈Rn 以及充分小的 θ ∈ ( 0 , 1 ) \theta\in(0,1) θ∈(0,1) 利用泰勒公式有 f ( x θ h ) f ( x ) θ ∇ f ( x ) T h 1 2 θ 2 h T ∇ 2 f ( x ) h o ( θ 2 ) . f(x\theta h)f(x)\theta\nabla f(x)^Th\frac{1}{2}\theta^2h^T\nabla^2f(x)ho(\theta^2). f(xθh)f(x)θ∇f(x)Th21θ2hT∇2f(x)ho(θ2).利用命题 2.1(一阶微分判据), 得 1 2 θ 2 h T ∇ 2 f ( x ) h o ( θ 2 ) ≥ 0. \frac{1}{2}\theta^{2}h^{T}\nabla^{2}f(x)ho(\theta^{2})\geq0. 21θ2hT∇2f(x)ho(θ2)≥0.两边除以 θ 2 \theta^2 θ2 并令 θ → 0 \theta\to0 θ→0,便得 h T ∇ 2 f ( x ) h ≥ 0 h^T\nabla^2f(x)h\geq0 hT∇2f(x)h≥0.由 h ∈ R n h\in\mathbb{R}^n h∈Rn 的任意性即知 ∇ 2 f ( x ) \nabla^2f(x) ∇2f(x) 是半正定的.
充分性 设对任意 x ∈ d o m ( f ) , ∇ 2 f ( x ) x\in\mathbf{dom}(f),\nabla^2f(x) x∈dom(f),∇2f(x) 是半正定的. ∀ x , y ∈ d o m ( f ) , x ≠ y \forall x,y\in\mathbf{dom}(f),\:x\neq y ∀x,y∈dom(f),xy,则存在 ξ ( 1 − θ ) x θ y ∈ d o m ( f ) \xi(1-\theta)x\theta y\in\mathbf{dom}(f) ξ(1−θ)xθy∈dom(f),其中 θ ∈ ( 0 , 1 ) \theta\in(0,1) θ∈(0,1), 使得 f ( y ) f ( x ) ∇ f ( x ) T ( y − x ) 1 2 ( y − x ) T ∇ 2 f ( ξ ) ( y − x ) . f(y)f(x)\nabla f(x)^T(y-x)\frac{1}{2}(y-x)^T\nabla^2f(\xi)(y-x). f(y)f(x)∇f(x)T(y−x)21(y−x)T∇2f(ξ)(y−x).将 y − x ( 1 − θ ) − 1 ( y − ξ ) y-x(1-\theta)^{-1}(y-\xi) y−x(1−θ)−1(y−ξ) 代入上式最后一项并利用 ∇ 2 f ( x ) \nabla^2f(x) ∇2f(x) 的半正定性得 f ( y ) ≥ f(y)\geq f(y)≥ f ( x ) ∇ f ( x ) T ( y − x ) f(x)\nabla f(x)^T(y-x) f(x)∇f(x)T(y−x).据命题 2.1(一阶微分判据)可知 f f f 是凸函数.
下面证明(2)
若 ∇ 2 f ( x ) \nabla^2f(x) ∇2f(x) 是正定的那么对互异的 x , y ∈ d o m ( f ) x,y\in\mathbf{dom}(f) x,y∈dom(f),根据泰勒公式有 f ( y ) f ( x ) ∇ f ( x ) T ( y − f(y)f(x)\nabla f(x)^T(y- f(y)f(x)∇f(x)T(y− x ) x) x).余项中带有 ∇ 2 f ( x ) \nabla^2f(x) ∇2f(x)且是二次项。因为 ∇ 2 f ( x ) \nabla^2f(x) ∇2f(x)正定那么余项一定大于0因而 f f f 是严格凸函数.
注 严格凸函数不一定 ∇ 2 f ( x ) \nabla^2f(x) ∇2f(x) 在 dom$( f) $ 上恒为正定的. 例如在一维函数情形 f ( x ) x 4 f(x)x^4 f(x)x4 在 R \mathbb{R} R 上严格凸但其二阶导数不恒为正.
2.2 可微凸函数的例子
例 (多元凸函数) 如下函数 f : R n → R ∪ { ∞ } f:\mathbb{R}^n\to\mathbb{R}\cup\{\infty\} f:Rn→R∪{∞} 均为凸函数
(1) 仿射函数 f ( x ) a T x b , a ∈ R n , b ∈ R . f(x)a^Txb,\:a\in\mathbb{R}^n,b\in\mathbb{R}. f(x)aTxb,a∈Rn,b∈R.
(2) 二次函数 f ( x ) : 1 2 x T A x b T x c , A ∈ S n , b ∈ R n , c ∈ R f(x):\frac12x^TAxb^Txc,\quad A\in\mathbb{S}_^n,\quad b\in\mathbb{R}^n,\quad c\in\mathbb{R} f(x):21xTAxbTxc,A∈Sn,b∈Rn,c∈R. 特别地当 A ∈ S ⊢ n A\in\mathbb{S}_{\vdash}^n A∈S⊢n时 f f f 是严格凸函数.
(3) 二次线性分式 f ( x , y ) : x 2 / y , d o m ( f ) : R × R . f(x,y):x^2/y,\:\mathbf{dom}(f):\mathbb{R}\times\mathbb{R}_{}. f(x,y):x2/y,dom(f):R×R.
(4) 指数对数函数 f ( x ) : ln ( ∑ i 1 n e x i ) f(x):\ln(\sum_{i1}^ne^{x_i}) f(x):ln(∑i1nexi),其中 x i x_i xi 是 x x x 的第 i i i 个分量.
(5) 负对数指数函数 f ( x ) : − exp ( 1 n ∑ i 1 n ln x i ) , f( x) : - \exp \left ( \frac 1n\sum _{i 1}^n\ln x_i\right ) , f(x):−exp(n1∑i1nlnxi), d o m ( f ) \mathbf{dom}(f) dom(f) : R n . \mathbb{R} _{ }^n. Rn.
注(5)中的函数可以化为 f ( x ) − exp ( 1 n ∑ i 1 n ln x i ) − ( ∏ i 1 n x i ) 1 / n , dom ( f ) : R n . f(x)-\exp\Big(\frac{1}{n}\sum_{i1}^{n}\ln x_i\Big)-\big(\prod_{i1}^{n}x_i\big)^{1/n},\quad\text{dom}(f):\mathbb{R}_{}^{n}. f(x)−exp(n1i1∑nlnxi)−(i1∏nxi)1/n,dom(f):Rn.所以此函数又称为负几何平均函数.
3. 保凸运算
3.1 复合函数的凸性
命题 3.1.1设 h : R m → R ‾ h:\mathbb{R}^m\to\overline{\mathbb{R}} h:Rm→R 是一个凸函数对 i 1 , ⋯ , m , g i : C i → R i1,\cdots,m,g_i:C_i\to\mathbb{R} i1,⋯,m,gi:Ci→R 是凸函数或凹函数其中 C i ⊂ R n C_i\subset\mathbb{R}^n Ci⊂Rn,满足条件 ( 1 ) g i (1)g_i (1)gi 是凸函数时 h h h 关于第 i i i 个变元 x i x_i xi 在 R 上递增 或 ( 2 ) g i (2)g_i (2)gi 是凹函数时 h h h 关于第 i i i 个变元 x i x_i xi 在 R 上递减
记 g ( x ) : ( g 1 ( x ) , ⋯ , g m ( x ) ) T . g(x):(g_1(x),\cdots,g_m(x))^T. g(x):(g1(x),⋯,gm(x))T.那么复合函数 f h ∘ g , dom ( f ) : { x ∈ ⋂ i 1 m C i ∣ h ( g ( x ) ) ∞ } , fh\circ g,\quad\textbf{dom}(f):\Big\{x\in\bigcap\limits_{i1}^mC_i\Big|h(g(x))\infty\Big\}, fh∘g,dom(f):{x∈i1⋂mCi h(g(x))∞},也是凸函数.
证根据凸函数的定义以及 h h h的凸性可以得到 C 1 , . . . , C m C_1,...,C_m C1,...,Cm 以及 d o m ( h ) \mathbf{dom}(h) dom(h) 均为凸集. 设 x , y ∈ d o m ( f ) , θ ∈ [ 0 , 1 ] x,y\in\mathbf{dom}(f),\theta\in[0,1] x,y∈dom(f),θ∈[0,1],我们有 θ x ( 1 − θ ) y ∈ ⋂ i 1 m C i \theta x(1-\theta)y\in\bigcap_{i1}^mC_i θx(1−θ)y∈⋂i1mCi, 且 θ g ( x ) ( 1 − θ ) g ( y ) ∈ d o m ( h ) \theta g(x)(1-\theta)g(y)\in\mathbf{dom}(h) θg(x)(1−θ)g(y)∈dom(h). 这里是因为 g ( ⋅ ) 的值域是 h ( ⋅ ) 的定义域且 h 是凸的 这里是因为g(·)的值域是h(·)的定义域且h是凸的 这里是因为g(⋅)的值域是h(⋅)的定义域且h是凸的记 u : g ( θ x ( 1 − θ ) y ) , v : θ g ( x ) ( 1 − θ ) g ( y ) . \begin{aligned}u:g(\theta x(1-\theta)y),\quad v:\theta g(x)(1-\theta)g(y).\end{aligned} u:g(θx(1−θ)y),v:θg(x)(1−θ)g(y).对于 i 1 i 1 i1 ( a ) \mathrm{( a) } (a) 当条件 (1) 成立时 g 1 g_1 g1 是凸的故 u 1 ≤ v 1 u_1\leq v_1 u1≤v1. 由于 h ( x ) h(x) h(x) 关于第一个变元 x 1 x_1 x1 是递增的所以 f ( θ x ( 1 − θ ) y ) h ( u 1 , u 2 , ⋯ , u m ) ≤ h ( v 1 , u 2 , ⋯ , u m ) . \begin{aligned}f(\theta x(1-\theta)y)h(u_1,u_2,\cdots,u_m)\le h(v_1,u_2,\cdots,u_m).\end{aligned} f(θx(1−θ)y)h(u1,u2,⋯,um)≤h(v1,u2,⋯,um). ( b ) \mathrm{(b) } (b) 当条件 (2) 成立时 g 1 g_1 g1 是凹的故 u 1 ≥ v 1 u_1\geq v_1 u1≥v1. 由于 h ( x ) h(x) h(x) 关于第一个变元 x 1 x_{1} x1 是递减的所以有 f ( θ x ( 1 − θ ) y ) h ( u 1 , u 2 , ⋯ , u m ) ≤ h ( v 1 , u 2 , ⋯ , u m ) . \begin{aligned}f(\theta x(1-\theta)y)h(u_1,u_2,\cdots,u_m)\leq h(v_1,u_2,\cdots,u_m).\end{aligned} f(θx(1−θ)y)h(u1,u2,⋯,um)≤h(v1,u2,⋯,um).总之有 h ( u 1 , u 2 , ⋯ , u m ) ≤ h ( v 1 , u 2 , ⋯ , u m ) h(u_1,u_2,\cdots,u_m)\leq h(v_1,u_2,\cdots,u_m) h(u1,u2,⋯,um)≤h(v1,u2,⋯,um). 依次对变元 u 2 , ⋯ , u n u_2,\cdots,u_n u2,⋯,un 做同样的推导最终我们得到 f ( θ x ( 1 − θ ) y ) h ( u 1 , u 2 , ⋯ , u m ) ≤ h ( v 1 , v 2 , ⋯ , v m ) h ( θ g ( x ) ( 1 − θ ) g ( y ) ) \begin{aligned}f(\theta x(1-\theta)y)h(u_1,u_2,\cdots,u_m)\le h(v_1,v_2,\cdots,v_m)h(\theta g(x)(1-\theta)g(y))\end{aligned} f(θx(1−θ)y)h(u1,u2,⋯,um)≤h(v1,v2,⋯,vm)h(θg(x)(1−θ)g(y))利用 h h h的凸性可以得到 f ( θ x ( 1 − θ ) y ) ≤ θ h ( g ( x ) ) ( 1 − θ ) h ( g ( y ) ) θ f ( x ) ( 1 − θ ) f ( y ) . f(\theta x(1-\theta)y)\leq\theta h(g(x))(1-\theta)h(g(y))\theta f(x)(1-\theta)f(y). f(θx(1−θ)y)≤θh(g(x))(1−θ)h(g(y))θf(x)(1−θ)f(y).所以 f f f 是凸函数.
注 上述证明中我们用到了 h h h 在如下点列 u ( u 1 , ⋯ , u m ) T → ( v 1 , u 2 , ⋯ , u m ) T → ⋯ → ( v 1 , ⋯ , v m − 1 , u m ) T → v u(u_1,\cdots,u_m)^T\to(v_1,u_2,\cdots,u_m)^T\to\cdots\to(v_1,\cdots,v_{m-1},u_m)^T\to v u(u1,⋯,um)T→(v1,u2,⋯,um)T→⋯→(v1,⋯,vm−1,um)T→v的值其中除了 v ∈ d o m ( h ) v \in\mathbf{dom}(h) v∈dom(h),我们并不知道其他的点是否属于 d o m ( h ) \mathbf{dom}(h) dom(h).所以我们需要假定 h h h 关于每一个单变量在 R \mathbb{R} R上的单调性即使这样的点不在 d o m ( h ) \mathbf{dom}(h) dom(h)中.
例 3.1.1(凹函数的对数与倒数)设 g : C → R g:C\to\mathbb{R} g:C→R是凸函数其中 C ⊂ R n C\subset\mathbb{R}^n C⊂Rn则有 f ( x ) : − ln g ( x ) , d o m ( f ) : { x ∈ C ∣ g ( x ) 0 } 和 f ( x ) : 1 / g ( x ) , d o m ( f ) : { x ∈ C ∣ g ( x ) 0 } 均为凸函数 f(x):-\ln g(x),\quad\mathbf{dom}(f):\{x\in C|g(x)0\}\\和f(x):1/g(x),\quad\mathbf{dom}(f):\{x\in C|g(x)0\}均为凸函数 f(x):−lng(x),dom(f):{x∈C∣g(x)0}和f(x):1/g(x),dom(f):{x∈C∣g(x)0}均为凸函数
证由于 h ( u ) : − ln u h(u):-\ln u h(u):−lnu 是凸函数且关于 u u u递减而 g g g是凹函数根据命题 3.3.1可知 h ∘ g h\circ g h∘g 是凸函数即 − ln g ( x ) -\ln g(x) −lng(x)是凸函数.
类似地因为 h ( u ) : 1 / u , d o m ( h ) : R h(u):1/u,\quad\mathbf{dom}(h):\mathbb{R}_ h(u):1/u,dom(h):R 是凸函数关于 u u u 递减而 g g g 是凹函数 所以 f ( x ) : h ( g ( x ) ) 1 / g ( x ) f(x):h(g(x))1/g(x) f(x):h(g(x))1/g(x) 是凸函数.
注 对恒为正的凸函数 g g g,不能保证 ln g \ln g lng 和 1 / g 1/g 1/g 仍为凹或凸的函数. 例如 g 1 ( x ) x g_1(x)x g1(x)x和 g 2 ( x ) 1 / x g_2(x)1/\sqrt{x} g2(x)1/x 均是凸函数而 1 / g 1 1/g_1 1/g1 和 1 / g 2 1/g_2 1/g2却一个是凸函数另一个是凹的. ln g 1 \ln g_1 lng1 和 ln g 2 \ln g_2 lng2 亦然.
3.2 几种保凸运算
下面给出几个命题其中几个命题没有给出证明感兴趣的读者可以自行证明。
命题 3.2.1(求和的保凸性) 设 f i : R n → R ∪ { ∞ } , i 1 , ⋯ , m f_i:\mathbb{R}^n\to\mathbb{R}\cup\{\infty\},\quad i1,\cdots,m fi:Rn→R∪{∞},i1,⋯,m,均为凸函数那么 f ( x ) : f 1 ( x ) . . . f m ( x ) , ∀ x ∈ R n , f(x):f_1(x)...f_m(x),\quad\forall x\in\mathbb{R}^n, f(x):f1(x)...fm(x),∀x∈Rn,和 h ( X ) : f 1 ( x 1 ) . . . f m ( x m ) , X : ( x 1 , . . . , x m ) ∈ R m n , h(X):f_1(x_1)...f_m(x_m),\quad X:(x_1,...,x_m)\in\mathbb{R}^{mn}, h(X):f1(x1)...fm(xm),X:(x1,...,xm)∈Rmn,都是凸函数其有效定义域分别是 d o m ( f ) ⋂ i 1 m d o m ( f i ) , d o m ( h ) d o m ( f 1 ) × ⋯ × d o m ( f m ) . \mathbf{dom}(f)\bigcap_{i1}^m\mathbf{dom}(f_i),\quad\mathbf{dom}(h)\mathbf{dom}(f_1)\times\cdots\times\mathbf{dom}(f_m). dom(f)i1⋂mdom(fi),dom(h)dom(f1)×⋯×dom(fm).
命题 3.2.2(与仿射变换复合) 设 f : R n → R ‾ f:\mathbb{R}^n\to\overline{\mathbb{R}} f:Rn→R 为凸函数 A ∈ R m × n , b ∈ R m A\in\mathbb{R}^{m\times n},\quad b\in\mathbb{R}^m A∈Rm×n,b∈Rm, 那么 g ( x ) : f ( A x b ) g(x):f(Axb) g(x):f(Axb) 是凸函数.
命题 3.2.3(凸函数族的逐点上确界) 设 f γ : R n → R ‾ , γ ∈ Γ ≠ ∅ f_\gamma:\mathbb{R}^n\to\overline{\mathbb{R}},\quad\gamma\in\Gamma\neq\emptyset fγ:Rn→R,γ∈Γ∅,是一族凸函数则 f ( x ) : sup γ ∈ Γ f γ ( x ) , x ∈ R n , f(x):\sup_{\gamma\in\Gamma}f_\gamma(x),\quad x\in\mathbb{R}^n, f(x):γ∈Γsupfγ(x),x∈Rn,也是凸函数.
证 容易证明 f sup γ ∈ Γ f γ ⟺ e p i ( f ) ⋂ γ ∈ Γ e p i ( f γ ) . f\sup_{\gamma\in\Gamma}f_\gamma\iff\mathbf{epi}(f)\bigcap_{\gamma\in\Gamma}\mathbf{epi}(f_\gamma). fγ∈Γsupfγ⟺epi(f)γ∈Γ⋂epi(fγ).所以 f f f 也是凸函数.
命题 3.2.4 (凸函数关于部分变量的下确界) 设 f : R n × R m → R ‾ f:\mathbb{R}^n\times\mathbb{R}^m\to\overline{\mathbb{R}} f:Rn×Rm→R 是一个凸函数 C ⊂ C\subset C⊂ R m \mathbb{R}^m Rm 是非空凸集则 g ( x ) : inf y ∈ C f ( x , y ) g(x):\inf_{y\in C}f(x,y) g(x):y∈Cinff(x,y)是一个凸函数.
证.易见 g g g 的有效定义域为 d o m ( g ) : { x ∣ \mathbf{dom}(g):\{x| dom(g):{x∣存在 y ∈ C y\in C y∈C, 使得 ( x , y ) ∈ d o m ( f ) } . (x,y)\in\mathbf{dom}(f)\}. (x,y)∈dom(f)}.
对任意的 x 1 , x 2 ∈ d o m ( g ) , θ ∈ [ 0 , 1 ] , ∀ y 1 , y 2 ∈ C x_1,x_2\in\mathbf{dom}(g),\theta\in[0,1],\:\forall y_1,y_2\in C x1,x2∈dom(g),θ∈[0,1],∀y1,y2∈C, 记 x θ : θ x 1 ( 1 − θ ) x 2 , y θ : θ y 1 ( 1 − θ ) y 2 . \begin{aligned}x_\theta:\theta x_1(1-\theta)x_2,\quad y_\theta:\theta y_1(1-\theta)y_2.\end{aligned} xθ:θx1(1−θ)x2,yθ:θy1(1−θ)y2.则 y θ ∈ C y_\theta\in C yθ∈C 且 ( x θ , y θ ) θ ( x 1 , y 1 ) ( 1 − θ ) ( x 2 , y 2 ) (x_\theta,y_\theta)\theta(x_1,y_1)(1-\theta)(x_2,y_2) (xθ,yθ)θ(x1,y1)(1−θ)(x2,y2).于是 g ( x θ ) ≤ f ( x θ , y θ ) ≤ θ f ( x 1 , y 1 ) ( 1 − θ ) f ( x 2 , y 2 ) . g(x_\theta)\leq f(x_\theta,y_\theta)\leq\theta f(x_1,y_1)(1-\theta)f(x_2,y_2). g(xθ)≤f(xθ,yθ)≤θf(x1,y1)(1−θ)f(x2,y2). , y 2 ∈ C 是任意的, 所以 g ( x θ ) ≤ θ g ( x 1 ) ( 1 − θ ) g ( x 2 ) \begin{aligned},y_2\in C\text{ 是任意的, 所以 }g(x_\theta)\leq\theta g(x_1)(1-\theta)g(x_2)\end{aligned} ,y2∈C 是任意的, 所以 g(xθ)≤θg(x1)(1−θ)g(x2)即 g g g是凸函数.
例 3.2.1 (点到凸集的距离) 设 ∥ ⋅ ∥ \parallel\cdot\parallel ∥⋅∥ 是 R n \mathbb{R}^n Rn 中一个半范数 C C C 是 R n \mathbb{R}^n Rn 中凸集则 d i s t ( x , C ) : inf y ∈ C ∥ x − y ∥ , ∀ x ∈ R n , \mathbf{dist}(x,C):\inf_{y\in C}\|x-y\|,\quad\forall x\in\mathbb{R}^n, dist(x,C):y∈Cinf∥x−y∥,∀x∈Rn,是 R n \mathbb{R}^n Rn 中凸函数.
证易见 f ( x , y ) : ∥ x − y ∥ f(x,y):\|x-y\| f(x,y):∥x−y∥ 是 R n × R n \mathbb{R}^n\times\mathbb{R}^n Rn×Rn 上凸函数所以 d i s t ( x , C ) : inf y ∈ C f ( x , y ) {\mathrm{dist}}(x,C):\inf_{y\in\mathcal{C}}f(x,y) dist(x,C):infy∈Cf(x,y) 是凸函数.
