02-凸函数
目录一、基本性质和例子二、保留凸性的运算三、共轭函数四、拟凸函数五、对数凹/对数凸函数六、关于广义不等关系的凸性
凸优化从入门到放弃完整教程地址：https://www.cnblogs.com/nickchen121/p/14900036.html
一、基本性质和例子
[凸函数] 一个函数 f: R^nightarrow R) 是凸的，如果定义域 dom\,f) 是凸集，并且对于所有 x,yin f, hetaleq 1) ，我们有 f heta x+1- heta)y)leq heta fx)+1- heta)fy).)
注：如果不能理解，从二维角度去理解
几何解释：点 x,fx))) 和 y,fy))) 之间的线段在 f) 对应的图像上方。
函数 f) 是严格凸的，如果以上不等式在 x
e y) ，且 0< heta <1) 时也成立.
函数 f) 是凹的，当 -f) 是凸的，严格凹，当 -f) 是严格凸的。
仿射函数既是凸的也是凹的，反过来，既凹又凸的函数是仿射的。
一个函数是凸的当且仅当对任意 xin dom\,f) 和任意 v) ，函数 gt)=fx+tv)) 是凸的， {t|x+tvin dom\,f}.)注：其实只是修改了自变量的表示，又由于自变量的集合是凸集，线性表示后仍然是凸集
[扩展值] 将凸函数扩展到整个 R^n) ，通常令它在定义域之外取 infty) 。如果 f) 是凸函数那么它的拓展为 widetilde{f} : R^nightarrow R cup {infty}) ,
widetilde{f}x)=left {egin{aligned} fx);; xin domf\ infty;; x
otin domf end{aligned}ight.)
[一阶条件] 令函数 f) 是可微的（也就是它的梯度
abla f) 在开集 domf) 的每个点上都存在）。那么 f) 是凸的，当且仅当 domf) 是凸的，并且对所有的 x,yin domf) 有：
fy)geq fx)+
abla fx)^Ty-x).)
注：其实同样可以从二维角度的考虑，无非就是 dy)，也就是函数图像永远在某一点的切上上，同时 fx)+
abla fx)^Ty-x)) 相当于 f) 在 x) 的一阶泰勒近似，如果你对泰勒展开公式熟悉，更好理解，因为泰勒展开是无穷阶的，只不过此处做了省略
在每个点上，函数图像都高于在该点的切线。
解释：y) 的仿射函数 fx)+
abla fx)^Ty-x)) 是 f) 在靠近 x) 处的一阶泰勒近似。上述不等式表达了这个一阶泰勒近似是函数的全局下限（global underestimator），反过来，如果函数的一阶泰勒近似总是函数的全局下限，那么这个函数是凸的。
如果
abla fx)=0) ,那么对于所有 yin domf) ，有 fy)geq fx)) ， 也就是在 x) 处 f) 取到全局最小值（ x) is a global minimizer of f) ）。
f) 是严格凸的，当且仅当 domf) 是凸的，且对于所有 x,yin domf, x
e y) 有 fy)>fx)+
abla fx)^Ty-x).)
f) 是凹的，当且仅当 domf) 是凸的，并且 fy)leq fx)+
abla fx)^Ty-x),)forall x,yin domf.)
[二阶条件] 设函数 f) 是二阶可微的，也就是它在开集 domf) 的每个点上都存在二阶导数
abla^2 f) 。那么 f) 是凸的，当且仅当它的二阶导数是半正定的：
注：同样在二维角度理解，二阶导大于 0，则一阶导单调递增，则在一阶导为 0 的左边是小于 0 的，右边大于 0 的，也就是说原函数在一阶导为 0 的左边是单调递减的，在右边是单调递增的，凸
forall xin domf) ,
abla^2fx)succeq 0) .
几何解释：函数图像在每个定义域的每个点上都有正的曲率curvature)。
函数 f) 是凹的，当且仅当 domf) 是凸的，并且
abla^2fx)preceq 0) , forall xin domf)
如果 forall xin domf) ,
abla^2fx)succ 0) ，那么 f) 是严格凸的。反过来不成立，例如 fx)=x^4) 是严格凸的，但是在 x=0) 处二阶导数为 0) .
[例]
注：以下判断，简单的函数可以画图确定，复杂的可以通过求二阶导确定
在 R) 上：
e^{ax} , forall ain R) , 在 R) 上凸。
x^a,) 当 ageq 1) 或 aleq 0) ，在 R_{++}) 上凸，当 0leq aleq 1) 时凹。
|x|^p) , pgeq 1) ，在R上凸。
log;x) ，在 R_{++}) 上凸 。
负熵 x log ; x) ，在 R_+) 和 R_{++}) 上凸。
在 R^n) 上：
范数，凸
最大值函数，凸
Quadratic-over-linear 函数： fx,y)=x^2/y) , domf=R imes R_{++}={x,y)in R^n| y>0}) ，凸。
fx)=loge^{x_1}+…+e^{x_n})) ，凸
几何平均 fx)=prod^n_{i=1}x_i)^{1/n}) ，在 R^n_{++}) 上凹。
fX)=log; detX) ，在 S^n_{++}) 上凹。
[下水平集 sublevel set] 函数 f:R^nightarrow R) 的一个 alpha) -下水平集是
注：下水平集其实就是对函数做了一个水平切割，或者说对定义域做了切割
C_{alpha}={xin domf | fx)leq alpha}) .
凸函数的下水平集是凸集，对于所有的 alpha) 。反过来不对，例如 fx)=-e^x) 在 R) 上不是凸的，但是它的所有下水平集都是凸集。
凹函数的下水平集是凸集。
[上境图 epigraph] 一个函数 f:R^nightarrow R) 的图像是 {x,fx))|xin dom f}) . 它是 R^{n+1}) 的子集。定义函数 f) 的
上境图: epi; f = {x,t)| xin dom f , fx)leq t}) .
下境图： hypo;f = {x,t)| tleq fx)}) .
注：上、下境图，其实就是对函数做了一个水平切割。有可能说凸函数的下境图是一个凸集，但是这种说法没有意义，因为上、下境图的水平切割是没有固定值的
函数是凸的当且仅当它的上境图是一个凸集。
函数是凹的当且仅当它的下境图是一个凸集。
[Jensen不等式] 基本不等式 f heta x+1- heta)y)leq heta fx)+1- heta)fy)) 有时被叫做Jensen不等式。
注：Jensen 不等式其实就是凸函数的定义
它可以拓展到多个点的凸组合：
如果 f) 是凸的， x_1,…,x_kin domf, heta_1,…, heta_k geq 0) , heta_1+…+ heta_k=1) 那么
f heta_1x_1+…+ heta_kx_k)leq heta_1 fx_1)+…+ heta_k fx_k)) .
还可以拓展到无限，积分和期望：
积分：如果 px)geq 0) 在 Ssubseteq domf) 上， int_{S} px) dx =1) ，那么 fint_{S} px) dx)leq int_S fx) px) dx) .
期望：如果 x) 是随机变量 xin dom f) ，且 f) 是凸函数，那么有 fEx)leq E fx)) .
二、保留凸性的运算
注：以下保凸运算其实可以使用定义，也就是用 Jensen 不等式证明，注意保留的是凸函数的性质，而不是保留了凸集的性质，不要和凸集的概念搞混了
[非负加权和] 如果 f_1,…,f_m) 是凸函数，他们的集合是一个凸锥——凸函数的非负加权和 f=w_1f_1+…+w_mf_m， w_1,…,w_mgeq 0)) 是凸的。
注：非负加权和其实可以看做是多个做非负伸缩的凸函数进行了加和
还可以拓展到积分：如果 fx,y)) 对于x是凸的，对于每个 yin A) ，且wy)geq 0, forall yin A) ，那么函数 gx)=int_A wy)fx,y)dy) 对于 x) 是凸的。
[与仿射函数的复合] 令 f:R^nightarrow R) , Ain R^{n imes m}) , bin R) 。定义 g:R^mightarrow R) 为
gx)=fAx+b)) , domg={a| Ax+bin domf}) .
那么如果 f) 是凸函数， g) 也是凸函数。
[逐点最大 pointwise maximum] 如果 f_1,f_2) 是凸函数，那么他们的逐点最大 f) ，定义为
fx)=max{f_1x),f_2x)}) , 定义域 domf=domf_1cap domf_2)
也是凸集。可以拓展到多个凸函数的逐点最大。
[逐点上确界 pointwise supremum] 如果对于每个 yin A) , fx,y)) 关于 x) 是凸的，那么函数
gx)=underset {yin A}{sup} \,fx,y))
关于 x) 是凸的。 g) 的定义域是
dom g={x|x,y)in dom f, forall yin A, underset{yin A}{sup}fx,y)<infty}) .
类似地，一组凹函数的逐点下确界是凹函数。
epi\, g =igcap _ {yin A}epi \, fcdot,y)) .
[最小化] 如果 f) 关于 x,y)) 是凸函数，并且 C) 是非空凸集，那么函数
gx)=underset{gin C}{inf}\, fx,y))
是关于 x) 的凸函数，对于所有的 x) 有 gx)>-infty) 的定义域是 domf) 到 x) 轴的投影：
dom g={x| x,y)in domf, for \,some\,yin C}) .
[函数的透视] 函数 f: R^nightarrow R) ， f) 的透视函数为
g:R^{n+1}ightarrow R) ， gx,t)=tfx/t)) ，
domg={x,t)| x/tin dom f, t>0})
透视运算保存凸性：如果函数 f) 是凸的，那么它的透视函数 g) 也是凸的；如果 f) 是凹的，那么 g) 也是凹的。
三、共轭函数
[函数的共轭 conjugate] 令 f:R^nightarrow R) 函数 f^* : R^nightarrow R) 定义为
f^*y)=underset{xin domf}{sup} y^Tx-fx))) , 叫做函数 f) 的共轭。
注：共轭函数的本质，其实就是通过一阶导，对求 x) 的最小值问题转化为了求解截距最大值问题，如果我们把共轭函数写成这样 gx_0) = -x_0 frac{partial f}{ partial x} x_0) + fx_0),x_0in domf)，这样看是不是亲切很多，其实就是切线截距公式，而前面的 underset{{xin domf}}{sup}) 就是求最大值咯
共轭函数的定义域 由使得上述上确界有限的 y, yin R^n) 组成。也就是说在 domf) 上差 y^Tx-fx)) 是有界的。如图：
共轭函数 f^*) 是凸的，因为它是关于 y) 的凸函数的逐点上确界，这一点为真不论 f) 是否是凸的。
[Fenchel不等式] 由共轭函数的定义，我们有
fx)+f^*y)geq x^T y) , forall x,y) ，叫做Fenchel不等式。
例如对于 fx)=1/2)x^TQx) , Qin S^n_{++}) 有 x^Tyleq 1/2)x^TQx+1/2)y^TQ^{-1}y.)
[共轭的共轭] 如果函数 f) 是凸且闭的，那么 f^{**}=f) .
[可微函数] 可微函数 f) 的共轭，也叫做 f) 的 Legendre变换。令 f) 是凸且可微的， domf=R^n) ，任意使 y^Tx-fx)) 取最大值的 x^*) 都满足 y=
abla fx^*)) 。
反过来如果 x^{*}) 满足 y=
abla fx^*)) ，那么 x^{*}) 使得 y^Tx-fx)) 最大化。因此如果 y=
abla fx^*)) 我们有：
f^*y)=x^{*T}
abla fx^*)-fx^*).) 注：这里就讲到了 y^T) 其实就是一阶导
这允许我们能为任何 y) 通过得到 f^*y)) 来解出梯度方程 y=
abla fz)) 。
另一种表示，令 zin R^n) 是任意的，定义 y=
abla fz)) , 那么有 f^*y)=z^T
abla fz)-fz)) .
注：下面就是共轭函数的一些特殊性质咯
[伸缩变换，与仿射变换的复合] 对于 a>0,bin R) ，函数 gx)=afx)+b) 的共轭是
g^*y)=af^*A^{-1}y)-b^TA^{-T}y) . 定义域 domg^*=A^Tdomf^*.)
[独立函数的和] 如果 fu,v)=f_1u)+f_2v)) ， f_1,f_2) 都是凸函数，且有共轭 f_1^*,f_2^*，) 那么 f^*w,z)=f_1^*w)+f_2^*z).)
也就是，独立凸函数的和的共轭，是函数的共轭的和。
四、拟凸函数
[拟凸 Quasiconvex] 函数 f: R^nightarrow R) 是拟凸的，如果它的定义域和所有下水平集 S_{alpha}={xin domf | fx)leq alpha}) , alpha in R) 都是凸的。
注：这里需要注意的是下水平集是凸集，而不是凸函数，其实就是利用了下境图的概念去理解，就很好理解，就是一个函数可能不是凸，但是它的最小值在凸的那一部分，那我做个水平切割只要凸的那一部分就好了
一个函数是拟凹（quasiconcave）的，如果 -f) 是拟凸的，也就是每个上水平集 {x| fx)geq alpha}) 是凸的。
如果一个函数既拟凸又拟凹，那么叫做拟线性（quasilinear）。如果一个函数是拟线性的那么它的定义域和每个下水平集 {x| fx)=alpha}) 都是凸的.
[基本性质—不等式] 凸和拟凸有很多对应的性质，例如Jesen不等式的拟凸版本：一个函数 f) 是拟凸的，当且仅当 domf) 是凸的，且对任意 x) ， 0leq hetaleq 1) 有
f heta x+1- heta)y)leq max{fx),fy)}.)
注：拟凸函数的 Jensen 不等式就是说明了函数被函数两端的最大值控制着
也就是定义域某一段上的函数值，不超过这段两端的函数值的最大值，如图：
[ R) 上的拟凸函数] 考虑连续函数 f:Rin R) 是拟凸的，当且仅当满足以下至少一个条件：
f) 是非减的
f) 是非增的
存在一个点 cin domf) 使得对于 tleq c tin domf)) ， f) 是非增的，且当 tgeq c tin domf)) ， f) 是非减的。
c) 是一个全局最小点：
[可微拟凸函数—一阶条件] 令 f: R^nightarrow R) 是可微的，那么 f) 是拟凸的当且仅当 domf) 是凸的，并且 forall x,yin domf) 有
fy)leq fx) Rightarrow
abla fx)^Ty-x)leq 0.)
注：这个一阶条件就是规定了 y-x) 和
abla fx)) 的夹角为钝角，从下图可以看出，也就是说 y) 的等高线一定在 x) 的等高线之内，也就是说明了 fy) leq fx))
[可微拟凸函数—二阶条件] 令 f) 是二次可微的，如果 f) 是拟凸的，那么 forall xin domf, yin R^n) 有
y^T
abla fx)=0Rightarrow y^T
abla^2 fx)ygeq 0.)
对于 R) 上的拟凸函数 f) ，条件简化为 f’x)=0Rightarrow f”x)geq 0.) 注：也就是说在斜率为 0) 的坡的任意点上，二阶导数都是非负的。
[保留拟凸性的运算]
非负加权最大值： $f=max{w_1f_1,…,w_mf_m} ，w_igeq 0, $$f_i$ 是拟凸函数。这个性质可以推广到逐点上确界。
复合：如果 g:R^nightarrow R) 是拟凸函数， h:Rightarrow R) 是非减的，那么 f=hcirc g) 是拟凸的。拟凸函数和仿射函数或线性-分数函数的复合也是一个拟凸函数。
最小化： fx,y)) 是拟凸函数， C) 是一个凸集，那么函数 gx)=underset{yin C }{inf}fx,y)) 是拟凸的。
[用一族凸函数表示] 用凸函数的不等式来表示拟凸函数 f) 的下水平集。找一族凸函数 phi_t:R^nightarrow R , tin R) 满足 fx)leq tLeftrightarrow phi_tx)leq 0.)
也就是，拟凸函数 f) 的 t)-下水平集是凸函数 phi_t) 的 0)-下水平集。
五、对数凹/对数凸函数
注：个人理解，因为对数凸不能证明什么，对数凸只是在某些情况让一个函数更易于进行优化，例如拟凸函数 f=e^{x^2})，对数之后就是凸函数 log f = -x^2)，让一个拟凸函数变成凸函数，性质更好
[对数凹/凸 log-concave/log-convex] 函数 f:R^nightarrow R) 是对数凹的，如果 fx)>0, forall xin domf) 是凹的。
f) 是对数凸的当且仅当 1/f) 是对数凹的。
允许 f) 取 0) ， log\,fx)=-infty) ，此时 f) 是对数凹的，如果拓展值函数 log\,f) 是凹的。
[用不等式表示] 函数 f:R^nightarrow R) 带有凸定义域，并且 fx)>0,forall xin domf) 有：
logf heta x+1- heta)y))geq logfx)^{ heta}fy)^{1- heta})=f heta x+1- heta)y)geq logfx)^{ heta}fy)^{1- heta}.)
注：从变异的 Jensen 不等式可以看出，其实对数凸就是对 Jensen 不等式做了对数变化
特别地，对数凹函数在两点的中点上的值，大于等于两点上函数值的几何平均数。
[二次可微的对数凹/对数凸函数] 令 f) 是二次可微的， domf) 是凸集，那么有
abla^2 log fx)=frac{1}{fx)}
abla^2 fx)-frac{1}{fx)^2}
abla fx)
abla fx)^T.)
f) 是对数凸的，当且仅当 forall xin domf) 有：
fx)
abla^2 fx)succeq
abla fx)
abla fx)^T.)
f) 是对数凹的，当且仅当 forall xin domf) 有：
fx)
abla^2 fx)preceq
abla fx)
abla fx)^T.)
[加法，乘法，积分] 对数凸性和对数凹性对于加法和正标量乘法封闭。
如果 fx,y)) 对于所有的 yin C) 关于 x) 对数凸, 那么 gx)=int_C fx,y) dy) 是对数凸的
[对数凹函数的积分] 在某些特殊情况中积分保留对数凹性。如果 f:R^n imes R^mightarrow R) 是对数凹的，那么 gx)= int fx,y)dy) 是关于 x) 的对数凹函数。
这说明对数凹性在卷积下封闭，也就是如果 f,g) 是 R^n) 上的对数凹函数，那么卷积 f*g)x)=int fx-y)gy)dy) 也是对数凹函数。
六、关于广义不等关系的凸性
注：广义不等式的凸性，其实就是把 Jensen 不等式扩展到锥上定义了
单调性和凸性的推广。
[单调性] 令 Ksubseteq R^n) 是一个正常锥proper cone) ，有对应的广义不等关系 preceq_K) 。
一个函数 f:R^nightarrow R) 叫做K) -非减的，如果
xpreceq_K yRightarrow fx)leq fy).)
f) 是K) -增的，如果
xprec_K y, x
e yRightarrow fx)<fy).)
类似可以定义 K) -非增函数，和 K) -减函数。
[单调性的梯度条件] 一个定义域是凸集的可微函数 f) ，是 K) -非增的，当且仅当对于所有的 xin domf) 有
abla fx)succeq_{K^*} 0) .
更严格的情况，如果
abla fx)succ_{K^*} 0) 对于所有 xin domf) 成立，那么说 f) 是 K) -增的。
[凸性] 令 Ksubseteq R^m) 是一个正常锥，有对应的广义不等关系 preceq_K) 。
函数 f: R^nightarrow R^m) 是 K) –凸的，当且仅当对于所有 x,y, 0leq heta leq 1) 有
f heta x+1- heta) y)preceq_K heta fx)+1- heta)fy).)
函数 f) 是严格 K) -凸的，如果对于所有 x
e y, 0< heta< 1) 有
f heta x+1- heta) y)prec_K heta fx)+1- heta)fy).)
[ K) -凸的对偶刻画] 一个函数 f) 是 K) -凸的当且仅当对于每个 wsucceq_{K^*} 0) ，实值函数 w^Tf) 是凸的。 f) 是严格 K) -凸的当且仅当对于每个非零 wsucceq_{K^*} 0) 函数 w^Tf) 是严格凸的。
[可微 K) -凸函数] 一个可微函数 f) 是 K) -凸的当且仅当它的定义域是凸集，并且对于所有的 x,yin domf) 有
fy)succeq_K fx)+Dfx)y-x).)
此处 Dfx)in R^{m imes n}) 是函数 f) 关于 x) 的导数或 Jacobian 矩阵。
函数 f) 是严格 K) -凸的，当且仅当对于所有 x,yin domf ,x
e y) 有
fy)succ_K fx)+Dfx)y-x).)
[复合定理 composition theorem] 凸函数的非减凸函数是凸的。如果 g:R^nightarrow R^p) 是 K) -凸的， h: R^pightarrow R) 是凸的，且 h) 的值拓展 widetilde{h}) 是 K) -非减的，那么 hcirc g) 是凸的。
参考文献：Stephen Boyd, Lieven Vandenberghe: Convex Optimization