定义: 函数
f
:
R
n
→
R
f:R^n\rightarrow R
f:Rn→R是凸的,如果
d
o
m
f
domf
domf是凸集,且对于任意
x
,
y
∈
d
o
m
f
x,y\in domf
x,y∈domf和任意
0
≤
θ
≤
1
0\le \theta \le1
0≤θ≤1都有
f
(
θ
x
+
(
1
?
θ
)
y
)
≥
θ
f
(
x
)
+
(
1
?
θ
)
f
(
y
)
f(\theta x+(1-\theta)y)\ge \theta f(x)+(1-\theta)f(y)
f(θx+(1?θ)y)≥θf(x)+(1?θ)f(y)
从几何上看就是两个点的线段在函数之上
一阶条件:
f
(
y
)
≥
f
(
x
)
+
?
f
(
x
)
T
(
y
?
x
)
f(y)\ge f(x)+\nabla f(x)^T(y-x)
f(y)≥f(x)+?f(x)T(y?x)
二阶条件:
f
′
′
(
x
)
≥
R
+
0
f''(x)\ge_{R^+}0
f′′(x)≥R+?0这边大于号是各个元素都大于0的意思
下水平集:
函数
f
:
R
n
→
R
f:R^n\rightarrow R
f:Rn→R的
α
\alpha
α下水平集定义为
C
α
=
{
x
∈
d
o
m
f
∣
f
(
x
)
≤
a
}
C_\alpha=\{x\in domf|f(x)\le a\}
Cα?={x∈domf∣f(x)≤a}
凸函数的下水平集仍是凸集,凹函数的上水平集也是凸集,这两个性质分过来就不一定
上镜图:
e
p
i
f
=
{
(
x
,
t
)
∣
x
∈
d
o
m
f
,
f
(
x
)
≤
t
}
epif=\{(x,t)|x\in domf,f(x)\le t\}
epif={(x,t)∣x∈domf,f(x)≤t}
亚图:
h
y
p
o
f
=
{
(
x
,
t
)
∣
t
≤
f
(
x
)
}
hypo f=\{(x,t)|t\le f(x)\}
hypof={(x,t)∣t≤f(x)}
一个函数是凸函数,当且仅当它的上镜图是凸集;一个函数是凹函数,当且仅当其亚图是凸集
保凸运算:
1.非负加权求和
2.复合仿射映射
g
(
x
)
=
f
(
A
x
+
b
)
g(x)=f(Ax+b)
g(x)=f(Ax+b)
3.逐点最大和逐点上确界
f
(
x
)
=
m
a
x
{
f
1
(
x
)
,
f
2
(
x
)
}
f(x)=max\{f_1(x),f_2(x)\}
f(x)=max{f1?(x),f2?(x)}
上确界对应着这些函数的上镜图的交集
4.透视函数
g
(
x
,
t
)
=
t
f
(
x
/
t
)
g(x,t)=tf(x/t)
g(x,t)=tf(x/t)
共轭函数
设函数
f
:
R
n
→
R
f:R^n\rightarrow R
f:Rn→R定义函数
f
?
:
R
n
→
R
f^*:R^n\rightarrow R
f?:Rn→R为
f
?
(
y
)
=
s
u
p
x
∈
d
o
m
f
(
y
T
x
?
f
(
x
)
)
f^*(y)=\underset{x\in domf}{sup}(y^Tx-f(x))
f?(y)=x∈domfsup?(yTx?f(x))
Fenchel不等式
f
(
x
)
+
f
?
(
y
)
≥
x
T
y
f(x)+f^*(y)\ge x^Ty
f(x)+f?(y)≥xTy
使
y
T
x
?
f
(
x
)
y^Tx-f(x)
yTx?f(x)取最大值的
x
?
x^*
x?满足
y
=
?
f
(
x
?
)
y=\nabla f(x^*)
y=?f(x?),反之亦然
所以
f
?
(
y
)
=
x
?
T
?
f
(
x
?
)
?
f
(
x
?
)
f^*(y)=x^{*T}\nabla f(x^*)-f(x^*)
f?(y)=x?T?f(x?)?f(x?)
g
(
x
)
=
f
(
A
x
+
b
)
g(x)=f(Ax+b)
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?(A?Ty)?bTA?Ty
f
(
u
,
v
)
=
f
1
(
u
)
+
f
2
(
v
)
f(u,v)=f_1(u)+f_2(v)
f(u,v)=f1?(u)+f2?(v)
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)
这里要求两个变量是独立的
拟凸函数: 它的定义域和所有下水平集是凸集
拟凹函数: 它的定义域和所有上水平集是凸集
充要条件
d
o
m
f
是凸集
,
对于任意
x
,
y
∈
d
o
m
f
及
0
≤
θ
≤
1
domf是凸集,对于任意x,y\in domf及0\le \theta \le 1
domf是凸集,对于任意x,y∈domf及0≤θ≤1有
f
(
θ
x
+
(
1
?
θ
)
y
)
≤
m
a
x
{
f
(
x
)
,
f
(
y
)
}
f(\theta x+(1-\theta)y)\le max\{f(x),f(y)\}
f(θx+(1?θ)y)≤max{f(x),f(y)}\
函数f是拟凸的下面至少有一个条件成立:
f非减
f非增
存在一个点c,使得
t
≤
c
t\le c
t≤c时非增,
t
≥
c
t\ge c
t≥c时非减
一阶条件
函数f可微时,f拟凸的充要条件是
f
(
y
)
≤
f
(
x
)
?
f
(
x
)
T
(
y
?
x
)
≤
0
f(y)\le f(x)\Rightarrow f(x)^T(y-x)\le0
f(y)≤f(x)?f(x)T(y?x)≤0
二阶条件
y
T
?
f
(
x
)
=
0
→
y
T
?
2
f
(
x
)
y
≥
0
y^T\nabla f(x)=0\rightarrow y^T\nabla^2f(x)y\ge0
yT?f(x)=0→yT?2f(x)y≥0
保拟凸运算:
1.非负加权最大
2.复合
h非减,g拟凸 h(g(x))拟凸
f拟凸 g(x)=f(Ax+b)拟凸
3.最小化
对数凹和对数凸
logf是凹的是对数凹,logf是凸的是对数凸
f是对数凸的,当且仅当1/f是对数凹的
函数f是对数凹的,当且仅当
0
≤
θ
≤
1
0\le \theta \le1
0≤θ≤1
f
(
θ
x
+
(
1
?
θ
)
y
)
≥
f
(
x
)
θ
f
(
y
)
1
?
θ
f(\theta x+(1-\theta)y)\ge f(x)^\theta f(y)^{1-\theta}
f(θx+(1?θ)y)≥f(x)θf(y)1?θ
对数凸的函数的凸函数,非负凹函数是对数凹函数
对数凸函数的拟凸函数,对数凹函数是拟凹函数
二次可微的对数凸凹函数
?
2
l
o
g
f
(
x
)
=
1
f
(
x
)
?
2
f
(
x
)
?
1
f
(
x
)
2
?
f
(
x
)
?
f
(
x
)
T
\nabla^2logf(x)=\frac{1}{f(x)}\nabla^2f(x)-\frac{1}{f(x)^2}\nabla f(x)\nabla f(x)^T
?2logf(x)=f(x)1??2f(x)?f(x)21??f(x)?f(x)T
f是对数凸函数,当且仅当
f
(
x
)
?
2
f
(
x
)
≥
?
f
(
x
)
?
f
(
x
)
T
f(x)\nabla^2f(x)\ge \nabla f(x)\nabla f(x)^T
f(x)?2f(x)≥?f(x)?f(x)T
f是对数凹函数,当且仅当
f
(
x
)
?
2
f
(
x
)
≤
?
f
(
x
)
?
f
(
x
)
T
f(x)\nabla^2f(x)\le\nabla f(x)\nabla f(x)^T
f(x)?2f(x)≤?f(x)?f(x)T
广义不等式的单调性
K是一个正常锥,如果
x
≤
K
y
?
f
(
x
)
≤
f
(
y
)
x\le_Ky\Rightarrow f(x)\le f(y)
x≤K?y?f(x)≤f(y) 称f K-非减
关于广义不等式的凸性
正常锥定义的函数K凸是
f
(
θ
x
+
(
1
?
θ
)
y
)
≤
K
θ
f
(
x
)
+
(
1
?
θ
)
f
(
y
)
f(\theta x+(1-\theta)y)\le_K \theta f(x)+(1-\theta)f(y)
f(θx+(1?θ)y)≤K?θf(x)+(1?θ)f(y) ,其中
0
≤
θ
≤
1
0\le\theta\le1
0≤θ≤1
K凸的对偶刻画
函数f是K凸的,当且仅当对于任意
w
≥
K
?
0
w\ge_{K^*}0
w≥K??0,函数
w
T
f
w^Tf
wTf是凸的
可微的K凸函数
可微函数是K凸的,当且仅当其定义域是凸集,且
f
(
y
)
≥
K
f
(
x
)
+
D
f
(
x
)
(
y
?
x
)
f(y)\ge_K f(x)+Df(x)(y-x)
f(y)≥K?f(x)+Df(x)(y?x)