精华内容
下载资源
问答
  • 证明函数凸性的一种判据。

    可微函数 f f f 是凸函数 当且仅当 d o m f domf domf 是凸集,且 ( ▽ f ( x ) − ▽ f ( y ) ) T ( x − y ) > 0 ,      ∀ x , y ∈ d o m f (\bigtriangledown f(x)-\bigtriangledown f(y))^T(x-y)>0, \;\; \forall x,y \in dom f (f(x)f(y))T(xy)>0,x,ydomf ▽ f : R n → R n \bigtriangledown f: \R^n \rightarrow \R^n f:RnRn 是单调映射(monotone mapping)。


    证明:

    1. 如果 f f f 是可微的凸函数,则有 f ( y ) ≥ f ( x ) + ▽ f ( x ) T ( y − x ) , f ( x ) ≥ f ( y ) + ▽ f ( y ) T ( x − y ) . f(y) \geq f(x) + \bigtriangledown f(x)^T(y-x),\\ f(x) \geq f(y) + \bigtriangledown f(y)^T(x-y). f(y)f(x)+f(x)T(yx),f(x)f(y)+f(y)T(xy).将上面两式相加得 ( ▽ f ( x ) − ▽ f ( y ) ) T ( x − y ) > 0 (\bigtriangledown f(x)-\bigtriangledown f(y))^T(x-y)>0 (f(x)f(y))T(xy)>0
    2. 如果 ▽ f \bigtriangledown f f 是单调的,定义函数 g g g : g ( t ) = f ( x + t ( y − x ) ) ,    t ∈ [ 0 , 1 ] g ′ ( t ) = ▽ f ( x + t ( y − x ) ) T ( y − x ) g(t) = f(x+t(y-x)), \;t \in [0,1]\\ g'(t) = \bigtriangledown f(x+t(y-x))^T(y-x) g(t)=f(x+t(yx)),t[0,1]g(t)=f(x+t(yx))T(yx)则由 g ′ ( t ) g'(t) g(t) 的连续性以及 g ′ ( 1 ) − g ′ ( 0 ) > 0    且    g ′ ( 0 ) − g ′ ( 0 ) = 0 g'(1)-g'(0) >0 \;且\; g'(0)-g'(0) = 0 g(1)g(0)>0g(0)g(0)=0 g ′ ( t ) − g ′ ( 0 ) ≥ 0 ,      g'(t) -g'(0) \geq 0,\;\; g(t)g(0)0,因此 f ( y ) = g ( 1 ) = g ( 0 ) + ∫ 0 1 g ′ ( t ) d t ≥ g ( 0 ) + g ′ ( 0 ) = f ( x ) + ▽ f ( x ) ) T ( y − x ) f(y) = g(1) = g(0) + \int_0^1 g'(t)dt \geq g(0) + g'(0) \\= f(x) + \bigtriangledown f(x))^T(y-x) f(y)=g(1)=g(0)+01g(t)dtg(0)+g(0)=f(x)+f(x))T(yx) f f f 为凸函数。
    展开全文
  • 03 凸函数

    2020-01-29 22:51:28
    03 凸函数 目录 3.1 凸函数的定义、性质(凸函数的判定)、示例 3.2 保凸运算 3.4 拟凸函数 3.5 对数凸函数 3.3 共轭函数 3.6 关于广义不等式的凸性 3.1 凸函数的定义、性质和例子 (一)凸函数的定义&扩展值...

    03 凸函数

    目录
    3.1 凸函数的定义、性质(凸函数的判定)、示例
    3.2 保凸运算
    3.4 拟凸函数
    3.5 对数凸函数

    3.3 共轭函数

    3.6 关于广义不等式的凸性

    3.1 凸函数的定义、性质和例子

    (一)凸函数的定义&扩展值延伸

    3.1.1 定义

    Def 1 凸函数的定义、几何含义

    定理1:仿射函数等价于既凸又凹函数。

    定理2 (凸性由函数在直线上的性质刻画)*:凸函数的充要条件是与其定义域相交的任何直线上都是凸的。(可以将函数限制在直线上来判断其是否为凸函数)

    定理3:凸函数在其定义域相对内部连续,只可能在相对边界上不连续。

    3.1.2 扩展值延伸

    Def 2 凸函数扩展值延伸的定义
    目的:简化定义域符号描述:例1.凸函数定义的简化;例2.两个凸函数逐点和函数定义域的简化
    凸集的示性函数[符号描述更灵活]:例1.凸函数的极小化 简化
    ps.凹函数扩展值延伸

    (二)可微凸函数的充要条件

    3.1.3 一阶条件

    定理4(可微凸函数的一阶条件) :假设f可微,则函数f是凸(严格)函数的充要条件是domf是凸集且对任意 x , y ∈ d o m f x,y \in domf x,ydomf,下式成立:
    f ( y ) ≥ ( > ) f ( x ) + Δ f ( x ) T ( y − x ) f(y)\geq(>) f(x)+\Delta f(x)^T(y-x) f(y)(>)f(x)+Δf(x)T(yx)

    一阶条件的含义
    1.凸函数等价于某函数的一阶泰勒近似是全局下估计
    2.凸函数局部信息(某点函数值及导数)可知全局信息(全局下估计、全局极小)

    定理5:如果 ▽ f ( x ) = 0 \bigtriangledown f(x)=0 f(x)=0,那么对于所有 y ∈ d o m f y \in domf ydomf,存在 f ( y ) ≥ f ( x ) f(y)\geq f(x) f(y)f(x),即x是函数f的全局极小点。

    ps.严格凸函数、凹函数的一阶条件

    3.1.4 二阶条件

    定理6(可微凸函数的二阶条件)*:假设f可微,则函数f是凸函数等价于Hessian矩阵是半正定矩阵:对于所有的 x ∈ d o m f x \in domf xdomf,有 ▽ 2 f ( x ) ≥ 0 \bigtriangledown^2 f(x)\geq 0 2f(x)0

    定理7(可微严格凸函数的二阶条件):(1)假设f可微,则函数f是严格凸函数对于所有的 x ∈ d o m f x \in domf xdomf,有 ▽ 2 f ( x ) > 0 \bigtriangledown^2 f(x)> 0 2f(x)>0;(2)逆定理不一定成立。

    ps.凹函数的二阶条件
    示例:二次函数
    注意:凸函数的定义域必须是凸集

    3.1.5 例子(凸函数的判定)

    证明方法:定义、直线上的等价、可微凸函数等价条件
    一维凸函数:指数函数、幂函数、绝对值幂函数、对数函数、负熵
    多维凸函数:范数、最大值函数、二次-线性分式函数、指数和的对数、几何平均、对数-行列式

    (三)凸函数的性质

    (1)3.1.6 下水平集

    Def 3 下水平集的定义

    定理8(不等价):(1)凸函数的下水平集为凸集;(2)下水平集是凸集的函数不一定是凸函数。(反之不一定成立)

    ps.上水平集的定义

    (2)3.1.7 上境图

    Def 4 上境图的定义

    定理9(等价)*:一个函数是凸函数等价于其上境图是凸集,一个函数是凹函数等价于其下境图是凸集。

    示例:矩阵分式函数
    凸函数一阶条件的几何含义:上境图结合凸集的结论证明凸函数的结论

    (3) 凸函数基本不等式的扩展

    3.1.8 Jensen不等式及其扩展

    Def 5 基本不等式扩展至多点的凸组合、积分、期望

    3.1.9 不等式

    利用Jensen不等式证明以下不等式:
    Def 6 算数-几何平均不等式
    Def 7 Holder不等式

    3.2 保凸运算

    (一) 基本的保凸运算

    3.2.1 凸函数非负加权求和

    定理10:(1)凸函数构成的集合是凸锥:凸函数的非负加权求和仍然是凸函数,即函数 f = w 1 f 1 + . . . + w m f m f=w_1f_1+...+w_mf_m f=w1f1+...+wmfm是凸函数;
    (2)凹函数的非负加权求和是凹函数;
    (3)严格凸(凹)函数的非负、非零加权求和是严格凸(凹)函数。

    推论11(推广到无限项求和、积分情形):如果固定任意 y ∈ A y \in A yA,函数f(x,y)关于x是凸函数,且对任意 y ∈ A y \in A yA,有 w ( y ) ≥ 0 w(y) \geq 0 w(y)0,则函数g,
    g(x)=,关于x是凸函数。

    3.2.2 仿射映射复合凸函数

    定理12*:定义g(x)=f(Ax+b),如果f是凸函数,则函数g是凸函数;如果f是凹函数,则函数g是凹函数。

    3.2.6 透视函数

    Def 8 透视函数的定义

    定理13:(1)如果f是凸函数,则f的透视函数g也是凸函数;(2)如果f是凹函数,则f的透视函数g也是凹函数。

    示例
    1.Euclid范数的平方 的透视函数
    2.负对数的透视函数:相对熵、K-L散度、归一化熵

    (二)逐点最大化、最小化

    3.2.3 逐点最大和逐点上确界

    1.逐点最大

    定理14:(1)如果函数 f 1 和 f 2 f_1和f_2 f1f2均为凸函数,则二者的逐点最大函数f(x)=max{ f 1 ( x ) , f 2 ( x ) f_1(x),f_2(x) f1(x),f2(x)}仍然是凸函数;(2)对于凸函数 f 1 , . . . , f m f_1,...,f_m f1,...,fm同样成立。

    示例:
    1.分片线性函数

    定理15:(1)分片线性函数是凸函数;(2)*凸函数可以表示为分片线性函数。

    2.最大r个分量之和

    定理16:最大r个分量之和是凸函数。

    2.逐点上确界

    逐点最大性质扩展至无限个凸函数的逐点上确界

    定理17(一系列凸函数的逐点上确界是凸函数):(1)如果对于任意 y ∈ A y \in A yA,函数f(x,y)关于x都是凸函数,则函数 g ( x ) = s u p y ∈ A f ( x , y ) g(x)=sup_{y \in A}f(x,y) g(x)=supyAf(x,y)关于x也是凸的。(2)一系列凹函数的逐点下确界是凹函数。

    示例:
    1.集合的支撑函数;
    2.到集合中最远的距离;
    3.以权为变量的最小二乘费用函数;
    4.对称矩阵的最大特征值;
    5.矩阵范数:(1)矩阵的二范数(矩阵的最大奇异值);(2)推广至矩阵的一般范数(诱导范数)

    定理18(将凸函数表示成一族仿射函数的逐点上确界):几乎所有的凸函数都可以表示为一族仿射函数的逐点上确界。例如, R n R_n Rn中的凸函数f是它所有仿射全局下估计的逐点上确界。

    3.2.5 最小化

    特殊形式的最小化同样可以得到凸函数

    定理19:如果函数f关于(x,y)是凸函数,集合C是非空凸集,定义函数 g ( x ) = i n f y ∈ C f ( x , y ) g(x)=inf_{y \in C}f(x,y) g(x)=infyCf(x,y)。若存在某个x使得 g ( x ) > − ∞ g(x)>-\infty g(x)>,则函数g关于x是凸函数。

    示例
    1.Schur补的推导;

    定理20:如果矩阵C可逆,称矩阵 A − B C − 1 B T A-BC^{-1}B^T ABC1BT是C在矩阵 ( A B B T C ) \left( \begin{matrix} A & B \\ B^T & C \end{matrix} \right) (ABTBC)中的Schur补。如果该矩阵半正定,则Schur补也半正定。

    2.到某一集合的距离;
    3.h是凸函数,则函数g(x)=inf{h(y)|Ay=x}是凸函数

    (三)复合

    思路:复合函数 f ( x ) = h ( g ( x ) ) , h : R k → R , g : R n → R k f(x)=h(g(x)),h:R_k\to R,g:R_n\to R_k f(x)=h(g(x))h:RkR,g:RnRk保凸时, h ( x ) 和 g ( x ) h(x)和g(x) h(x)g(x)必须满足的条件

    1.标量复合( k = 1 k=1 k=1)

    定理21:对于n=1,假设函数f和g都是二次可微的, d o m g = R , d o m h = R domg=R,domh=R domg=R,domh=R,则:
    (1)如果h是凸函数且非减,g是凸函数,则f是凸函数;
    (2)如果h是凸函数且非增,g是凹函数,则f是凸函数;
    (3)如果h是凹函数且非减,g是凹函数,则f是凹函数;
    (4)如果h是凹函数且非增,g是凸函数,则f是凹函数;

    定理22:对于n>1,无需假设函数f和g可微,其中 h ‾ \overline{h} h是h的扩展值延伸, d o m g = R n , d o m h = R domg=R_n,domh=R domg=Rn,domh=R,有:
    (1)如果h是凸函数且 h ‾ \overline{h} h非减,g是凸函数,则f是凸函数;
    (2)如果h是凸函数且 h ‾ \overline{h} h非增,g是凹函数,则f是凸函数;
    (3)如果h是凹函数且 h ‾ \overline{h} h非减,g是凹函数,则f是凹函数;
    (4)如果h是凹函数且 h ‾ \overline{h} h非增,g是凸函数,则f是凹函数;

    含义 h ‾ \overline{h} h非减的含义
    注意 h ‾ \overline{h} h非减的条件必不可少(反例)。

    2.矢量复合( k ≥ 1 k \geq 1 k1)

    定理23:对于n=1,假设函数f和g都是二次可微的, d o m g = R , d o m h = R k domg=R,domh=R_k domg=R,domh=Rk则:
    (1)如果h是凸函数且在每维分量上h非减, g i g_i gi是凸函数,则f是凸函数;
    (2)如果h是凸函数且在每维分量上h非增, g i g_i gi是凹函数,则f是凸函数;
    (3)如果h是凹函数且在每维分量上h非减, g i g_i gi是凹函数,则f是凹函数;
    (4)如果h是凹函数且在每维分量上h非增, g i g_i gi是凸函数,则f是凹函数;

    定理24:对于n>1,无需假设函数f和g可微,其中 h ‾ \overline{h} h是h的扩展值延伸, d o m g = R n , d o m h = R k domg=R_n,domh=R_k domg=Rn,domh=Rk,有:
    (1)如果h是凸函数且在每维分量上 h ‾ \overline{h} h非减, g i g_i gi是凸函数,则f是凸函数;
    (2)如果h是凸函数且在每维分量上 h ‾ \overline{h} h非增, g i g_i gi是凹函数,则f是凸函数;
    (3)如果h是凹函数且在每维分量上 h ‾ \overline{h} h非减, g i g_i gi是凹函数,则f是凹函数;
    (4)如果h是凹函数且在每维分量上 h ‾ \overline{h} h非增, g i g_i gi是凸函数,则f是凹函数;

    含义 h ‾ \overline{h} h非减的含义: d o m h − R + k = d o m h domh-R^k_+=domh domhR+k=domh
    示例:矢量复合的例子

    3.4 拟凸函数

    (一)拟凸函数的定义

    3.4.2 基本性质

    将拟凸函数的基本性质作为定义

    Def 9 函数f是拟凸函数的充要条件是domf是凸集,且对于任意 x , y ∈ d o m f x,y\in domf x,ydomf 0 ≤ θ ≤ 1 0\leq θ \leq 1 0θ1,有 f ( θ x + ( 1 − θ ) y ) ≤ m a x f(θx+(1-θ)y)\leq max f(θx+(1θ)y)max{ f ( x ) , f ( y ) f(x),f(y) f(x),f(y)}。也就是说,线段中任意一点的函数值不超过其端点函数值中最大的那个。

    示例
    1.非零向量的基数;
    2.半正定矩阵的秩;

    (二)拟凸函数的性质

    3.4.1 定义及例子(下水平集)

    定理25(拟凸函数等价于下水平集是凸集):函数 f : R n → R f:R_n\to R fRnR是拟凸函数,如果其定义域及其所有下水平集 S α S_α Sα={ x ∈ d o m f ∣ f ( x ) ≤ α x\in domf|f(x)\leqα xdomff(x)α}。

    ps.1.拟线性函数的定义;2.凸函数是拟凸函数。

    R R R上的拟凸函数示例
    1.对数函数是拟线性函数;
    2.上取值函数是拟线性函数;
    :拟线性函数可能是凹函数,也可能不连续。

    R n R_n Rn上的拟凸函数示例
    1.向量的长度是拟凸函数;
    2. f ( x 1 , x 2 ) = x 1 x 2 f(x_1,x_2)=x_1x_2 f(x1,x2)=x1x2是拟凹函数;
    3.线性分式函数是拟线性函数;
    4.距离比函数是拟凸函数;
    5.内生回报率:(1)贴现的概念;(2)内生回报率是拟凹函数。

    3.4.5 通过一族凸函数表示拟凸函数的下水平集

    定理26:可以将拟凸函数f的下水平集表示为凸函数的不等式:选择一族凸函数 Φ t : R n → R , t ∈ R Φ_t:R_n\to R,t\in R Φt:RnR,tR表示凸函数的编号,这些函数满足 f ( x ) ≤ t f(x)\leq t f(x)t等价于 Φ t ≤ 0 Φ_t\leq 0 Φt0,即拟凸函数f的t-下水平集是凸函数 Φ t Φ_t Φt的0-下水平集。

    示例:凸凹函数之比是拟凸函数

    3.4.2 基本性质(直线上的性质)

    定理27(拟凸性由函数在直线上的性质刻画) :函数f是拟凸的充要条件是它在和其定义域相交的任意直线上是拟凸函数。

    定理28(R上的拟凸函数的刻画):f是R的拟凸函数,则该函数满足以下一个条件(1)函数f是单调的;(2)存在一点 c ∈ d o m f c\in domf cdomf,使得对于 t ≤ c t\leq c tc(且 t ∈ d o m f t\in domf tdomf),f非增,对于 t ≥ c t\geq c tc(且 t ∈ d o m f t\in domf tdomf),f非减。

    (三)可微拟凸函数的充要条件

    一阶条件

    定理29(等价):函数 f : R n → R f:R_n\to R fRnR可微,则函数f是拟凸的充要条件是: d o m f dom f domf是凸集,且对于任意 x , y ∈ x,y \in x,y domf有f(y) ≤ \leq f(x) ⇒ \Rightarrow ∇ f ( x ) T ( y − x ) ≤ 0 \nabla f(x)^T(y-x)\leq0 f(x)T(yx)0

    ps:1.一阶条件的几何含义;2.凸性一阶条件和拟凸性一阶条件的区别。

    二阶条件

    定理30(不等价):假设函数f二次可微,(1)如果函数f是拟凸函数,则对于任意 x ∈ d o m f x\in domf xdomf以及任意 y ∈ R n y\in R_n yRn y T ∇ f ( x ) = 0 y^T\nabla f(x)=0 yTf(x)=0 ⇒ \Rightarrow y T ∇ 2 f ( x ) y ≥ 0 y^T\nabla^2 f(x)y\geq0 yT2f(x)y0
    (2)如果对于任意 x ∈ d o m f x\in domf xdomf,以及任意 y ∈ R n y\in R^n yRn,函数f满足
    y T ∇ f ( x ) = 0 y^T\nabla f(x)=0 yTf(x)=0 ⇒ \Rightarrow y T ∇ 2 f ( x ) y > 0 y^T\nabla^2 f(x)y>0 yT2f(x)y>0,则函数f是拟凸函数。

    (四)保拟凸运算

    1. 非负加权最大

    (1)非负加权最大

    定理31:f=max{ w 1 f 1 , . . . , x m f m w_1f_1,...,x_mf_m w1f1,...,xmfm},其中 w i ≥ 0 , f i w_i\geq 0,f_i wi0,fi是拟凸函数,则函数f是拟凸函数。

    (2)逐点上确界

    推论32 f ( x ) = s u p y ∈ C ( w ( y ) g ( x , y ) ) f(x)=sup_{y\in C}(w(y)g(x,y)) f(x)=supyC(w(y)g(x,y)),其中 w ( y ) ≥ 0 w(y)\geq 0 w(y)0,固定任意y,g(x,y)关于x是拟凸函数。

    示例:最大广义特征值是拟凸函数

    2. 复合

    定理33:如果函数 g : R n → R g:R_n\to R g:RnR是拟凸函数,且函数 h : R → R h:R\to R h:RR是非减的,则复合函数f=h(g)是拟凸函数。

    示例:拟凸函数和一个仿射函数或线性分式函数复合得到拟凸函数

    3. 最小化

    定理34:如果函数f(x,y)是x和y的联合拟凸函数,且C是凸集,则函数 g ( x ) = i n f y ∈ C f ( x , y ) g(x)=inf_{y\in C}f(x,y) g(x)=infyCf(x,y)是拟凸函数。

    3.5 对数凸函数

    3.5.1 对数凸函数的定义

    Def 10 对数凸函数的定义

    定理35(对数凸函数的等价定义):函数 f : R n → R f:R_n\to R fRnR,其定义域是凸集,且对于任意 x ∈ d o m f x\in domf xdomf 有f(x)>0,函数是对数凸函数,当且仅当对任意 x , y ∈ d o m f , 0 ≤ θ ≤ 1 x,y\in domf,0\leqθ\leq1 x,ydomf,0θ1,有 f ( θ x + ( 1 − θ ) y ) ≥ f ( x ) θ f ( y ) 1 − θ f(θx+(1-θ)y)\geq f(x)^θ f(y)^{1-θ} f(θx+(1θ)y)f(x)θf(y)1θ

    定理36(凸函数、拟凸函数、对数凸函数的关系)*:(1)对数凸函数 ⊂ \subset 凸函数 ⊂ \subset 拟凸函数;
    (2)非负凹函数 ⊂ \subset 对数凹函数 ⊂ \subset 拟凹函数。

    示例
    1.仿射函数;
    2.幂函数;
    3.指数函数;
    4.Guass概率密度函数的累积分布函数;
    5.Gamma函数;
    6.行列式;
    7.行列式与迹的比;
    8.对数凹函数的概率密度函数:多变量正态分布概率密度函数、指数分布的概率密度函数、凸集C上均匀分布的概率密度函数、Wishart分布

    3.5.2 相关性质

    (一)可微对数-凸函数的性质

    定理37(二次可微的对数-凸/凹函数):函数f二次可微,其中domf是凸集,函数f是对数-凸函数等价于 ∇ 2 l o g f ( x ) = 1 f ( x ) ∇ 2 f ( x ) − 1 f ( x ) 2 ∇ f ( x ) ∇ f ( x ) T ≥ 0 \nabla^2logf(x)=\frac{1}{f(x)}\nabla^2f(x)-\frac{1}{f(x)^2}\nabla f(x)\nabla f(x)^T\geq 0 2logf(x)=f(x)12f(x)f(x)21f(x)f(x)T0

    (二)保凸运算

    1.乘积运算

    定理38(乘积) :对数凸以及对数凹对乘积以及正的伸缩运算是封闭的。

    2.求和运算

    定理39(求和):(1)*对数凹函数的和一般不是对数凹函数;(2)对数凸函数的和是对数凸函数。

    3.积分运算(求和运算的推论)

    定理40(积分)(1)对数凸函数的积分:如果对于任意 y ∈ C , f ( x , y ) y\in C,f(x,y) yCf(x,y)是x的对数凸函数,则函数 g ( x ) = ∫ C f ( x , y ) d y g(x)=\int_Cf(x,y)dy g(x)=Cf(x,y)dy是对数凸函数;
    (2)对数凹函数的积分:在一些特殊情况下对数凹函数的在积分后的性质可以保留。即:如果函数 f : R n × R m → R f:R_n\times R_m\to R f:Rn×RmR是对数凹函数,则函数 g ( x ) = ∫ f ( x , y ) d y g(x)=\int f(x,y)dy g(x)=f(x,y)dy R n R_n Rn上是x的对数凹函数;

    推论41:(1)对数凹函数的概率密度分布函数的边际分布是对数凹函数;(2)对数凹函数对卷积是封闭的;(3)设 C ⊂ R n C\subset R_n CRn是凸集,w是 R n R_n Rn上的随机向量,设其具有对数凹的概率密度函数p,则函数f(x)=prob( x + w ∈ C x+w\in C x+wC)是x的对数凹函数。

    示例
    1.概率密度函数的累积分布函数;
    2.产生函数;
    3.多面体的体积

    3.3 共轭函数

    3.3.1 定义及示例

    Def 12 共轭函数的定义、几何含义

    定理42:共轭函数是凸函数。

    示例
    1.R上凸函数的共轭函数;
    (1)仿射函数;
    (2)负对数函数;
    (3)指数函数;
    (4)负熵函数;
    (5)反函数
    2.严格凸的二次函数;
    3.对数-行列式;
    4.示性函数:支撑函数;
    5.指数和的对数函数;
    6.范数:对偶范数单位球的示性函数;
    7.范数的平方;
    8.总收入和收益函数

    3.3.2 基本性质

    (一)共轭的共轭

    1.Fenchel不等式

    定理43(Fenchel不等式):对于任意x和y,如下不等式成立 f ( x ) + f ∗ ( y ) ≥ x T y f(x)+f^*(y)\geq x^Ty f(x)+f(y)xTy,该不等式称为Fenchel不等式。

    推论44(Young不等式)
    在这里插入图片描述
    加粗样式
    用的Young不等式*:令 f ( x ) = x p − 1 f(x)=x^{p-1} f(x)=xp1,g(x)= x 1 p − 1 x^{\frac{1}{{p-1}}} xp11,可得
    在这里插入图片描述

    2.共轭的共轭

    定理45*:如果函数f是闭的凸函数,则f**=f

    (二)可微函数的共轭

    定理46:可微函数的共轭称为f的Legendre变换,设函数f是凸函数且可微, f ∗ ( y ) = x ∗ T ∇ f ( x ∗ ) − f ( x ∗ ) f^*(y)=x^{*T}\nabla f(x^*)-f(x^*) f(y)=xTf(x)f(x)

    (三)变换下的共轭函数

    1.伸缩变换

    定理47:若a>0以及 b ∈ R b \in R bR,g(x)=af(x)+b的共轭函数为 g ∗ ( y ) = a f ∗ ( y / a ) − b g^*(y)=af^*(y/a)-b g(y)=af(y/a)b

    2.复合仿射变换

    定理48:设 A ∈ R n × n A\in R_{n\times n} ARn×n非奇异, b ∈ R n b\in R_n bRn,则函数g(x)=f(Ax+b)的共轭函数, g ∗ ( y ) = f ∗ ( A − T y ) − b T A − T y g^*(y)=f^*(A^{-T}y)-b^TA^{-T}y g(y)=f(ATy)bTATy

    3.独立函数的和

    定理49:独立凸函数的和的共轭函数是各个凸函数的共轭函数的和。

    3.6 关于广义不等式的凸性

    3.6.1 单调函数(广义不等式下)

    Def 13 广义不等式的单调性
    示例
    1.单调向量函数;
    2.矩阵单调函数;

    定理50(等价定义:单调性的梯度条件):可微函数f,其定义域是凸集,它是K-非减的,当且仅当,对于任意 x ∈ d o m f x\in domf xdomf,有 ∇ f ( x ) ≥ K ∗ 0 \nabla f(x)\geq_{K^*} 0 f(x)K0

    3.6.2 凸函数(广义不等式下)

    (一)定义及示例

    Def 14 K-凸函数、严格K-凸函数的定义
    示例
    1.关于分量不等式的凸性;
    2.矩阵凸性;

    定理51*:矩阵凸性的等价定义是对于任意向量z,标量函数 z T f ( x ) z z^Tf(x)z zTf(x)z都是凸函数

    (二)性质

    1. K-凸函数的判定

    定理52(直线上的性质):函数是K-凸的,当且仅当它在定义域上的任意直线上是K-凸的。

    定理53(广义不等式的对偶):(1)函数f是K-凸的,当且仅当对任意 w ≥ K ∗ 0 w\geq_{K^*}0 wK0,函数 w T f w^Tf wTf是凸的;
    (2)函数f是严格K-凸的,当且仅当对任意非零向量 w ≥ K ∗ 0 w\geq_{K^*}0 wK0,函数 w T f w^Tf wTf是严格凸的。

    定理54(可微的K-凸函数):(1)可微函数f是K-凸的,当且仅当其定义域是凸集,且对于任意 x , y ∈ d o m f x,y\in domf x,ydomf f ( y ) ≥ K f ( x ) + D f ( x ) ( y − x ) f(y)\geq_Kf(x)+Df(x)(y-x) f(y)Kf(x)+Df(x)(yx)
    (2)可微函数f是严格K-凸的,当且仅当其定义域是凸集,且对于任意 x , y ∈ d o m f x,y\in domf x,ydomf x ≠ y x\neq y x=y f ( y ) > K f ( x ) + D f ( x ) ( y − x ) f(y)>_Kf(x)+Df(x)(y-x) f(y)>Kf(x)+Df(x)(yx)

    2. 复合定理

    定理55:如果函数 g : R n → R p g:R_n\to R_p g:RnRp是K-凸的,函数 h : R p → R h:R_p\to R h:RpR是凸的, h ‾ \overline h h是K-非减的,那么函数h(g)是凸的。

    展开全文
  • 提出了一类求解非凸函数极小的修正Broyden算法,并在较弱条件下,即假设目标函数二阶连续可微,其梯度满足Lipschitz条件,采用非单调Wolfe线性搜索确定步长,证明了所提出的修正Broyden算法的全局收敛
  • 文章目录1 基本性质和例子2 保留凸性的运算3 共轭函数4 拟凸函数5 对数凹/对数凸函数6 关于广义不等关系的凸性参考资料 1 基本性质和例子 定义\large\color{#70f3ff}{\boxed{\color{brown}{定义 } }}定义​ 一个函数...


    最优化知识笔记整理汇总,超级棒

    1 基本性质和例子

    定 义 \large\color{#70f3ff}{\boxed{\color{brown}{定义 } }}

    一个函数 f : R n → R f: R^n\rightarrow R f:RnR 是凸的,如果定义域 d o m   f dom\,f domf 是凸集,并且对于所有 x , y ∈ f , θ ≤ 1 x,y\in f, \theta\leq 1 x,yf,θ1 ,我们有
    f ( θ x + ( 1 − θ ) y ) ≤ θ f ( x ) + ( 1 − θ ) f ( y ) (1) f(\theta x+(1-\theta)y)\leq \theta f(x)+(1-\theta)f(y)\tag1 f(θx+(1θ)y)θf(x)+(1θ)f(y)(1)

    几何解释:点 ( x , f ( x ) ) (x,f(x)) (x,f(x)) ( y , f ( y ) ) (y,f(y)) (y,f(y)) 之间的线段在 f f f 对应的图像上方。

    img

    凸 函 数 的 图 表 示 。 函 数 上 任 意 两 点 之 间 的 弦 ( 即 线 段 ) 位 于 函 数 的 上 方 。 凸函数的图表示。函数上任意两点之间的弦(即线段)位于函数的上方。 (线)

    • 函数 f f f严格凸的,则不等式(1)在 x ≠ y x\ne y x=y ,且 0 < θ < 1 0<\theta <1 0<θ<1 时严格成立.

    • 函数 f f f的,当 − f -f f 是凸的,严格凹,当 − f -f f 是严格凸的。

    • 仿射函数既是凸的也是凹的,反过来,既凹又凸的函数是仿射的。

    • 一个函数 f f f 是凸的当且仅当对任意 x ∈ d o m   f x\in dom\,f xdomf 和任意 v v v ,函数 g ( t ) = f ( x + t v ) g(t)=f(x+tv) g(t)=f(x+tv) 是凸的, { t ∣ x + t v ∈ d o m   f } . \{t|x+tv\in dom\,f\}. {tx+tvdomf}.这个性质非常有用,因为它允许我们通过将一个函数限定为一条直线来检查它是否为凸函数。

    • 函数 f ( x ) : C → R f (x): C→R f(x):CR,其中 C C C是非空凸集,如果是凹函数,则有
      f ( θ x + ( 1 − θ ) y ) ≥ θ f ( x ) + ( 1 − θ ) f ( y ) f(\theta x+(1-\theta)y)\geq \theta f(x)+(1-\theta)f(y) f(θx+(1θ)y)θf(x)+(1θ)f(y)

    一个凸函数在其域的相对内部是连续的;它只能在其相对边界上有不连续。

    扩 展 值 扩 展 \large\color{#70f3ff}{\boxed{\color{brown}{扩展值扩展 } }}

    将凸函数扩展到整个 R n R^n Rn ,通常令它在定义域之外取 ∞ \infty 。如果 f f f 是凸函数那么它的拓展为 f ~ : R n → R ∪ { ∞ } \widetilde{f} : R^n\rightarrow R \cup \{\infty\} f :RnR{} ,扩展值定义:
    f ~ ( x ) = { f ( x )      x ∈ d o m f ∞      x ∉ d o m f \widetilde{f}(x)=\left \{\begin{aligned} f(x)\;\; x\in domf\\ \infty\;\; x\not\in domf \end{aligned}\right. f (x)={f(x)xdomfxdomf
    如果函数 f : R n → R f: \textbf{R}^n \rightarrow \textbf{R} f:RnR 是凹函数,定义其延拓(extended-value extentions)为 f ~ : R n → R ∪ { − ∞ } \tilde{f}: \textbf{R}^n \rightarrow \textbf{R} \cup \{ -\infty\} f~:RnR{} :
    f ~ ( x ) = { f ( x ) x ∈ dom f − ∞ x ∉ dom f . \tilde{f}(x) =\left\{\begin{array}{ll} f(x) &x \in \textbf{dom}f\\ -\infty &x \notin \textbf{dom}f. \end{array}\right. f~(x)={f(x)xdomfx/domf.
    这样拓展后,不需要每次指出 x ∈ dom f x \in \textbf{dom}f xdomf

    一 阶 条 件 \large\color{#70f3ff}{\boxed{\color{brown}{一阶条件 } }}

    令函数 f f f 是可微的(也就是它的梯度 ∇ f \nabla f f 在开集的 d o m   f dom\,f domf每个点上都存在)。那么 f f f 是凸的,充要条件是 d o m   f dom\,f domf是凸的,并且对所有的 x , y ∈ d o m   f x,y\in dom~f x,ydom f 有:

    f ( y ) ≥ f ( x ) + ∇ f ( x ) T ( y − x ) (2) f(y)\geq f(x)+\nabla f(x)^T(y-x)\tag{2} f(y)f(x)+f(x)T(yx)(2)

    在每个点上,函数图像都高于在该点的切线。

    img

    如果 f f f是凸可微的,对所有的 x , y ∈ d o m   f x,y\in dom~f x,ydom f f ( x ) + ∇ f ( x ) T ( y − x ) ≤ f ( y ) f(x)+\nabla f(x)^T(y-x)\leq f(y) f(x)+f(x)T(yx)f(y)

    解释: y y y 的仿射函数 f ( x ) + ∇ f ( x ) T ( y − x ) f(x)+\nabla f(x)^T(y-x) f(x)+f(x)T(yx) f f f 在靠近 x x x 处的一阶泰勒近似。(2)不等式表达了这个一阶泰勒近似是函数的全局下限(global underestimator),反过来,如果函数的一阶泰勒近似总是函数的全局下限,那么这个函数是凸的。

    • 如果 ∇ f ( x ) = 0 \nabla f(x)=0 f(x)=0 ,那么对于所有 y ∈ d o m   f y\in dom~f ydom f ,有 f ( y ) ≥ f ( x ) f(y)\geq f(x) f(y)f(x) , 也就是在 x x x f f f 取到全局最小值 x x x 是全局最小值)。

    f f f严格凸的,当且仅当 d o m   f dom\,f domf是凸的,且对于所有 x , y ∈ d o m f , x ≠ y x,y\in domf, x\ne y x,ydomf,x=y
    f ( y ) > f ( x ) + ∇ f ( x ) T ( y − x ) (3) f(y)>f(x)+\nabla f(x)^T(y-x)\tag3 f(y)>f(x)+f(x)T(yx)(3)

    • 函数 f f f 是凹函数的充要条件是** dom f \textbf{dom}f domf 是凸集且对 ∀ x , y ∈ dom   f \forall x,y \in \textbf{dom}~f x,ydom f**均有
      f ( y ) ≤ f ( x ) + ∇ f ( x ) T ( y − x ) (4) f(y)\leq f(x)+\nabla f(x)^T(y-x) \tag4 f(y)f(x)+f(x)T(yx)(4)

    二 阶 条 件 \large\color{#70f3ff}{\boxed{\color{brown}{二阶条件 } }}

    设函数 f f f 是二阶可微的,也就是它在开集 d o m   f dom~f dom f 的每个点上都存在二阶导数 ∇ 2 f \nabla^2 f 2f。那么 是凸的 f f f充要条件是它的二阶导数是半正定的: ∀ x ∈ d o m f \forall x\in domf xdomf
    ∇ 2 f ( x ) ⪰ 0 (5) \nabla^2f(x)\succeq 0\tag{5} 2f(x)0(5)
    假设 S S S是一个非空开凸集,且 f ( x ) : S → R f (x): S→R f(x):SR是二阶可微的。设 H ( x ) H(x) H(x)表示 f ( x ) f (x) f(x) H e s s i a n Hessian Hessian,则当且仅当 H ( x ) H(x) H(x)对所有 x ∈ S x∈S xS是正半定时, f ( x ) f (x) f(x)是一个凸函数。

    几何解释:函数图像在每个定义域的每个点上都有正的曲率(curvature)。

    • 函数 f f f的,充要条件是 是 d o m   f dom~f dom f凸的,并且 ∇ 2 f ( x ) ⪯ 0 \nabla^2f(x)\preceq 0 2f(x)0 , ∀ x ∈ d o m   f \forall x\in dom~f xdom f
    • 如果 ∀ x ∈ d o m   f \forall x\in dom~f xdom f , ∇ 2 f ( x ) ≻ 0 \nabla^2f(x)\succ 0 2f(x)0 ,那么 是* f f f*严格凸的。反过来不成立,例如 f ( x ) = x 4 f(x)=x^4 f(x)=x4 是严格凸的,但是在 x = 0 x=0 x=0 处二阶导数为 0 0 0 .

    例 子 \large\color{#70f3ff}{\boxed{\color{brown}{例子 } }}

    R R R :

    • e a x , ∀ a ∈ R e^{a x}, \forall a \in R eax,aR, 在 R R R 上凸。
    • x a x^{a} xa, 当 a ≥ 1 a \geq 1 a1 a ≤ 0 a \leq 0 a0, 在 R + + R_{++} R++ 上凸, 当 0 ≤ a ≤ 1 0 \leq a \leq 1 0a1 时凹。
    • ∣ x ∣ p , p ≥ 1 |x|^{p}, p \geq 1 xp,p1, 在R上凸。
    • log ⁡ x \log x logx, 在 R + + R_{++} R++ 上凸。
    • 负嫡 x log ⁡ x x \log x xlogx, 在 R + R_{+} R+ R + + R_{++} R++ 上凸。

    R n R^{n} Rn

    • 范数,凸
    • 最大值函数,凸
    • 二次方程函数: f ( x , y ) = x 2 / y f(x,y)=x^2/y f(x,y)=x2/y d o m   f = R × R + + = { ( x , y ) ∈ R n ∣ y > 0 } dom~f=R\times R_{++}=\{(x,y)\in R^n| y>0\} dom f=R×R++={(x,y)Rny>0} , 凸。
    • f ( x ) = l o g ( e x 1 + . . . + e x n ) f(x)=log(e^{x_1}+...+e^{x_n}) f(x)=log(ex1+...+exn) , 凸。
    • 几何平均 f ( x ) = ( ∏ i = 1 n x i ) 1 / n f(x)=\left(\prod_{i=1}^{n} x_{i}\right)^{1 / n} f(x)=(i=1nxi)1/n, 在 R + + n R_{++}^{n} R++n 上凹。
    • f ( X ) = log ⁡ det ⁡ X f(X)=\log \operatorname{det} X f(X)=logdetX, 在 S + + n S_{++}^{n} S++n 上凹。

    子 层 集 \large\color{#70f3ff}{\boxed{\color{brown}{子层集 } }}

    函数 f : R n → R f:R^n\rightarrow R f:RnR 的一个 α − 子 层 集 \alpha -子层集 α
    C α = { x ∈ d o m f ∣ f ( x ) ≤ α } (6) C_{\alpha}=\{x\in domf | f(x)\leq \alpha\}\tag{6} Cα={xdomff(x)α}(6)

    • 凸函数的子层集是凸集,对于所有的 α \alpha α 。反过来不对,例如 f ( x ) = − e x f(x)=-e^x f(x)=ex R R R 上不是凸的,但是它的所有子层集都是凸集。
    • 凹函数 f : R n → R f: \mathbf{R}^{n} \rightarrow \mathbf{R} f:RnR α − \alpha- α 超水平集 被定义为 { x ∈ dom ⁡ f ∣ f ( x ) ≥ α } \{x \in \operatorname{dom} f \mid f(x) \geq \alpha\} {xdomff(x)α}, 也就是定义域中使得函数值不小于 α \alpha α 的元素的集合。

    对于凹函数, α \alpha α 取任意值时的 α − \alpha- α 超水平集均为凸集。反过来不成立!

    图 \large\color{#70f3ff}{\boxed{\color{brown}{图 } }}

    一个函数 f : R n → R f: R^{n} \rightarrow R f:RnR 的图像是
    { ( x , f ( x ) ) ∣ x ∈ dom ⁡ f } (7) \{(x, f(x)) \mid x \in \operatorname{dom} f\}\tag{7} {(x,f(x))xdomf}(7)
    它是 R n + 1 R^{n+1} Rn+1 的子集。定义函数 f f f 的, R n → R R^{n} \rightarrow R RnR :

    上境图: e p i    f = { ( x , t ) ∣ x ∈ d o m f , f ( x ) ≤ t } epi\; f = \{(x,t)| x\in dom f , f(x)\leq t\} epif={(x,t)xdomf,f(x)t}

    下境图: h y p o    f = { ( x , t ) ∣ t ≤ f ( x ) } hypo\;f = \{(x,t)| t\leq f(x)\} hypof={(x,t)tf(x)}

    • 函数是凸的当且仅当它的上境图是一个凸集。
    • 函数是凹的当且仅当它的下境图是一个凸集。

    img

    函 数 f 的 上 境 图 , 用 阴 影 表 示 。 下 界 的 颜 色 更 深 , 是 f 的 图 像 。 函数f的上境图,用阴影表示。下界的颜色更深,是f的图像。 ff

    J e n s e n 不 等 式 及 其 拓 展 \large\color{#70f3ff}{\boxed{\color{brown}{ Jensen不等式及其拓展} }} Jensen

    基本不等式 ( 1 ) (1) (1)
    f ( θ x + ( 1 − θ ) y ) ≤ θ f ( x ) + ( 1 − θ ) f ( y ) (8) f(\theta x+(1-\theta) y) \leq \theta f(x)+(1-\theta) f(y)\tag{8} f(θx+(1θ)y)θf(x)+(1θ)f(y)(8)
    有时被叫做Jensen不等式。

    • 它可以拓展到多个点的凸组合:

    如果 f f f 是凸的, x 1 , … , x k ∈ dom ⁡ f , θ 1 , … , θ k ≥ 0 , θ 1 + … + θ k = 1 x_{1}, \ldots, x_{k} \in \operatorname{dom} f, \theta_{1}, \ldots, \theta_{k} \geq 0, \theta_{1}+\ldots+\theta_{k}=1 x1,,xkdomf,θ1,,θk0,θ1++θk=1 那么
    f ( θ 1 x 1 + … + θ k x k ) ≤ θ 1 f ( x 1 ) + … + θ k f ( x k ) (9) f\left(\theta_{1} x_{1}+\ldots+\theta_{k} x_{k}\right) \leq \theta_{1} f\left(x_{1}\right)+\ldots+\theta_{k} f\left(x_{k}\right)\tag{9} f(θ1x1++θkxk)θ1f(x1)++θkf(xk)(9)
    还可以拓展到无限和,积分,期望:

    积分: 如果 p ( x ) ≥ 0 p(x) \geq 0 p(x)0 S ⊆ dom ⁡ f S \subseteq \operatorname{dom} f Sdomf 上, ∫ S p ( x ) d x = 1 \int_{S} p(x) d x=1 Sp(x)dx=1, 那么
    f ( ∫ S p ( x ) d x ) ≤ ∫ S f ( x ) p ( x ) d x f\left(\int_{S} p(x) d x\right) \leq \int_{S} f(x) p(x) d x f(Sp(x)dx)Sf(x)p(x)dx
    期望: 如果 x x x 是随机变量, x ∈ d o m f x \in d o m f xdomf 的概率为1,且 f f f 是凸函数,那么有
    f ( E x ) ≤ E f ( x ) f(E x) \leq E f(x) f(Ex)Ef(x)
    如果 f f f不凸,有一个 x x x 是随机变量, x ∈ d o m f x \in d o m f xdomf 的概率为 1, 使得 f ( E x ) > E f ( x ) f(E x)>E f(x) f(Ex)>Ef(x).

    Jensen不等式简单的一种:
    f ( x + y 2 ) ≤ f ( x ) + f ( y ) 2 f\left(\frac{x+y}{2}\right) \leq \frac{f(x)+f(y)}{2} f(2x+y)2f(x)+f(y)
    其 他 不 等 式 \large\color{#70f3ff}{\boxed{\color{brown}{ 其他不等式} }}

    很多关于凸函数的不等式都可以由Jensen不等式导出。例如:

    均值不等式: a b ≤ a + b 2 \quad \sqrt{a b} \leq \frac{a+b}{2} ab 2a+b,

    Hölder不等式: 对于 p > 1 , 1 p + 1 q = 1 , x , y ∈ R n p>1, \quad \frac{1}{p}+\frac{1}{q}=1, \quad x, y \in \mathbf{R}^{n} p>1,p1+q1=1,x,yRn, 有
    ∑ i = 1 n x i y i ≤ ( ∑ i = 1 n ∣ x i ∣ p ) 1 p ( ∑ i = 1 n ∣ y i ∣ q ) 1 q \sum_{i=1}^{n} x_{i} y_{i} \leq\left(\sum_{i=1}^{n}\left|x_{i}\right|^{p}\right)^{\frac{1}{p}}\left(\sum_{i=1}^{n}\left|y_{i}\right|^{q}\right)^{\frac{1}{q}} i=1nxiyi(i=1nxip)p1(i=1nyiq)q1

    2 保留凸性的运算

    非 负 加 权 和 \large\color{#70f3ff}{\boxed{\color{brown}{ 非负加权和} }}

    如果 f 1 , . . . , f m f_1,...,f_m f1,...,fm 是凸函数,他们的集合是一个凸锥——凸函数的非负加权和 f = w 1 f 1 + . . . + w m f m , ( w 1 , . . . , w m ≥ 0 ) f=w_1f_1+...+w_mf_m, (w_1,...,w_m\geq 0) f=w1f1+...+wmfm(w1,...,wm0) 是凸的。

    • 还可以拓展到积分:如果 f ( x , y ) f(x,y) f(x,y) 对于 x x x是凸的,对于每个 y ∈ A y\in A yA ,且 w ( y ) ≥ 0 w(y)\geq 0 w(y)0, ∀ y ∈ A \forall y\in A yA ,那么函数 g ( x ) = ∫ A w ( y ) f ( x , y ) d y g(x)=\int_A w(y)f(x,y)dy g(x)=Aw(y)f(x,y)dy 对于 x x x 是凸的。

    与 仿 射 函 数 的 复 合 \large\color{#70f3ff}{\boxed{\color{brown}{ 与仿射函数的复合} }} 仿

    f : R n → R , A ∈ R n × m , b ∈ R f: R^{n} \rightarrow R, A \in R^{n \times m}, b \in R f:RnR,ARn×m,bR 。定义 g : R m → R g: R^{m} \rightarrow R g:RmR
    g ( x ) = f ( A x + b ) , d o m g = { a ∣ A x + b ∈ dom ⁡ f } (10) g(x)=f(A x+b), domg=\{a \mid A x+b \in \operatorname{dom} f\}\tag{10} g(x)=f(Ax+b),domg={aAx+bdomf}(10)
    那么如果 f f f 是凸函数, g g g 也是凸函数。

    逐 点 最 大 p o i n t w i s e    m a x i m u m \large\color{#70f3ff}{\boxed{\color{brown}{ 逐点最大 pointwise \ \ maximum} }} pointwise  maximum

    如果 f 1 , f 2 f_{1}, f_{2} f1,f2 是凸函数,那么他们的逐点最大 f f f, 定义为
    f ( x ) = max ⁡ { f 1 ( x ) , f 2 ( x ) } (11) f(x)=\max \left\{f_{1}(x), f_{2}(x)\right\}\tag{11} f(x)=max{f1(x),f2(x)}(11)
    定义域 d o m f = dom ⁡ f 1 ∩ d o m f 2 d o m f=\operatorname{dom} f_{1} \cap d o m f_{2} domf=domf1domf2 . f f f也是凸集。可以拓展到多个凸函数的逐点最大。

    逐 点 上 确 界 p o i n t w i s e    s u p r e m u m \large\color{#70f3ff}{\boxed{\color{brown}{ 逐点上确界 pointwise \ \ supremum} }} pointwise  supremum

    如果对于每个 y ∈ A , f ( x , y ) y \in A, f(x, y) yA,f(x,y) 关于 x x x 是凸的, 那么函数
    g ( x ) = sup ⁡ y ∈ A f ( x , y ) (12) g(x)=\sup _{y \in A} f(x, y)\tag{12} g(x)=yAsupf(x,y)(12)
    关于 x x x 是凸的。 g g g 的定义域是
    d o m g = { x ∣ ( x , y ) ∈ d o m f , ∀ y ∈ A , s u p y ∈ A f ( x , y ) < ∞ } dom g=\{x|(x,y)\in dom f, \forall y\in A, \underset{y\in A}{sup}f(x,y)<\infty\} domg={x(x,y)domf,yA,yAsupf(x,y)<}

    • 类似地,一组凹函数的逐点下确界是凹函数。
    • e p i   g = ⋂ y ∈ A e p i   f ( ⋅ , y ) epi\, g =\bigcap _ {y\in A}epi \, f(\cdot,y) epig=yAepif(,y) .

    最 小 化 \large\color{#70f3ff}{\boxed{\color{brown}{ 最小化} }}

    如果 f f f 关于 ( x , y ) (x, y) (x,y) 是凸函数,并且 C C C 是非空凸集,那么函数
    g ( x ) = inf ⁡ g ∈ C f ( x , y ) (13) g(x)=\inf _{g \in C} f(x, y)\tag{13} g(x)=gCinff(x,y)(13)
    是关于 x x x 的凸函数,对于所有的 x x x g ( x ) > − ∞ g(x)>-\infty g(x)> 的定义域是 d o m f d o m f domf x x x 轴的投影:
    d o m g = { x ∣ ( x , y ) ∈ d o m f , for some y ∈ C } (14) dom g=\{x| (x,y)\in domf, \text{for some y} \in C\}\tag{14} domg={x(x,y)domf,for some yC}(14)
    函 数 的 透 视 \large\color{#70f3ff}{\boxed{\color{brown}{ 函数的透视} }}

    函数 f : R n → R , f f: R^{n} \rightarrow R, \quad f f:RnR,f 的透视函数为
    g : R n + 1 → R , g ( x , t ) = t f ( x / t ) d o m g = { ( x , t ) ∣ x / t ∈ d o m f , t > 0 } (15) g: R^{n+1} \rightarrow R, \quad g(x, t)=t f(x / t)\\ d o m g=\{(x, t) \mid x / t \in d o m f, t>0\}\tag{15} g:Rn+1R,g(x,t)=tf(x/t)domg={(x,t)x/tdomf,t>0}(15)
    透视运算保存凸性:如果函数 f f f 是凸的, 那么它的透视函数 g g g 也是凸的; 如果 f f f 是凹的, 那 么 g g g 也是凹的。

    3 共轭函数

    定 义 和 例 子 \large\color{#70f3ff}{\boxed{\color{brown}{ 定义和例子} }}

    f : R n → R f: R^{n} \rightarrow R f:RnR 函数 f ∗ : R n → R f^{*}: R^{n} \rightarrow R f:RnR 定义为
    f ∗ ( y ) = sup ⁡ x ∈  domf  ( y T x − f ( x ) ) (16) f^{*}(y)=\sup _{x \in \text { domf }}\left(y^{T} x-f(x)\right)\tag{16} f(y)=x domf sup(yTxf(x))(16)
    叫做函数 f f f共轭

    共轭函数的定义域 由使得上述上确界有限的 y , y ∈ R n y, y \in R^{n} y,yRn 组成。也就是说在 dom ⁡ f \operatorname{dom} f domf y T x − f ( x ) y^{T} x-f(x) yTxf(x) 是有界的。如图:

    img

    共 轭 函 数 f ∗ ( y ) 为 线 性 函 数 x y 与 f ( x ) 之 间 的 最 大 间 隙 , 如 图 虚 线 所 示 。 如 果 f 是 可 微 的 , 它 发 生 在 点 x 处 f ′ ( x ) = y 。 共轭函数f^∗(y) 为线性函数xy与f(x)之间的最大间隙,如图虚线所示。如果f是可微的,它发生在点x处f′(x) = y。 f(y)线xyf(x)线fxf(x)=y

    • 共轭函数 f ∗ f^* f 是凸的,因为它是关于 y 的凸函数的逐点上确界,这一点为真不论 f f f 是否是凸的。

    基 本 性 质 \large\color{#70f3ff}{\boxed{\color{brown}{ 基本性质} }}

    [Fenchel不等式]

    由共轭函数的定义,我们有
    f ( x ) + f ∗ ( y ) ≥ x T y , ∀ x , y (17) f(x)+f^*(y)\geq x^T y,\forall x,y\tag{17} f(x)+f(y)xTy,x,y(17)
    叫做Fenchel不等式。

    例如对于 f ( x ) = ( 1 / 2 ) x T Q x f(x)=(1/2)x^TQx f(x)=(1/2)xTQx , Q ∈ S + + n Q\in S^n_{++} QS++n x T y ≤ ( 1 / 2 ) x T Q x + ( 1 / 2 ) y T Q − 1 y x^Ty\leq (1/2)x^TQx+(1/2)y^TQ^{-1}y xTy(1/2)xTQx+(1/2)yTQ1y.

    [共轭的共轭]

    如果函数 f f f 是凸且闭的,那么 f ∗ ∗ = f f^{**}=f f=f .

    [可微函数]

    可微函数 f f f 的共轭, 也叫做 f f f 的 Legendre变换。令 f f f 是凸且可微的, d o m f = R n d o m f=R^{n} domf=Rn, 任意使 y T x − f ( x ) y^{T} x-f(x) yTxf(x) 取最大值的 x ∗ x^{*} x 都满足 y = ∇ f ( x ∗ ) y=\nabla f\left(x^{*}\right) y=f(x)

    反过来如果 x ∗ x^{*} x 满足 y = ∇ f ( x ∗ ) y=\nabla f\left(x^{*}\right) y=f(x), 那么 x ∗ x^{*} x 使得 y T x − f ( x ) y^{T} x-f(x) yTxf(x) 最大化。因此如果 y = ∇ f ( x ∗ ) y=\nabla f\left(x^{*}\right) y=f(x) 我们有:
    f ∗ ( y ) = x ∗ T ∇ f ( x ∗ ) − f ( x ∗ ) (18) f^{*}(y)=x^{* T} \nabla f\left(x^{*}\right)-f\left(x^{*}\right)\tag{18} f(y)=xTf(x)f(x)(18)
    这允许我们能为任何 y y y 通过得到 f ∗ ( y ) f^{*}(y) f(y) 来解出梯度方程 y = ∇ f ( z ) y=\nabla f(z) y=f(z)

    另一种表示, 令 z ∈ R n z \in R^{n} zRn 是任意的, 定义 y = ∇ f ( z ) y=\nabla f(z) y=f(z), 那么有 f ∗ ( y ) = z T ∇ f ( z ) − f ( z ) f^{*}(y)=z^{T} \nabla f(z)-f(z) f(y)=zTf(z)f(z)

    [伸缩变换,与仿射变换的复合]

    对于 a > 0 , b ∈ R a>0, b \in R a>0,bR, 函数 g ( x ) = a f ( x ) + b g(x)=a f(x)+b g(x)=af(x)+b 的共轭是

    g ∗ ( y ) = a f ∗ ( A − 1 y ) − b T A − T y ⋅ g^{*}(y)=a f^{*}\left(A^{-1} y\right)-b^{T} A^{-T} y \cdot g(y)=af(A1y)bTATy 定义域 d o m g ∗ = A T d o m f ∗ . d o m g^{*}=A^{T} d o m f^{*} . domg=ATdomf.

    [独立函数的和]

    如果 f ( u , v ) = f 1 ( u ) + f 2 ( v ) , f 1 , f 2 f(u, v)=f_{1}(u)+f_{2}(v), \quad f_{1}, f_{2} f(u,v)=f1(u)+f2(v),f1,f2 都是凸函数,且有共轭 f 1 ∗ , f 2 ∗ , f_{1}^{*}, f_{2}^{*}, \quad f1,f2, 那么
    f ∗ ( w , z ) = f 1 ∗ ( w ) + f 2 ∗ ( z ) f^{*}(w, z)=f_{1}^{*}(w)+f_{2}^{*}(z) f(w,z)=f1(w)+f2(z)
    也就是,独立凸函数的和的共轭,是函数的共轭的和。

    4 拟凸函数

    定 义 和 例 子 \large\color{#70f3ff}{\boxed{\color{brown}{定义和例子} }}

    函数 f : R n → R f: R^{n} \rightarrow R f:RnR 是拟凸的, 如果它的定义域和所有下水平集 S α = { x ∈ domf ⁡ ∣ f ( x ) ≤ α } , α ∈ R S_{\alpha}=\{x \in \operatorname{domf} \mid f(x) \leq \alpha\}, \alpha \in R Sα={xdomff(x)α},αR 都是凸的。

    • 一个函数是拟凹(quasiconcave) 的,则 − f -f f 是拟凸的, 也就是每个上水平集 { x ∣ f ( x ) ≥ α } \{x \mid f(x) \geq \alpha\} {xf(x)α} 是凸的。
    • 如果一个函数既拟凸又拟凹,那么叫做拟线性(quasilinear)。如果一个函数是拟线性的那么它的定义域和每个下水平集 { x ∣ f ( x ) = α } \{x \mid f(x)=\alpha\} {xf(x)=α} 都是凸的.

    对于R上的函数,拟凸要求每个下水平集是一个区间(可能包括无限区间)。拟凸函数的一个例子如图5所示。凸函数具有凸下水平集,拟凸函数也具有凸下水平集。但是反过来是不正确的。

    img
    图 5 图5 5

    图5:一个拟凸函数在 R \mathbf{R} R上。对于每个 α \alpha α α \alpha α -子层集 S α S_{\alpha} Sα是凸的,即一个区间。子级别集 S α S_{\alpha} Sα是区间 [ a , b ] . [a, b] . [a,b].子级别集 S β S_{\beta} Sβ是区间 ( − ∞ , c ] (-\infty, c] (,c]

    基 本 性 质 \large\color{#70f3ff}{\boxed{\color{brown}{基本性质} }} 凸和拟凸有很多对应的性质,例如Jesen不等式的拟凸版本:一个函数 f f f 是拟凸的, 当且仅当 d o m f d o m f domf 是凸的, 且对任意 x , 0 ≤ θ ≤ 1 x, 0 \leq \theta \leq 1 x,0θ1
    f ( θ x + ( 1 − θ ) y ) ≤ max ⁡ { f ( x ) , f ( y ) } (19) f(\theta x+(1-\theta) y) \leq \max \{f(x), f(y)\}\tag{19} f(θx+(1θ)y)max{f(x),f(y)}(19)
    也就是定义域某一段上的函数值,不超过这段两端的函数值的最大值,如图:

    img

    [ R R R 上的拟凸函数] 考虑连续函数 f : R ∈ R f: R \in R f:RR 是拟凸的, 当且仅当满足以下至少一个条件:

    • f f f 是非减的

    • f f f 是非增的

    • 存在一个点 c ∈ d o m f c \in d o m f cdomf 使得对于 t ≤ c ( t ∈ d o m f ) , f t \leq c(t \in d o m f), \quad f tc(tdomf),f 是非增的, 且当 t ≥ c ( t ∈ dom ⁡ f ) , f t \geq c(t \in \operatorname{dom} f), \quad f tc(tdomf),f 是非减的。

    • c c c 是一个全局最小点:

    image-20210603215039192

    可 微 拟 凸 函 数 \large\color{#70f3ff}{\boxed{\color{brown}{可微拟凸函数} }}

    f : R n → R f: R^n\rightarrow R f:RnR 是可微的,那么 f f f 是拟凸的当且仅当 d o m f domf domf 是凸的,并且 ∀ x , y ∈ d o m f \forall x,y\in domf x,ydomf

    f ( y ) ≤ f ( x ) ⇒ ∇ f ( x ) T ( y − x ) ≤ 0. (20) f(y)\leq f(x) \Rightarrow \nabla f(x)^T(y-x)\leq 0.\tag{20} f(y)f(x)f(x)T(yx)0.(20)
    简单的几何解释,如图8,给出了拟凸函数 f f f的三个水平曲线。向量 ∇ f ( x ) \nabla f(x) f(x)定义了子层集合 { z ∣ f ( z ) ≤ \{z \mid f(z) \leq {zf(z) f ( x ) } f(x)\} f(x)} x x x处的支持超平面.

    image-20210604081920543
    图 8 图8 8
    [可微拟凸函数—二阶条件] f f f 是二次可微的, 如果 f f f 是拟凸的, 那么 ∀ x ∈ d o m f , y ∈ R n \forall x \in d o m f, y \in R^{n} xdomf,yRn
    y T ∇ f ( x ) = 0 ⇒ y T ∇ 2 f ( x ) y ≥ 0 (21) y^{T} \nabla f(x)=0 \Rightarrow y^{T} \nabla^{2} f(x) y \geq 0\tag{21} yTf(x)=0yT2f(x)y0(21)
    对于 R R R 上的拟凸函数 f f f, 条件简化为 f ′ ( x ) = 0 ⇒ f ′ ′ ( x ) ≥ 0. f^{\prime}(x)=0 \Rightarrow f^{\prime \prime}(x) \geq 0 . f(x)=0f(x)0. 也就是在斜率为 0 的坡的任意点上,二阶导数都是非负的。

    [保留拟凸性的运算]

    非负加权最大值: f = max ⁡ { w 1 f 1 , … , w m f m } , w i ≥ 0 , f i f=\max \left\{w_{1} f_{1}, \ldots, w_{m} f_{m}\right\}, \quad w_{i} \geq 0, f_{i} f=max{w1f1,,wmfm},wi0,fi 是拟凸函数。这个性质可以推广到逐点上确界。

    复合: 如果 g : R n → R g: R^{n} \rightarrow R g:RnR 是拟凸函数, h : R → R h: R \rightarrow R h:RR 是非减的, 那么 f = h ∘ g f=h \circ g f=hg 是拟凸的。拟凸函数和仿射函数或线性-分数函数的复合也是一个拟凸函数。

    最小化: f ( x , y ) f(x, y) f(x,y) 是拟凸函数, C C C 是一个凸集, 那么函数 g ( x ) = inff ⁡ y ∈ C ( x , y )   g(x)=\operatorname{inff}_{y \in C}(x, y)_{\text { }} g(x)=inffyC(x,y)  是拟凸的。

    [用一族凸函数表示] 用凸函数的不等式来表示拟凸函数 f f f 的下水平集。找一族凸函数 ϕ t : R n → R , t ∈ R \phi_t:R^n\rightarrow R , t\in R ϕt:RnR,tR 满足 f ( x ) ≤ t ⇔ ϕ t ( x ) ≤ 0 f(x)\leq t\Leftrightarrow \phi_t(x)\leq 0 f(x)tϕt(x)0.

    也就是, 拟凸函数 f f f t t t -下水平集是凸函数 ϕ t \phi_{t} ϕt 的 0 -下水平集。

    5 对数凹/对数凸函数

    [对数凹/凸 log-concave/log-convex] 函数 f : R n → R f: R^{n} \rightarrow R f:RnR对数凹的, 如果 f ( x ) > 0 , ∀ x ∈ d o m f f(x)>0, \forall x \in d o m f f(x)>0,xdomf的。

    f f f对数凸的当且仅当 1 / f 1 / f 1/f对数凹的。

    允许 f f f 0 , log ⁡ f ( x ) = − ∞ 0, \log f(x)=-\infty 0,logf(x)=, 此时 f f f 是对数凹的, 如果拓展值函数 log ⁡ f \log f logf 是凹的。

    [用不等式表示] 函数 f : R n → R f:R^n\rightarrow R f:RnR 带有凸定义域, 并且 f ( x ) > 0 , ∀ x ∈ d o m f f(x)>0,\forall x\in domf f(x)>0,xdomf 有:
    f ( θ x + ( 1 − θ ) y ) ≥ f ( x ) θ f ( y ) 1 − θ . f(\theta x+(1-\theta) y) \geq f(x)^{\theta} f(y)^{1-\theta} . f(θx+(1θ)y)f(x)θf(y)1θ.

    • 特别地,对数凹函数在两点的中点上的值,大于等于 两点上函数值的几何平均数

    [二次可微的对数凹/对数凸函数] f f f 是二次可微的, d o m f d o m f domf 是凸集,那么有
    ∇ 2 l o g f ( x ) = 1 f ( x ) ∇ 2 f ( x ) − 1 f ( x ) 2 ∇ f ( x ) ∇ f ( x ) T . \nabla^2 log f(x)=\frac{1}{f(x)}\nabla^2 f(x)-\frac{1}{f(x)^2}\nabla f(x)\nabla f(x)^T. 2logf(x)=f(x)12f(x)f(x)21f(x)f(x)T.

    • f f f 是对数凸的,当且仅当 ∀ x ∈ dom ⁡ f \forall x \in \operatorname{dom} f xdomf 有:
      f ( x ) ∇ 2 ⪰ ∇ f ( x ) ∇ f ( x ) T . f(x)\nabla^2\succeq \nabla f(x)\nabla f(x)^T. f(x)2f(x)f(x)T.

    • f f f 是对数凹的,当且仅当 ∀ x ∈ dom ⁡ f \forall x \in \operatorname{dom} f xdomf 有:
      f ( x ) ∇ 2 ⪯ ∇ f ( x ) ∇ f ( x ) T . f(x)\nabla^2\preceq \nabla f(x)\nabla f(x)^T. f(x)2f(x)f(x)T.

    [加法,乘法,积分] 对数凸性和对数凹性对于加法和正标量乘法封闭。

    • 如果 f ( x , y ) f(x, y) f(x,y) 对于所有的 y ∈ C y \in C yC 关于 x x x 对数凸, 那么 g ( x ) = ∫ C f ( x , y ) d y g(x)=\int_{C} f(x, y) d y g(x)=Cf(x,y)dy 是对数凸的

    [对数凹函数的积分] 在某些特殊情况中积分保留对数凹性。如果 f : R n × R m → R f:R^n\times R^m\rightarrow R f:Rn×RmR 是对 数凹的,那么 g ( x ) = ∫ f ( x , y ) d y g(x)= \int f(x,y)dy g(x)=f(x,y)dy 是关于 x x x 的对数凹函数。

    • 这说明对数凹性在卷积下封闭,也就是如果 f , g f, g f,g R n R^{n} Rn 上的对数凹函数,那么卷和 ( f ∗ g ) ( x ) = ∫ f ( x − y ) g ( y ) d y (f*g)(x)=\int f(x-y)g(y)dy (fg)(x)=f(xy)g(y)dy 也是对数凹函数

    6 关于广义不等关系的凸性

    单调性和凸性的推广。

    [单调性] K ⊆ R n K \subseteq R^{n} KRn 是一个真锥(proper cone),有对应的广义不等关系 ⪯ K \preceq_{K} K

    • 一个函数 f : R n → R f: R^{n} \rightarrow R f:RnR 叫做 K K K -非减的, 如果
      x ⪯ K y ⇒ f ( x ) ≤ f ( y ) . x\preceq_K y\Rightarrow f(x)\leq f(y). xKyf(x)f(y).

    • f f f K K K -增的, 如果
      x ≺ K y , x ≠ y ⇒ f ( x ) < f ( y ) . x\prec_K y, x\ne y\Rightarrow f(x)<f(y). xKy,x=yf(x)<f(y).

    类似可以定义 K K K -非增函数,和 K K K -减函数。

    [单调性的梯度条件] 一个定义域是凸集的可微函数 f f f, 是 K K K -非增的, 当且仅当对于所有的 x ∈ d o m f x \in d o m f xdomf ∇ f ( x ) ⪰ K ∗ 0 \nabla f(x)\succeq_{K^*} 0 f(x)K0

    更严格的情况,如果 ∇ f ( x ) ≻ K ∗ 0 \nabla f(x)\succ_{K^*} 0 f(x)K0 对于所有 x ∈ d o m f x\in domf xdomf 成立,那么说 f f f K K K -增的。

    [凸性] K ⊆ R m K \subseteq R^{m} KRm 是一个正常雉,有对应的广义不等关系 ⪯ K \preceq_{K} K

    • 函数 f : R n → R m \mathrm{f}: R^{n} \rightarrow R^{m} f:RnRm K K K -凸的, 当且仅当对于所有 x , y , 0 ≤ θ ≤ 1 x, y, 0 \leq \theta \leq 1 x,y,0θ1
      f ( θ x + ( 1 − θ ) y ) ⪯ K θ f ( x ) + ( 1 − θ ) f ( y ) . f(\theta x+(1-\theta) y)\preceq_K \theta f(x)+(1-\theta)f(y). f(θx+(1θ)y)Kθf(x)+(1θ)f(y).

    • 函数 f f f 是严格 K K K -凸的,如果对于所有 x ≠ y , 0 < θ < 1 x \neq y, 0<\theta<1 x=y,0<θ<1
      f ( θ x + ( 1 − θ ) y ) ≺ K θ f ( x ) + ( 1 − θ ) f ( y ) . f(\theta x+(1-\theta) y)\prec_K \theta f(x)+(1-\theta)f(y). f(θx+(1θ)y)Kθf(x)+(1θ)f(y).

    [ K K K -凸的对偶刻画] 一个函数 f f f K K K -凸的当且仅当对于每个 w ⪰ K ∗ 0 w\succeq_{K^*} 0 wK0, 实值函数 w T f w^Tf wTf 是凸的。 f f f 是严格 K K K -凸的当且仅当对于每个非零 w ⪰ K ∗ w\succeq_{K^*} wK 函数 w T f w^{T} f wTf 是严格凸的。

    [可微 K K K -凸函数] 一个可微函数 f f f K K K -凸的当且仅当它的定义域是凸集, 并且对于所有的 x , y ∈ dom ⁡ f x, y \in \operatorname{dom} f x,ydomf
    f ( y ) ⪰ K f ( x ) + D f ( x ) ( y − x ) . f(y)\succeq_K f(x)+Df(x)(y-x). f(y)Kf(x)+Df(x)(yx).

    此处 D f ( x ) ∈ R m × n D f(x) \in R^{m \times n} Df(x)Rm×n 是函数 f f f 关于 x x x 的导数或 Jacobian 矩阵。

    函数 f f f 是严格 K K K -凸的,当且仅当对于所有 x , y ∈ dom ⁡ f , x ≠ y x, y \in \operatorname{dom} f, x \neq y x,ydomf,x=y
    f ( y ) ≻ K f ( x ) + D f ( x ) ( y − x ) . f(y)\succ_K f(x)+Df(x)(y-x). f(y)Kf(x)+Df(x)(yx).
    [复合定理 composition theorem] 凸函数的非减凸函数是凸的。如果 g : R n → R p g:R^n\rightarrow R^p g:RnRp K K K -凸的, h : R p → R h: R^p\rightarrow R h:RpR 是凸的, 且 h h h 的值拓展 h ~ \tilde{h} h~ K K K -非减的,那么 h ∘ g h \circ g hg 是凸的。

    参考资料

    Stephen BoydConvex Optimization

    《凸优化》,Stephen Boyd等著,王书宁等译

    MIT凸优化课程

    展开全文
  • 凸函数定义2. 拟凸函数的判定/等价定义2.1 Jensen 不等式2.1 “降维打击”2.2 一阶条件2.3 二阶条件3. 拟凸函数的保凸变换3.1 与仿射变换复合3.2 最大值/上确界3.3 复合函数3.4 下确界 1. 拟凸函数定义 拟凸函数...

    个人博客地址 Glooow,欢迎光临~~~

    1. 拟凸函数定义

    拟凸函数(quasiconvex function) 的定义为:若 dom f \text{dom}f domf 为凸集,且对任意的 α \alpha α,其下水平集
    S α = { x ∈ dom f ∣ f ( x ) ≤ α } S_\alpha = \{x\in\text{dom}f | f(x)\le\alpha\} Sα={xdomff(x)α}
    都是凸集,则 f f f 为拟凸函数。

    类似的有拟凹函数(quasiconcave) 的定义。如果一个函数既是拟凸的,又是拟凹的,那么它是拟线性(quasilinear) 的。

    Reamrks:对于拟线性函数,要求其上水平集和下水平集同时是凸集,因此简单理解,其在某种意义上具有“单调性”。比如 e x , log ⁡ x e^x,\log x ex,logx 等。

    拟凸函数各种函数的关系
    在这里插入图片描述在这里插入图片描述

    一些常见的拟凸/拟凹/拟线性函数比如

    拟凸函数

    • f ( x ) = ∣ x ∣ f(x)=\sqrt{|x|} f(x)=x
    • f ( x ) = ∥ x − a ∥ 2 ∥ x − b ∥ 2 , dom f = { x ∣ ∥ x − a ∥ 2 ≤ ∥ x − b ∥ 2 } f(x)=\frac{\Vert x-a\Vert_2}{\Vert x-b\Vert_2},\text{dom}f=\{x|\Vert x-a\Vert_2 \le \Vert x-b\Vert_2\} f(x)=xb2xa2,domf={xxa2xb2}

    拟凹函数

    • f ( x ) = x 1 x 2 f(x)=x_1x_2 f(x)=x1x2 on R 2 R^2 R2

    拟线性函数

    • ceil ( x ) = inf ⁡ { z ∈ Z ∣ z ≥ x } \text{ceil}(x)=\inf\{z\in Z|z\ge x\} ceil(x)=inf{zZzx}
    • log ⁡ x \log x logx on R + + R_{++} R++
    • f ( x ) = a T x + b c T x + d , dom f = { c T x + d > 0 } f(x)=\frac{a^Tx+b}{c^Tx+d},\text{dom}f=\{c^Tx+d >0\} f(x)=cTx+daTx+b,domf={cTx+d>0} (注意 f f f 本身不是凸函数,但是是一个保凸变换)

    2. 拟凸函数的判定/等价定义

    对于普通凸函数,有一些等价定义,比如

    • Jensen 不等式 / 凸函数原生定义: f ( θ x + ( 1 − θ ) y ) ≤ θ f ( x ) + ( 1 − θ ) f ( y ) f(\theta x+(1-\theta)y)\le \theta f(x)+(1-\theta)f(y) f(θx+(1θ)y)θf(x)+(1θ)f(y)
    • “降维打击”: g ( t ) = f ( x + t v ) g(t)=f(x+tv) g(t)=f(x+tv) convex    ⟺    f ( x ) \iff f(x) f(x) convex
    • 一阶条件: f ( x ) f(x) f(x) convex    ⟺    f ( y ) ≥ ∇ f T ( x ) ( y − x ) \iff f(y)\ge \nabla f^T(x)(y-x) f(y)fT(x)(yx)
    • 二阶条件: f ( x ) f(x) f(x) convex    ⟺    ∇ f 2 ( x ) ⪰ 0 \iff \nabla f^2(x)\succeq 0 f2(x)0
    • epigraph: f ( x ) f(x) f(x) convex    ⟺    epi f \iff \text{epi}f epif convex

    2.1 Jensen 不等式

    等价定义 1:函数 f f f 为拟凸的等价于:定义域为凸集,且
    0 ≤ θ ≤ 1 ⟹ f ( θ x + ( 1 − θ ) y ) ≤ max ⁡ { f ( x ) , f ( y ) } 0\le\theta\le1 \Longrightarrow f(\theta x+(1-\theta)y)\le\max\{f(x),f(y)\} 0θ1f(θx+(1θ)y)max{f(x),f(y)}
    证明可以直接用定义。

    2.1 “降维打击”

    等价定义 2 g ( t ) = f ( x + t v ) g(t)=f(x+tv) g(t)=f(x+tv) quasiconvex    ⟺    f ( x ) \iff f(x) f(x) quasiconvex

    证明可以直接用定义。

    Reamrks:这种“降维打击”的定义方式实际上就是要求 f f f 沿着任意一个方向都是(拟)凸的,对于一些高维空间中难以判定凸性,而其一维形式又比较简单的函数来说较适用,比如下面的二阶条件的证明。

    2.2 一阶条件

    等价定义 3 f ( x ) f(x) f(x) quasiconvex 等价于:定义域为凸集,且
    f ( y ) ≤ f ( x ) ⟹ ∇ f T ( x ) ( y − x ) ≤ 0 f(y)\le f(x) \Longrightarrow \nabla f^T(x)(y-x)\le0 f(y)f(x)fT(x)(yx)0
    Remarks:该定义实际上是指 ∇ f ( x ) \nabla f(x) f(x) 定义了一个 R n R^n Rn 空间中的超平面(作为法向量),该超平面就是某一个下水平集的支撑超平面
    S α = { y ∣ f ( y ) ≤ f ( x ) = α } ⊆ R n S_\alpha = \{y| f(y)\le f(x)=\alpha \}\subseteq R^n Sα={yf(y)f(x)=α}Rn
    需要注意的是,前面讲的对于凸函数来说 [ ∇ f T ( x )    − 1 ] T \left[\nabla f^T(x)\ \ -1\right]^T [fT(x)  1]T 定义了一个 R n + 1 R^{n+1} Rn+1 空间中的支撑超平面。注意二者的不同!!!前者是下水平集的支撑超平面,后者是凸函数 surface 的支撑超平面,二者相差一个维度。

    在这里插入图片描述

    上图中三条封闭曲线代表三个水平集,而 ∇ f ( x ) \nabla f(x) f(x) 就是其中一个水平集的支撑超平面。这可以联想梯度下降法(牛顿下山法),想象这是一个山谷,每一条线都是一个等高线, [ ∇ f T ( x )    − 1 ] T \left[\nabla f^T(x)\ \ -1\right]^T [fT(x)  1]T是山坡地面的法向量,指向空中,而 ∇ f ( x ) \nabla f(x) f(x)则在这个等高线所在的平面内,且指向山体内部,与等高线相切。。

    2.3 二阶条件

    对于拟凸函数来说,没有二阶的充分必要条件,有充分条件和必要条件。

    必要条件 f ( x ) f(x) f(x) quasiconvex ⟹ \Longrightarrow 对任意 x ∈ dom f , y ∈ R n x\in\text{dom}f,y\in R^n xdomf,yRn
    if  y T ∇ f ( x ) = 0 ⟹ y T ∇ 2 f ( x ) y ≥ 0 \text{if }\quad y^T \nabla f(x)=0 \Longrightarrow y^T\nabla^2f(x)y\ge0 if yTf(x)=0yT2f(x)y0
    对于一维函数,只需要 f ′ ( x ) = 0 ⟹ f ′ ′ ( x ) ≥ 0 f'(x)=0 \Longrightarrow f''(x)\ge0 f(x)=0f(x)0

    充分条件 f ( x ) f(x) f(x) quasiconvex ⟸ \Longleftarrow 对任意 x ∈ dom f , y ∈ R n , y ≠ 0 x\in\text{dom}f,y\in R^n,y\ne0 xdomf,yRn,y=0
    if  y T ∇ f ( x ) = 0 ⟹ y T ∇ 2 f ( x ) y > 0 \text{if }\quad y^T \nabla f(x)=0 \Longrightarrow y^T\nabla^2f(x)y>0 if yTf(x)=0yT2f(x)y>0
    证明:注意这里对于一维函数 f : R → R f:R\to R f:RR 较简单,因此可以应用“降维打击”的等价定义进行证明。

    3. 拟凸函数的保凸变换

    先来复习一下凸函数的保凸变换

    • 正权重求和
    • 与仿射变换复合
    • 最大值/上确界
    • 单调凸函数与凸函数的复合
    • 下确界
    • 透射变换

    拟凸函数的也是类似的,主要少了第一个和最后一个,也即拟凸函数的正权重求和不一定是拟凸的,也没有透射变换的定义。

    3.1 与仿射变换复合

    f f f 拟凸,则 g ( x ) = f ( A x + b ) g(x)=f(Ax+b) g(x)=f(Ax+b) 也是拟凸的

    这个也很简单,因为 g ( x ) g(x) g(x) 的下水平集就是 f ( y ) f(y) f(y) 的下水平集外加仿射变换 y = A x + b y=Ax+b y=Ax+b,仿射变换不改变凸性。

    3.2 最大值/上确界

    离散情况 f = max ⁡ { ω 1 f 1 , . . . , ω m f m } , ω i ≥ 0 f=\max\{\omega_1 f_1,...,\omega_m f_m\},\omega_i\ge0 f=max{ω1f1,...,ωmfm},ωi0

    连续情况 g ( x ) = sup ⁡ { w ( y ) f ( x , y ) , ω ( y ) ≥ 0 } g(x)=\sup\{w(y)f(x,y),\omega(y)\ge0\} g(x)=sup{w(y)f(x,y),ω(y)0} 是拟凸的,如果 f ( ⋅ , y ) f(\cdot,y) f(,y) 是拟凸的

    证明很简单,因为导出函数的下水平集就是多个拟凸函数下水平集的交集,当然也是凸集。

    3.3 复合函数

    如果 g g g 为拟凸函数,且 h h h 单调递增,则 f = h ∘ g f=h\circ g f=hg 是拟凸的

    证明的话也可以从下水平集的角度理解。

    :若 f f f 是拟凸的,则 g ( x ) = f ( A x + b ) g(x)=f(Ax+b) g(x)=f(Ax+b) 是拟凸的,且 g ~ ( x ) = f ( ( A x + b ) / ( c T x + d ) ) \tilde{g}(x)=f((Ax+b)/(c^Tx+d)) g~(x)=f((Ax+b)/(cTx+d)) 也是拟凸的,其中
    { x ∣ c T x + d > 0 , ( A x + b ) / ( c T x + d ) ∈ dom f } \{x|c^Tx+d>0,(Ax+b)/(c^Tx+d)\in\text{dom}f\} {xcTx+d>0,(Ax+b)/(cTx+d)domf}
    原因很简单, g ~ ( x ) \tilde{g}(x) g~(x) 的下水平集就是 f ( y ) f(y) f(y) 的下水平集外加一个线性分式变换