700字范文 > 组合最优化——凸集凸函数

组合最优化——凸集凸函数

时间：2019-05-01 22:34:23

相关推荐

组合最优化——凸集凸函数

1、凸集：

对于一个数集合D，对于其中的任何两个数x和y，构成一个点，以及我们所选的任何实数a，0＜a＜1，都有

a*x+(1-a)*y∈D

则证明集合D是一个凸集

**性质1：**有限个（或者无限个）凸集的交集为凸集

**性质2：**假设D是凸集，β是一个实数，则下面的集合是凸集

β*D={y|y=β*x, x∈D}

**性质3：**两个凸集的和集是凸集

D1+D2={y|y=x+z,x∈D1,z∈D2}

**推论1：**凸集的线性组合是凸集

**推论2：**凸集中任意有限个点的凸组合仍然在该凸集中

2、极点

对于一个凸集D中的x，如果D中不存在两个相异的数y，z及某一个实数a，0＜a＜1，使得

x=α*y+(1-α)*z

则x为D的极点

**性质1：**若D={x ∈Rn| ||x||≤a}(a>0),则||x||=a上的点均为极点

证明:设||x||=a,若存在y,z ∈D及α∈(0,1),使得x=αy+(1-α)z.则 a2=||x||2=（αy+(1-α)z,αy+(1-α)z） ≤α2||y||2+(1-α)2||z||2+2α (1-α)||y||||z||≤a2不等式取等号,必须||y||=||z||=a,且（ y,z ） =||y||||z||,容易证明y=z=x,根据定义可知,x为极点.

3、凸函数

设函数f(x)定义在凸集D上，如果对应任意的x,y∈D，及任意的a∈[0,1]都有

f (α x+(1-α)y) ≤ α f(x)+(1-α) f (y)

则f(x)为凸集D上的凸函数

同理，有严格凸函数的定义

设函数f (x)定义在凸集D上,若对任意的x,y∈D，x≠y,及任意的α ∈(0,1)都有

f (α x+(1-α)y) < α f(x)+(1-α) f (y)

则称函数f (x)为凸集D上的严格凸函数

最常见的严格凸函数是二次函数y=x^2

**举例：**设f (x)=(x–1)^2,试证明f(x)在(–∞,+∞)上是严格凸函数.

证明:设x,y∈ R,且x≠y, α∈(0,1)都有f (αx+(1-α)y)-(α f (x) +(1-α)f (y))=(αx+(1-α)y-1)2-α (x-1)2-(1-α) (y-1)2= –α (1-α)(x-y)2<0因此f(x)在(–∞,+∞)上是严格凸函数.

下面是判断凸函数的代码，采用的是随机数方法：

import random as rndef hanshu(x):return float((x-1)*(x-1))if __name__=="__main__":a=float(input('请输入范围左端点横坐标'))b=float(input('请输入范围右端点横坐标'))c=float(input('请输入范围左端点纵坐标'))d=float(input('请输入范围右端点纵坐标'))flag=1for i in range(100):x=rn.uniform(a,b)y=rn.uniform(c,d)z=rn.uniform(0,1)if(hanshu(z*x+(1-z)*y)<(z*hanshu(x)+(1-z)*hanshu(y))):flag=1else:flag=0breakif(flag==1):print('是凸函数')else:print('不是凸函数')

这个代码是生成随机数进行100次测试，得到一个结果，如果更改循环的次数，准确率会更高

**凸函数几何性质：**对一元函数f (x),在几何上α f (x1)+(1-α)f (x2)(0≤α≤1)表示连接(x1,f(x1)),(x2,f (x2))的线段, f(αx1+(1-α)x2)表示在点αx1+(1-α)x2处的函数值,所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方.

个人感觉，这里的凸函数实际上就是我们初中时所学的“下凹函数”，当然，对于凸函数与凹函数，在学术界好像也没有特别严密的定义，每个学校都不一样，看自己啦~~

**性质1：**设f(x)是凸集D Rn上的凸函数,实数k≥0,则kf(x)也是D上的凸函数

**性质2：**设f1(x), f2(x)是凸集D上的凸函数,实数λ,µ≥0,则λf1(x)+µ f2(x)也是D上的凸函数

**性质3：**设f(x)是凸集D Rn上的凸函数,β为实数，则水平集S(f,β)={x|x∈D,f(x)≤β }是凸集。

凸函数的判断：

当然可以采用定义来判断，但这里似乎给出了更简单的判断方法：

设f(x)定义在凸集D Rn上,x,y∈D. 令Φ (t)=f (tx+(1-t)y), t ∈ [0,1],则

1、f(x)是凸集D上的凸函数的充要条件是对任意的x ∈ D,一元函数Φ (t)为[0,1]上的凸函数.2、f(x)是凸集D上的严格凸函数的充要条件是对任意的x,y ∈ D(x≠y),一元函数Φ (t)为[0,1]上的严格凸函数

该定理的几何意义是:凸函数上任意两点之间的部分是一段向下凸的弧线.

下面是这个判断方法的代码实现：

import random as rndef hanshu(x):return float((x-1)*(x-1))def hanshuq(x,y,t):return float(hanshu(t*x+(1-t)*y))if __name__=="__main__":a=float(input('请输入范围左端点横坐标'))b=float(input('请输入范围右端点横坐标'))c=float(input('请输入范围左端点纵坐标'))d=float(input('请输入范围右端点纵坐标'))flag=1for i in range(100):x=rn.uniform(a,b)y=rn.uniform(c,d)x0=rn.uniform(0,1)y0=rn.uniform(0,1)z=rn.uniform(0,1)if(hanshuq(x,y,z*x0+(1-z)*y0)<(z*hanshuq(x,y,x0)+(1-z)*hanshuq(x,y,y0))):flag=1else:flag=0breakif(flag==1):print('是凸函数')else:print('不是凸函数')

不知道为什么，感觉更复杂了呢~

一阶条件：

1、设在凸集D Rn上f(x)可微,则f(x)在D上为凸函数的充要条件是对任意的x,y ∈ D,都有

f(y)≥f(x)+ f(x)T(y-x)

2、设在凸集D Rn上f(x)可微,则f(x)在D上为严格凸函数的充要条件是对任意的x,y ∈ D, x≠y,都有

f(y)>f(x)+ f(x)T(y-x)

二阶条件：

设在开凸集D Rn上f(x)可微,则1、f(x)是D内的凸函数的充要条件为,在D内任一点x处, f(x)的Hesse矩阵G(x)半正定,其中

2、若在D内G(x)正定,则f(x)在D内是严格凸函数.