凸函数笔记（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: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),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: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}^{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×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)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)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),x=y,则存在 ξ = ( 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^Tx+b,\:a\in\mathbb{R}^n,b\in\mathbb{R}. f(x)=aTx+b,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^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,A∈S+n?,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_{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=1∑n?lnxi?)=?(i=1∏n?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:Rm→R 是一个凸函数，对 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):={x∈i=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,y∈dom(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?)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 i=1,\cdots,m fi?:Rn→R∪{∞},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),?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_{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: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(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γ?: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):=γ∈Γsup?fγ?(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=γ∈Γ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×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∈Cinf?f(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∈C?f(x,y) 是凸函数.

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