凸函数与凸规划

对于约束优化问题

若f（X）、g_i（X）（i=1，2，…，m）都为凸函数，则称此问题为凸函数。

凸函数有如下性质：

1）若给定一点X₀，则集合S={X|f（X）≤f（X₀）}为凸集（此性质表明，凸规划的问题，目标函数的等值线是大圈套小圈的形式）。

证明：取集合S中任意两点X₁、X₂，则有f（X₁）≤f（X₀），f（X₂）≤f（X₀）。由于f（X）为凸函数，又有

若f（X）、g_i（X）（i=1，2，…，m）都为凸函数，则称此问题为凸函数。

凸函数有如下性质：

1）若给定一点X₀，则集合S={X|f（X）≤f（X₀）}为凸集（此性质表明，凸规划的问题，目标函数的等值线是大圈套小圈的形式）。

证明：取集合S中任意两点X₁、X₂，则有f（X₁）≤f（X₀），f（X₂）≤f（X₀）。由于f（X）为凸函数，又有

即点X=αX₁+（1-α）X₂满足f（X）≤f（X₀），故在S集合之内，根据凸集定义，S为凸集。

2）可行域S={Xg|_i（X）≤0，i=1，2，…，m}为凸集。

证明：在集合S内任意两点X₁、X₂，由于g_i（X）为凸函数，则有

g_i（αX₁+（1-α）X₂）≤αg_i（X₁）+（1-α）g_i（X₂）≤0

即点X=αX₁+（1-α）X₂满足g_i（X）≤0，故在集合S之内，为凸集。

3）凸规划的任何局部最优解就是全局最优解。

证明：设X₁为局部极小点，则在X₁某邻域内的X点有f（X）≥f（X₁）。假若X₁不是全局极小点，设存在X₂有f（X₁）＞f（X₂），由于f（X）为凸函数，故有

f（αX₁+（1-α）X₂）≤αf（X₁）+（1-α）f（X₂）(www.xing528.com)

＜αf（X₁）+（1-α）f（X₁）=f（X₁）

当α→1时点X=αX₁+（1-α）X₂进入X₁某邻域内，则将有

f（X₁）≤f（αX₁+（1-α）X₂）＜f（X₁）

这显然是矛盾的，所有不存在X₂使f（X₂）＜f（X₁），从而证明X₁应该为全局极小点。

即点X=αX₁+（1-α）X₂满足f（X）≤f（X₀），故在S集合之内，根据凸集定义，S为凸集。

2）可行域S={Xg|_i（X）≤0，i=1，2，…，m}为凸集。

证明：在集合S内任意两点X₁、X₂，由于g_i（X）为凸函数，则有

g_i（αX₁+（1-α）X₂）≤αg_i（X₁）+（1-α）g_i（X₂）≤0

即点X=αX₁+（1-α）X₂满足g_i（X）≤0，故在集合S之内，为凸集。

3）凸规划的任何局部最优解就是全局最优解。

证明：设X₁为局部极小点，则在X₁某邻域内的X点有f（X）≥f（X₁）。假若X₁不是全局极小点，设存在X₂有f（X₁）＞f（X₂），由于f（X）为凸函数，故有

f（αX₁+（1-α）X₂）≤αf（X₁）+（1-α）f（X₂）

＜αf（X₁）+（1-α）f（X₁）=f（X₁）

当α→1时点X=αX₁+（1-α）X₂进入X₁某邻域内，则将有

f（X₁）≤f（αX₁+（1-α）X₂）＜f（X₁）

这显然是矛盾的，所有不存在X₂使f（X₂）＜f（X₁），从而证明X₁应该为全局极小点。