凸函数笔记(1)

2023-12-17 06:33:54

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:RnR, d o m ( f ) : = { x ∈ R n ∣ f ( x ) < ∞ } \mathbf{dom}(f):=\{x\in\mathbb{R}^n|f(x)<\infty\} dom(f):={xRnf(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)>??(?xRn)??dom(f)=?,?则称?f?是真的?(proper).

定义 1.1(凸函数):称函数 f : R n → R  ̄ f:\mathbb{R}^n\to\overline{\mathbb{R}} f:RnR是一个凸函数,如果对于任意的 x , y ∈ d o m ( f ) x,y \in \mathbf{dom}(f) x,ydom(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?θ)ydom(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,ydom(f),x=y 0 < θ < 1 0<\theta<1 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:RnR??α-水平集定义为: l e v α ( f ) : = { x ∈ R n ∣ f ( x ) ≤ α } . \mathbf{lev}_\alpha(f):=\{x\in\mathbb{R}^n|f(x)\leq\alpha\}. levα?(f):={xRnf(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:RnR?是凸的,???α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,ylevα?(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?θ)ylevα?(f).?levα?(f)?是凸集.

命题 1.1 的逆命题不成立。一个函数的水平集是凸集,不能够推出这个函数是凸函数。

此外函数的凸性可以通过集合的凸性来刻画。

定义 1.3(上镜图(epigraph))对于函数 f : R n → R  ̄ f:\mathbb{R}^n\to\overline{\mathbb{R}} f:RnR,我们称 R n + 1 \mathbb{R}^{n+1} Rn+1中集合 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×Rf(x)t} f f f上镜图

命题 1.2(函数凸性的上镜图刻画) 函数 f : R n → R  ̄ f:\mathbb{R}^n\to\overline{\mathbb{R}} f:RnR是凸函数当且仅当 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:RnR是凸函数当且仅当 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:RnR{},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,ydom(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,ydom(f),θ(0,1),??z=θy+(1?θ)x.

由于有效域是凸集 , 那么 z ∈ d o m ( f ) 由于有效域是凸集,\text{那么}z\in \mathbf{dom}( f) 由于有效域是凸集,那么zdom(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,ydom(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:RnR{},dom(f)是一个凸集,且fdom(f)上二阶连续可微,那么(1)是凸函数当且仅当:对任意xdom(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 ?xdom(f),?hRn 以及充分小的 θ ∈ ( 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)h+o(\theta^2). f(x+θh)=f(x)+θ?f(x)Th+21?θ2hT?2f(x)h+o(θ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)h+o(\theta^{2})\geq0. 21?θ2hT?2f(x)h+o(θ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)h0.由 h ∈ R n h\in\mathbb{R}^n hRn 的任意性即知 ? 2 f ( x ) \nabla^2f(x) ?2f(x) 是半正定的.

充分性: 设对任意 x ∈ d o m ( f ) , ? 2 f ( x ) x\in\mathbf{dom}(f),\nabla^2f(x) xdom(f),?2f(x) 是半正定的. ? x , y ∈ d o m ( f ) , ? x ≠ y \forall x,y\in\mathbf{dom}(f),\:x\neq y ?x,ydom(f),x=y,则存在 ξ = ( 1 ? θ ) x + θ y ∈ d o m ( f ) \xi=(1-\theta)x+\theta y\in\mathbf{dom}(f) ξ=(1?θ)x+θydom(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,ydom(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:RnR{} 均为凸函数:

(1) 仿射函数: f ( x ) = a T x + b , ? a ∈ R n , b ∈ R . f(x)=a^Tx+b,\:a\in\mathbb{R}^n,b\in\mathbb{R}. f(x)=aTx+b,aRn,bR.

(2) 二次函数: f ( x ) : = 1 2 x T A x + b T x + c , A ∈ S + n , b ∈ R n , c ∈ R f(x):=\frac12x^TAx+b^Tx+c,\quad A\in\mathbb{S}_+^n,\quad b\in\mathbb{R}^n,\quad c\in\mathbb{R} f(x):=21?xTAx+bTx+c,AS+n?,bRn,cR. 特别地,当 A ∈ S ? + n A\in\mathbb{S}_{\vdash+}^n AS?+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_{i=1}^ne^{x_i}) f(x):=ln(i=1n?exi?),其中 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?i=1n?lnxi?), d o m ( f ) \mathbf{dom}(f) dom(f) : = R + + n . \mathbb{R} _{+ + }^n. R++n?.

:(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_{i=1}^{n}\ln x_i\Big)=-\big(\prod_{i=1}^{n}x_i\big)^{1/n},\quad\text{dom}(f):=\mathbb{R}_{++}^{n}. f(x)=?exp(n1?i=1n?lnxi?)=?(i=1n?xi?)1/n,dom(f):=R++n?.所以,此函数又称为负几何平均函数.

3. 保凸运算

3.1 复合函数的凸性

命题 3.1.1:设 h : R m → R  ̄ h:\mathbb{R}^m\to\overline{\mathbb{R}} h:RmR 是一个凸函数,对 i = 1 , ? ? , m , g i : C i → R i=1,\cdots,m,g_i:C_i\to\mathbb{R} i=1,?,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 ) ) < ∞ } , f=h\circ g,\quad\textbf{dom}(f):=\Big\{x\in\bigcap\limits_{i=1}^mC_i\Big|h(g(x))<\infty\Big\}, f=h°g,dom(f):={xi=1?m?Ci? ?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,ydom(f),θ[0,1],我们有 θ x + ( 1 ? θ ) y ∈ ? i = 1 m C i \theta x+(1-\theta)y\in\bigcap_{i=1}^mC_i θx+(1?θ)y?i=1m?Ci?, 且 θ 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 i=1

( 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?)Tv的值,其中,除了 v ∈ d o m ( h ) v \in\mathbf{dom}(h) vdom(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:CR是凸函数,其中 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):={xCg(x)>0}f(x):=1/g(x),dom(f):={xCg(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 i=1,\cdots,m fi?:RnR{},i=1,?,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),?xRn, 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_{i=1}^m\mathbf{dom}(f_i),\quad\mathbf{dom}(h)=\mathbf{dom}(f_1)\times\cdots\times\mathbf{dom}(f_m). dom(f)=i=1?m?dom(fi?),dom(h)=dom(f1?)×?×dom(fm?).

命题 3.2.2:(与仿射变换复合) 设 f : R n → R  ̄ f:\mathbb{R}^n\to\overline{\mathbb{R}} f:RnR 为凸函数, A ∈ R m × n , b ∈ R m A\in\mathbb{R}^{m\times n},\quad b\in\mathbb{R}^m ARm×n,bRm, 那么 g ( x ) : = f ( A x + b ) g(x):=f(Ax+b) g(x):=f(Ax+b) 是凸函数.

命题 3.2.3:(凸函数族的逐点上确界) 设 f γ : R n → R  ̄ , γ ∈ Γ ≠ ? f_\gamma:\mathbb{R}^n\to\overline{\mathbb{R}},\quad\gamma\in\Gamma\neq\emptyset fγ?:RnR,γΓ=?,是一族凸函数,则 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):=γΓsup?fγ?(x),xRn,也是凸函数.

: 容易证明 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=γΓsup?fγ??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×RmR 是一个凸函数, 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):=yCinf?f(x,y)是一个凸函数.

.:易见 g g g 的有效定义域为 d o m ( g ) : = { x ∣ \mathbf{dom}(g):=\{x| dom(g):={x存在 y ∈ C y\in C yC, 使得 ( 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):=yCinf?x?y,?xRn, 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):=infyC?f(x,y) 是凸函数.

文章来源:https://blog.csdn.net/weixin_47255403/article/details/135032720
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。