凸函数笔记(2)

2023-12-17 20:03:13

4. 凸函数的结构

本节将证明: 给定凸函数 f f f 的一个相对内点 x x x, 必存在过 ( x , f ( x ) ) (x,f(x)) (x,f(x)) 的一个仿射函数 y = f ( x ) + v T ( y ? x ) y=f(x)+v^T(y-x) y=f(x)+vT(y?x) 支撑函数 f f f. 进而说明,下半连续的凸函数是仿射函数的逐点上确界.

函数 f : R n → R  ̄ f:\mathbb{R}^n\to\overline{\mathbb{R}} f:RnR 称为是下半连续的,是指对 R n \mathbb{R}^n Rn 中任意收敛的点列 x k → x ? ( k → ∞ ) x_k\to x\:(k\to\infty) xk?x(k) f ( x ) ≤ lim ? k → ∞ f ( x k ) . f(x)\leq\lim_{k\to\infty}f(x_k). f(x)klim?f(xk?).下半连续的函数也称为闭函数.

命题 4.1 (切平面的存在性):设 f : R n → R ∪ { ∞ } f:\mathbb{R}^n\to\mathbb{R}\cup\{\infty\} f:RnR{} 是真凸函数, x ∈ r i ( d o m ( f ) ) x\in\mathbf{ri}(\mathbf{dom}(f)) xri(dom(f)),则存在 v ∈ R n v\in\mathbb{R}^n vRn 使得 f ( y ) ≥ f ( x ) + v T ( y ? x ) , ? y ∈ R n . \begin{align}f(y)\geq f(x)+v^T(y-x),\quad\forall y\in\mathbb{R}^n.\end{align} f(y)f(x)+vT(y?x),?yRn.??因而 f f f 在有界集上有下界. 特别,若 f f f x x x 处可微,则 v = ? f ( x ) v=\nabla f(x) v=?f(x)

: 所需证的结论意味着切平面 t = f ( x ) + v T ( y ? x ) t=f(x)+v^T(y-x) t=f(x)+vT(y?x) 是上镜图 e p i ( f ) \mathbf{epi}(f) epi(f) 的支撑超平面,如图 4.1所示,由于 e p i ( f ) \mathbf{epi}(f) epi(f) R n + 1 \mathbb{R}^{n+1} Rn+1 中一凸集, ( x , f ( x ) ) (x,f(x)) (x,f(x)) 是边界上一点,所以这样的超平面是存在的. 但需要证明该超平面不与 R n + 1 \mathbb{R}^{n+1} Rn+1 中坐标向量 (0,…,0,1) 平行.


图 4.1:支撑超平面示意图

第一步: 支撑超平面的存在性: 设 x ∈ r i ( d o m ( f ) ) x\in\mathbf{ri}(\mathbf{dom}(f)) xri(dom(f)). 因为 e p i ( f ) \mathbf{epi}(f) epi(f)是凸集,显然 ( x , f ( x ) ) ∈ c l ( e p i ( f ) ) ? r i ( e p i ( f ) ) (x,f(x))\in\mathbf{cl}(\mathbf{epi}(f))\setminus\mathbf{ri}(\mathbf{epi}(f)) (x,f(x))cl(epi(f))?ri(epi(f)).根据支撑超平面命题, 存在 ( a T , b ) T ∈ R n + 1 (a^T,b)^T\in\mathbb{R}^{n+1} (aT,b)TRn+1,使得 ( a T , b ) [ ( y t ) ? ( x f ( x ) ) ] ≥ 0 , ? ( y t ) ∈ e p i ( f ) , (a^T,b)\Big[\begin{pmatrix}y\\t\end{pmatrix}-\begin{pmatrix}x\\f(x)\end{pmatrix}\Big]\geq0,\quad\forall\begin{pmatrix}y\\t\end{pmatrix}\in\mathbf{epi}(f), (aT,b)[(yt?)?(xf(x)?)]0,?(yt?)epi(f),其中等号不恒成立.显然上式可化为 a T ( y ? x ) + b ( t ? f ( x ) ) ≥ 0 , ? y ∈ d o m ( f ) , ? t ≥ f ( y ) , \begin{align} a^T(y-x)+b(t-f(x))\geq0,\quad\forall y\in\mathbf{dom}(f),\:t\geq f(y),\end{align} aT(y?x)+b(t?f(x))0,?ydom(f),tf(y),??且存在 y ˉ ∈ d o m ( f ) , t ˉ ≥ f ( y ˉ ) \bar{y}\in\mathbf{dom}(f),\bar{t}\geq f(\bar{y}) yˉ?dom(f),tˉf(yˉ?), 使得 a T ( y ˉ ? x ) + b ( t ˉ ? f ( x ) ) > 0. a^T(\bar{y}-x)+b(\bar{t}-f(x))>0. aT(yˉ??x)+b(tˉ?f(x))>0.

第二步 : b ≥ 0 :b\geq0 :b0:在(2)中,令 t → ∞ t\to\infty t 可知 b ≥ 0. b\geq0. b0.

第三步 : b > 0 :b>0 :b>0:若 b = 0 b=0 b=0,则 a T ( y ? x ) ≥ 0 , ? y ∈ d o m ( f ) , \begin{align} a^T(y-x)\geq0,\quad\forall y\in\mathbf{dom}(f),\end{align} aT(y?x)0,?ydom(f),??且存在 y ˉ ∈ d o m ( f ) \bar{y}\in\mathbf{dom}(f) yˉ?dom(f),使得 a T ( y ˉ ? x ) > 0 a^T(\bar{y}-x)>0 aT(yˉ??x)>0. 这意味着凸集 d o m ( f ) \mathbf{dom}( f) dom(f) { x } \{x\} {x} 被超平面 a T ( y ? x ) = 0 a^T(y-x)=0 aT(y?x)=0 真分离.根据凸集分离定理得: r i ( { x } ) ∩ r i ( d o m ( f ) ) = ? \mathbf{ri}(\{x\})\cap\mathbf{ri}(\mathbf{dom}(f))=\emptyset ri({x})ri(dom(f))=?.即 x ∈? r i ( d o m ( f ) ) x\not\in\mathbf{ri}(\mathbf{dom}(f)) xri(dom(f)).矛盾.所以 b > 0. b>0. b>0.

第四步: 切平面的存在性: 记 v : = ? a / b v:=-a/b v:=?a/b,代入(2), 并令 t = f ( y ) t=f(y) t=f(y),便得到 f ( y ) ≥ f ( x ) + v T ( y ? x ) , ? y ∈ d o m ( f ) f(y)\geq f(x)+v^T(y-x),\forall y\in\mathbf{dom}(f) f(y)f(x)+vT(y?x),?ydom(f).当 y ∈ R n ? d o m ( f ) y\in\mathbb{R}^n\setminus\mathbf{dom}(f) yRn?dom(f) 时,此不等式显然仍成立.

f ( x ) > ? ∞ f(x)>-\infty f(x)>?.对任意的 r > 0 r>0 r>0,当 y ∈ B ( x , r ) y\in B(x,r) yB(x,r) 时,有 f ( y ) ≥ f ( x ) + v T ( y ? x ) ≥ f ( x ) ? ∥ v ∥ 2 ∥ y ? x ∥ 2 ≥ f ( x ) ? r ∥ v ∥ 2 . \begin{aligned}f(y)\geq f(x)+v^T(y-x)\geq f(x)-\|v\|_2\|y-x\|_2\geq f(x)-r\|v\|_2.\end{aligned} f(y)f(x)+vT(y?x)f(x)?v2?y?x2?f(x)?rv2?.?所以 f f f B ( x , r ) B(x,r) B(x,r) 上有下界.

最后,当 f f f x x x 处可微时容易证明 v = ? f ( x ) v=\nabla f(x) v=?f(x).

注 1:满足(1)的 v v v 称为 f f f x x x 处的次梯度, 记为 v ∈ ? f ( x ) v ∈ ?f(x) v?f(x). 命题 3.4.1说明, 当 f f f 是凸函数且 x ∈ r i ( d o m ( f ) ) x ∈ \mathbf{ri}(\mathbf{dom}(f)) xri(dom(f)) 时, ? f ( x ) ?f(x) ?f(x) 非空.当 x ? r i ( d o m ( f ) ) x \notin \mathbf{ri}(\mathbf{dom}(f)) x/ri(dom(f)) 时, 次梯度未必存在.

注2:注 2: 证明的第三步也可以不利用凸集分离定理而直接证明: 因 x ∈ r i ( d o m ( f ) ) x\in\mathbf{ri}(\mathbf{dom}(f)) xri(dom(f)),对任意的 y ∈ d o m ( f ) y\in\mathbf{dom}(f) ydom(f),根据线段原理 可知,存在 λ > 1 \lambda>1 λ>1, 使得 y + λ ( x ? y ) ∈ d o m ( f ) . y+\lambda(x-y)\in \mathbf{dom}(f) . y+λ(x?y)dom(f). y + λ ( x ? y ) = x ? ( λ ? 1 ) ( y ? x ) ∈ d o m ( f ) . \begin{aligned}y+\lambda(x-y)=x-(\lambda-1)(y-x)\in\mathbf{dom}(f).\end{aligned} y+λ(x?y)=x?(λ?1)(y?x)dom(f).? x ? ( λ ? 1 ) ( y ? x ) x-(\lambda-1)(y-x) x?(λ?1)(y?x) 替换(3)中的 y y y 便得 ? ( λ ? 1 ) a T ( y ? x ) ≥ 0 -(\lambda-1)a^T(y-x)\geq0 ?(λ?1)aT(y?x)0,即 a T ( y ? x ) ≤ 0. a^T(y-x)\leq0. aT(y?x)0. 联立(3)得 a T ( y ? x ) = 0 a^T(y-x)=0 aT(y?x)=0.与 a T ( y ˉ ? x ) > 0 a^T(\bar{y}-x)>0 aT(yˉ??x)>0 矛盾.所以 b > 0. b>0. b>0.

命题 4.2: (凸函数是仿射函数族的逐点上确界) 设 f : R n → R ∪ { ∞ } f:\mathbb{R}^n\to\mathbb{R}\cup\{\infty\} f:RnR{} 是凸函数,且下半连续的,那么对任意的 x ∈ R n x\in\mathbb{R}^n xRn, 存在一列仿射函数 { g k } \{g_k\} {gk?}, 使得 f ( y ) ≥ g k ( y ) , ? ? y ∈ R n , g k ( x ) → f ( x ) ? ( k → ∞ ) . \begin{aligned}f(y)\geq g_k(y),\:\forall y\in\mathbb{R}^n,\quad g_k(x)\to f(x)\:(k\to\infty).\end{aligned} f(y)gk?(y),?yRn,gk?(x)f(x)(k).?从而 f ( x ) = sup ? { g ( x ) ∣ g 是仿射函数 , ?满足 : g ( y ) ≤ f ( y ) , ? ? y ∈ R n } . \begin{align} f(x)=\sup\{g(x)|g\text{是仿射函数},\text{ 满足}:g(y)\leq f(y),\mathrm{~}\forall y\in\mathbb{R}^n\}.\end{align} f(x)=sup{g(x)g是仿射函数,?满足:g(y)f(y),??yRn}.??

:根据命题 4.1, 只需考虑 x ∈ R n ? r i ( d o m ( f ) ) x\in\mathbb{R}^n\setminus\mathbf{ri}(\mathbf{dom}(f)) xRn?ri(dom(f)) 的情形.不妨设 d o m \mathbf{dom} dom ( f ) ≠ ? ( f) \neq\emptyset (f)=?.否则令 g k ( y ) ≡ k , ? ? y ∈ R n . g_k(y)\equiv k,\:\forall y\in\mathbb{R}^n. gk?(y)k,?yRn.

(a) 若 x ∈ c l ( d o m ( f ) ) \ r i ( d o m ( f ) ) x\in\mathbf{cl}(\mathbf{dom}(f))\backslash\mathbf{ri}(\mathbf{dom}(f)) xcl(dom(f))\ri(dom(f)), 取 x 0 ∈ r i ( d o m ( f ) ) x_0\in\mathbf{ri}(\mathbf{dom}(f)) x0?ri(dom(f)) x k : = x + 1 k ( x 0 ? x ) , ? k ∈ N . x_k:=x+\frac1k(x_0-x),\:k\in\mathbb{N}. xk?:=x+k1?(x0??x),kN. 由线段原理可知 x k ∈ r i ( d o m ( f ) ) x_k\in\mathbf{ri}(\mathbf{dom}(f)) xk?ri(dom(f)),于是,利用命题 4.1可知,存在仿射函数 g k ( y ) = g_k(y)= gk?(y)= f ( x k ) + v k T ( y ? x k ) , \begin{aligned}f(x_k)+v_k^T(y-x_k),\end{aligned} f(xk?)+vkT?(y?xk?),? 使得 f ( y ) ≥ g k ( y ) , ? y ∈ R n . f(y)\geq g_{k}(y),\quad\forall y\in\mathbb{R}^{n}. f(y)gk?(y),?yRn.
在上式中令 y = x 0 y=x_0 y=x0?,得:
f ( x 0 ) ≥ f ( x k ) + v k T ( x 0 ? x k ) = f ( x k ) + ( 1 ? 1 k ) v k T ( x 0 ? x ) \begin{aligned} f(x_{0})\geq f(x_{k})+v_{k}^{T}(x_{0}-x_{k})=f(x_{k})+(1-\frac{1}{k})v_{k}^{T}(x_{0}-x)\end{aligned} f(x0?)f(xk?)+vkT?(x0??xk?)=f(xk?)+(1?k1?)vkT?(x0??x)?
从而,当 k ≥ 2 k\geq2 k2 时, 有: v k T ( x 0 ? x ) ≤ k k ? 1 [ f ( x 0 ) ? f ( x k ) ] v_k^T(x_0-x)\leq\frac k{k-1}[f(x_0)-f(x_k)] vkT?(x0??x)k?1k?[f(x0?)?f(xk?)].于是 g k ( x ) = f ( x k ) + v k T ( x ? x k ) = f ( x k ) ? 1 k v k T ( x 0 ? x ) ≥ f ( x k ) ? 1 k ? 1 [ f ( x 0 ) ? f ( x k ) ] = k k ? 1 f ( x k ) ? 1 k ? 1 f ( x 0 ) . \begin{aligned}g_k(x)&=f(x_k)+v_k^T(x-x_k)=f(x_k)-\frac{1}{k}v_k^T(x_0-x)\\ &\geq f(x_k)-\frac1{k-1}[f(x_0)-f(x_k)] \\ &=\frac k{k-1}f(x_k)-\frac1{k-1}f(x_0). \end{aligned} gk?(x)?=f(xk?)+vkT?(x?xk?)=f(xk?)?k1?vkT?(x0??x)f(xk?)?k?11?[f(x0?)?f(xk?)]=k?1k?f(xk?)?k?11?f(x0?).? k → ∞ k\to\infty k,取下极限,利用 f f f 的下半连续性,得 f ( x ) ≤ lim ?  ̄ k → ∞ f ( x k ) ≤ lim ?  ̄ k → ∞ g k ( x ) . f(x)\leq\underline{\lim}_{k\to\infty}f(x_k)\leq\underline{\lim}_{k\to\infty}g_k(x). f(x)lim?k?f(xk?)lim?k?gk?(x).

f ( x ) ≥ g k ( x ) , ? ? k ∈ N f(x)\geq g_k(x),\:\forall k\in\mathbb{N} f(x)gk?(x),?kN.故 f ( x ) ≥ lim ?  ̄ k → ∞ g k ( x ) f(x)\geq\overline{\lim}_{k\to\infty}g_k(x) f(x)limk?gk?(x).所以 lim ? k → ∞ g k ( x ) = f ( x ) . \lim_{k\to\infty}g_k(x)=f(x). limk?gk?(x)=f(x).

(b) 若 x ∈ R n ? c l ( d o m ( f ) ) x\in\mathbb{R}^n\setminus\mathbf{cl}(\mathbf{dom}(f)) xRn?cl(dom(f)),因 d o m ( f ) \mathbf{dom}(f) dom(f) 非空,据 (1)所证,存在仿射函数 g g g,使得 f ( y ) ≥ g ( y ) , ? ? y ∈ R n . \begin{aligned}f(y)\geq g(y),\:\forall y\in\mathbb{R}^n.\end{aligned} f(y)g(y),?yRn.?

根据凸集的严格分离命题,存在 a ∈ R n a\in\mathbb{R}^n aRn b ∈ R b\in\mathbb{R} bR, 使得超平面 a T x + b = 0 a^Tx+b=0 aTx+b=0 严格分离 x x x c l ( d o m ( f ) ) \mathbf{cl}(\mathbf{dom}(f) ) cl(dom(f)),即

a T x + b > 0 , a T y + b ≤ 0 , ? y ∈ c l ( d o m ( f ) ) . a^Tx+b>0,\quad a^Ty+b\leq0,\quad\forall y\in\mathbf{cl}(\mathbf{dom}(f)). aTx+b>0,aTy+b0,?ycl(dom(f)).
a a a b b b 乘以适当的正数,可设 (将 a , b a,b a,b 改记为 a k , b k ) a_k,b_k) ak?,bk?)
a k T x + b k = k ?且? a k T y + b k ≤ 0 , ? y ∈ c l ( d o m ( f ) ) . a_k^Tx+b_k=k\quad\text{ 且 }\quad a_k^Ty+b_k\leq0,\quad\forall y\in\mathbf{cl}(\mathbf{dom}(f)). akT?x+bk?=k??akT?y+bk?0,?ycl(dom(f)). g k ( y ) : = g ( y ) + a k T y + b k g_k(y):=g(y)+a_k^Ty+b_k gk?(y):=g(y)+akT?y+bk?, 则 g k g_k gk? 仍为仿射函数,满足 g k ( y ) = g ( y ) + a k T y + b k ≤ g ( y ) ≤ f ( y ) , ? y ∈ d o m ( f ) , g_k(y)=g(y)+a_k^Ty+b_k\leq g(y)\leq f(y),\quad\forall y\in\mathbf{dom}(f), gk?(y)=g(y)+akT?y+bk?g(y)f(y),?ydom(f), g k ( x ) = g ( x ) + k → ∞ , ? k → ∞ . g_k(x)=g(x)+k\to\infty,\:k\to\infty. gk?(x)=g(x)+k,k∞.

最后, 利用已证结论容易推出(4),此部分可以留作练习。

5. 拟凸函数

5.1 定义与等价刻画

凸函数因为其局部极小必为全局极小而在优化理论中具有特别的重要性. 可以将具有这一特性的函数可以推广到更大的函数类, 即拟凸函数.

定义 5.1.1: (拟凸函数) 对函数 f : R n → R  ̄ f:\mathbb{R}^n\to\overline{\mathbb{R}} f:RnR, 如果 f ( θ x + ( 1 ? θ ) y ) ≤ max ? { f ( x ) , f ( y ) } , ? x , y ∈ d o m ( f ) , θ ∈ [ 0 , 1 ] , \begin{align} f(\theta x+(1-\theta)y)\leq\max\{f(x),f(y)\},\quad\forall x,y\in\mathbf{dom}(f),\quad\theta\in[0,1],\end{align} f(θx+(1?θ)y)max{f(x),f(y)},?x,ydom(f),θ[0,1],??则称 f f f 是拟凸的. 如果上式中的严格不等号对 x ≠ y x\neq y x=y 恒成立,则称 f f f 是严格拟凸的.

如果 ? f ?f ?f 是拟凸 (或严格拟凸) 的, 则称 f f f 是拟凹 (或严格拟凹) 的. 既是拟凸又是拟凹的函数称为拟线性函数.

拟凸函数的有效定义域 d o m ( f ) \mathbf{dom}(f) dom(f) 必为凸集.

易见,拟凸函数的有效定义域 d o m ( f ) \mathbf{dom}(f) dom(f)必为凸集. 对函数 f : R n → R ∪ { ∞ } f:\mathbb{R}^n\to\mathbb{R}\cup\{\infty\} f:RnR{},易见(5) 等价于 f ( θ x + ( 1 ? θ ) y ) ≤ max ? { f ( x ) , f ( y ) } , ? x , y ∈ R n , θ ∈ [ 0 , 1 ] . \begin{align} f(\theta x+(1-\theta)y)\leq\max\{f(x),f(y)\},\quad\forall x,y\in\mathbb{R}^n,\quad\theta\in[0,1].\end{align} f(θx+(1?θ)y)max{f(x),f(y)},?x,yRn,θ[0,1].??依据定义容易看出, 凸函数必为拟凸的; 凹函数必为拟凹的. 仿射函数必为拟线性的.

命题 5.1.1 :(拟凸性的水平集刻画) 函数 f : R n → R ∪ { ∞ } f:\mathbb{R}^n\to\mathbb{R}\cup\{\infty\} f:RnR{}是拟凸的当且仅当: ? α ∈ R ?α ∈ \mathbb{R} ?αR,水平集 l e v α ( f ) : = x ∈ R n ∣ f ( x ) ≤ α \mathbf{levα}(f) := {x ∈ \mathbb{R}^n \mid f(x) ≤ α} levα(f):=xRnf(x)α 是凸集.

:设 f f f 是拟凸函数,那么,对任意的 α ∈ R \alpha\in\mathbb{R} αR,若 x , y ∈ l e v α ( f ) x,y\in\mathbf{lev}_\alpha(f) x,ylevα?(f) 以及 ? θ ∈ [ 0 , 1 ] \forall\theta\in[0,1] ?θ[0,1],有
f ( θ x + ( 1 ? θ ) y ) ≤ max ? { f ( x ) , f ( y ) } ≤ α . f(\theta x+(1-\theta)y)\leq\max\{f(x),f(y)\}\leq\alpha. f(θx+(1?θ)y)max{f(x),f(y)}α.
所以 θ x + ( 1 ? θ ) y ∈ l e v α ( f ) \theta x+(1-\theta)y\in\mathbf{lev}_\alpha(f) θx+(1?θ)ylevα?(f).从而 l e v α ( f ) \mathbf{lev}_\alpha(f) levα?(f) 是凸集.

反之,设对任意的 α ∈ R \alpha\in\mathbb{R} αR, 水平集 l e v α ( f ) \mathrm{lev}_\alpha(f) levα?(f) 是凸集. 那么, ? x , y ∈ d o m ( f ) \forall x,y\in\mathbf{dom}(f) ?x,ydom(f), 不妨设 f ( y ) ≤ f ( x ) f(y)\leq f(x) f(y)f(x),对任意的 α > f ( x ) \alpha>f(x) α>f(x),有 x , y ∈ l e v α ( f ) x,y\in\mathbf{lev}_\alpha(f) x,ylevα?(f). 根据 l e v α ( f ) \mathbf{lev}_\alpha(f) levα?(f) 凸性可知, ? θ ∈ [ 0 , 1 ] \forall\theta\in[0,1] ?θ[0,1],有 θ x + ( 1 ? θ ) y ∈ l e v α ( f ) \theta x+(1-\theta)y\in\mathbf{lev}_\alpha(f) θx+(1?θ)ylevα?(f),从而 f ( θ x + ( 1 ? θ ) y ) ≤ α f(\theta x+(1-\theta)y)\leq\alpha f(θx+(1?θ)y)α.令 α → f ( x ) \alpha\to f(x) αf(x),便得 f ( θ x + ( 1 ? θ ) y ) ≤ f ( x ) = max ? { f ( x ) , f ( y ) } \begin{aligned}f(\theta x+(1-\theta)y)\leq f(x)=\max\{f(x),f(y)\}\end{aligned} f(θx+(1?θ)y)f(x)=max{f(x),f(y)}?.所以 f f f 是拟凸函数.

定义 5.1.2: (截面函数) 设 x , y ∈ d o m ( f ) x,y\in\mathbf{dom}(f) x,ydom(f),考虑函数 f f f 限制在过 x , y x,y x,y 的直线上的函数

? ( t ) : = f ( x + t ( y ? x ) ) , t ∈ R , \begin{align} \phi(t):=f(x+t(y-x)),\quad t\in\mathbb{R},\end{align} ?(t):=f(x+t(y?x)),tR,??它是一个一元函数,称为 f f f 的截面函数.

命题 5.1.2:(拟凸函数的截面刻画) 函数 f : R n → R  ̄ f:\mathbb{R}^n\to\overline{\mathbb{R}} f:RnR 是拟凸函数当且仅当如下条件之一成立:

( 5.1.2.1 ) ? ? x , y ∈ R n , ? ( 7 ) (5.1.2.1)\:\forall x,y\in\mathbb{R}^n,\:(7) (5.1.2.1)?x,yRn,(7)所定义的 ? \phi ? 是一元拟凸函数.

( 5.1.2.2 ) ? ? x , y ∈ R n , ? ( 7 ) (5.1.2.2)\:\forall x,y\in\mathbb{R}^n,\:(7) (5.1.2.2)?x,yRn,(7)所定义的 ? \phi ? 满足 ? ( t ) ≤ max ? { ? ( 0 ) , ? ( 1 ) } , ? ? t ∈ [ 0 , 1 ] . \phi(t)\leq\max\{\phi(0),\phi(1)\},\:\forall t\in[0,1]. ?(t)max{?(0),?(1)},?t[0,1].

( a ) (a) (a) f : R n → R  ̄ f:\mathbb{R}^n\to\overline{\mathbb{R}} f:RnR 是拟凸函数,那么 ? x , y ∈ R n \forall x,y\in\mathbb{R}^n ?x,yRn ? t , s ∈ R \forall t,s\in\mathbb{R} ?t,sR 以及 θ ∈ [ 0 , 1 ] \theta\in[0,1] θ[0,1], 记 ξ : = x + t ( y ? x ) , ? η : = x + s ( y ? x ) \xi:=x+t(y-x),\:\eta:=x+s(y-x) ξ:=x+t(y?x),η:=x+s(y?x).有
θ ξ + ( 1 ? θ ) η = x + ( θ t + ( 1 ? θ ) s ) ( y ? x ) . \theta\xi+(1-\theta)\eta=x+\left(\theta t+(1-\theta)s\right)(y-x). θξ+(1?θ)η=x+(θt+(1?θ)s)(y?x).于是
? ( θ t + ( 1 ? θ ) s ) = f ( θ ξ + ( 1 ? θ ) η ) ≤ max ? { f ( ξ ) , f ( η ) } = max ? { ? ( t ) , ? ( s ) } . \begin{aligned}\phi(\theta t+(1-\theta)s)=f(\theta\xi+(1-\theta)\eta)\leq\max\{f(\xi),f(\eta)\}=\max\{\phi(t),\phi(s)\}.\end{aligned} ?(θt+(1?θ)s)=f(θξ+(1?θ)η)max{f(ξ),f(η)}=max{?(t),?(s)}.?所以, ? \phi ? 是一个一元拟凸函数. 即 (5.1.2.1) 成立.

( b ) (b) (b) 若(5.1.2.1) 成立,那么 ? t ∈ [ 0 , 1 ] \forall t\in[0,1] ?t[0,1],有 ? ( t ) ≤ max ? { ? ( 0 ) , ? ( 1 ) } \phi(t)\leq\max\{\phi(0),\phi(1)\} ?(t)max{?(0),?(1)}.故 (5.1.2.2) 成立.

( c ) (c) (c) 设(5.1.2.2)成立.那么, ? x , y ∈ R n \forall x,y\in\mathbb{R}^n ?x,yRn θ ∈ [ 0 , 1 ] \theta\in[0,1] θ[0,1], 有
f ( x + θ ( y ? x ) ) = ? ( θ ) ≤ max ? { ? ( 0 ) , ? ( 1 ) } = max ? { f ( x ) , f ( y ) } . f(x+\theta(y-x))=\phi(\theta)\leq\max\{\phi(0),\phi(1)\}=\max\{f(x),f(y)\}. f(x+θ(y?x))=?(θ)max{?(0),?(1)}=max{f(x),f(y)}.所以 f f f 是拟凸函数.

命题 5.1.3:(一元拟凸函数) 函数 f : R → R  ̄ f:\mathbb{R}\to\overline{\mathbb{R}} f:RR 拟凸当且仅当如下条件成立:

(5.1.3.1) f f f R \mathbb{R} R 上单调;

(5.1.3.2) R \mathbb{R} R 可以被分成互不相交的左右两个区间,使得 f f f 在左边的区间上递减,在右边的区间上递增.

推论 5.1: 一元函数 f : R → R  ̄ f:\mathbb{R}\to\overline{\mathbb{R}} f:RR 是拟线性的 (既是拟凸的也是拟凹的) 当且仅当 f f f R \mathbb{R} R 上单调函数

5.2 可微函数的拟凸性判定

命题 5.2.1 :(拟凸性的一阶微分判据) 设函数 f : R n → R ∪ { ∞ } f:\mathbb{R}^n\to\mathbb{R}\cup\{\infty\} f:RnR{} 的有效定义域 d o m ( f ) \mathbf{dom}(f) dom(f) 是一个凸集, f f f d o m ( f ) \mathbf{dom}(f) dom(f) 上可微,那么, f f f 是拟凸函数当且仅当:
f ( y ) ≤ f ( x ) 蕴含 ? f ( x ) T ( y ? x ) ≤ 0 , ? x , y ∈ d o m ( f ) . \begin{align} f(y)\leq f(x)\quad\text{蕴含}\quad\nabla f(x)^T(y-x)\leq0,\quad\forall x,y\in\mathbf{dom}(f).\end{align} f(y)f(x)蕴含?f(x)T(y?x)0,?x,ydom(f).??

命题 5.2.3 :(拟凸性的二阶微分判据) 设函数 f : R n → R ∪ { ∞ } f:\mathbb{R}^n\to\mathbb{R}\cup\{\infty\} f:RnR{} 的有效定义域为凸集, f f f d o m ( f ) \mathbf{dom}(f) dom(f) 连续,在 r i ( d o m ( f ) ) \mathbf{ri}(\mathbf{dom}(f)) ri(dom(f)) 上处处二阶连续可微的. 那么,

(5.2.3.1) 当 f f f 拟凸时,对任意的 x ∈ r i ( d o m ( f ) ) x\in\mathbf{ri}(\mathbf{dom}(f)) xri(dom(f)) y ∈ d o m ( f ) y\in\mathbf{dom}(f) ydom(f),当 ? f ( x ) T ( y ? x ) = 0 \nabla f(x)^T(y-x)=0 ?f(x)T(y?x)=0时,有 ( y ? x ) T ? 2 f ( x ) ( y ? x ) ≥ 0 (y-x)^T\nabla^2f(x)(y-x)\geq0 (y?x)T?2f(x)(y?x)0;

(5.2.3.2) 若对任意的 x ∈ r i ( d o m ( f ) ) x\in\mathbf{ri}(\mathbf{dom}(f)) xri(dom(f)) y ∈ d o m ( f ) , ? y ≠ x y\in\mathbf{dom}(f),\:y\neq x ydom(f),y=x,当 ? f ( x ) T ( y ? x ) = 0 \nabla f(x)^T(y-x)=0 ?f(x)T(y?x)=0 时, 有 ( y ? x ) T ? 2 f ( x ) ( y ? x ) > 0 (y-x)^T\nabla^2f(x)(y-x)>0 (y?x)T?2f(x)(y?x)>0,则 f f f 拟凸.

5.3 保拟凸运算

类似于凸函数情形, 可以给出保拟凸运算的若干结果. 这里不加证明地将这些典型的结果罗列在这此.

命题 5.3.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,满足条件:

(5.3.1.1) g i g_i gi? 是凸函数时, h h h 关于第 i i i 个变元 x i x_i xi? 在 R 上递增; 或

(5.3.1.2) g i g_i 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))<},也是拟凸函数.

命题 5.3.2:(关于部分变量的下确界) 设 g : R n × R m → R  ̄ g:\mathbb{R}^n\times\mathbb{R}^m\to\overline{\mathbb{R}} g:Rn×RmR 是拟凸函数, C ? R m C\subset\mathbb{R}^m C?Rm 是非空凸集,那么 f ( x ) : = inf ? inf ? ( x , y ) ∈ d o m ( g ) g ( x , y ) f(x):=\inf_{\underset{(x,y)\in\mathbf{dom}(g)}{\operatorname*{inf}}}g(x,y) f(x):=(x,y)dom(g)inf?inf?g(x,y)是拟凸函数.

命题 5.3.3: (逐点上确界) 设 { f γ } γ ∈ Γ , Γ ≠ ? \{f_\gamma\}_{\gamma\in\Gamma},\quad\Gamma\neq\emptyset {fγ?}γΓ?,Γ=?,是 R n \mathbb{R}^n Rn 上一族拟凸函数,则
f ( x ) : = sup ? γ ∈ Γ f γ ( x ) f(x):=\sup_{\gamma\in\Gamma}f_\gamma(x) f(x):=γΓsup?fγ?(x)也是拟凸函数.

练习

g : R n → R ∪ { ∞ } g:\mathbb{R}^n\to\mathbb{R}\cup\{\infty\} g:RnR{} 是一个凸函数, h : R n → R ∪ { ? ∞ } h:\mathbb{R}^n\to\mathbb{R}\cup\{-\infty\} h:RnR{?} 是凹函数,在凸集 C ? R n C\subset\mathbb{R}^n C?Rn 上,有 g ( x ) ≥ 0 , ? h ( x ) > 0 g(x)\geq0,\:h(x)>0 g(x)0,h(x)>0.那么 f ( x ) : = g ( x ) / h ( x ) , d o m ( f ) : = C f(x):=g(x)/h(x),\quad\mathbf{dom}(f):=C f(x):=g(x)/h(x),dom(f):=C,是拟凸函数.

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