什么是凸优化问题

2021年6月17日 3点热度 0条评论 来源: turinglife

https://zh.wikipedia.org/wiki/%E5%87%B8%E5%87%BD%E6%95%B0


数学中最优化问题的一般表述是求取

,使

,其中

是n维向量,



的可行域,



上的实值函数。凸优化问题是指
是闭合的凸集合且

上的凸函数的最优化问题,这两个条件任一不满足则该问题即为非凸
的最优化问题。




其中,
是凸集是指对集合中的任意两点

,有

,即任意两点的连线段都在集合内,直观上就是集合不会像下图那样有”凹下去”的部分。至于闭合的凸集,则涉及到闭集的定义,而闭集的定义又基于开集,比较抽象。这里可以简单认为闭合的凸集是指包含有所有边界的凸集。






凸函数是一个定义在某个向量空间

凸子集


区间
)上的
实值函数

如果在其
定义域

上的任意两点

,以及

,有


也就是说,一个函数是凸的
当且仅当

上境图
(在
函数图像
上方的
点集
)为一个
凸集




特别注意:中国大陆统计大学对于函数凹凸性的定义正好与此相反。 本文中的凹凸性是指蓝色线上方区域是凹集还是凸集,
而同济大学高等数学教材则是指其下方图是凹集或凸集,两者定义正好相反。
本文中,蓝色函数,应为凸函数,因为蓝色上方部门的区域为凸集,然后,按照同济大学的定义的话,该蓝色函数为凹函数,因为蓝色线下方的区域为凹集。


为什么要求是凸函数呢?
因为如果是下图这样的函数,则无法获得全局最优解。



为什么要求是凸集呢?因为如果可行域不是凸集,也会导致局部最优






实际建模中,判断一个最优化问题是不是凸优化问题一般看以下几点:

1. 目标函数f如果不是凸函数,则不是凸优化问题。 2. 决策变量

中包含离散变量(0-1变量或整数变量),则不是凸优化问题
3. 
约束条件写成

时,

如果不是凸函数,则不是凸优化问题

之所以要区分凸优化问题和非凸的问题原因在于凸优化问题中局部最优解同时也是全局最优解,这个特性使凸优化问题在一定意义上更易于解决,而一般的非凸最优化问题相比之下更难解决。



非凸优化问题如何转化为凸优化问题的方法:
1)修改目标函数,使之转化为凸函数
2)抛弃一些约束条件,使新的可行域为凸集并且包含原可行域

    原文作者:turinglife
    原文地址: https://blog.csdn.net/Turinglife/article/details/49307097
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。