凸优化和非凸优化
学习笔记，仅供参考
转载自：凸优化和非凸优化
数学中最优化问题的一般表述是求取 x ∗ ∈ χ x^{*} \in \chi x∗∈χ，使 f ( x ∗ ) = m i n { f ( x ) : x ∈ χ } f(x^{*} )=min\{f(x):x\in \chi \} f(x∗)=min{f(x):x∈χ}，其中x是n维向量， χ \chi χ是x的可行域，f是 χ \chi χ上的实值函数。
凸优化问题是指：
χ
\chi
χ是闭合的凸集，且f是
χ
\chi
χ上的凸函数的最优化问题，这两个条件任一不满足则该问题即为非凸的最优化问题。
其中，
χ
\chi
χ是 凸集是指对集合中的任意两点
x
1
,
x
2
∈
χ
x_{1},x_{2}\in \chi
x1,x2∈χ，有
t
x
1
+
(
1
−
t
)
x
2
∈
χ
,
t
∈
[
0
,
1
]
tx_{1}+(1-t)x_{2}\in \chi,t\in[0,1]
tx1+(1−t)x2∈χ,t∈[0,1]，即任意两点的连线段都在集合内，直观上就是集合不会像下图那样有凹下去的部分。
至于闭合的凸集，则涉及到闭集的定义，而闭集的定义又基于开集，比较抽象，不赘述，这里可以简单地认为闭合的凸集是指包含有所有边界点的凸集。
注意：*数学界某些机构关于函数凹凸性定义和国外的定义是相反的。Convex Function在某些*的数学书中指凹函数。Concave Function指凸函数。但在*涉及经济学的很多书中，凹凸性的提法和其他国家的提法是一致的，也就是和数学教材是反的。举个例子，同济大学高等数学教材对函数的凹凸性定义与本条目相反，本条目的凹凸性是指其上方图是凹集或凸集，而同济大学高等数学教材则是指其下方图是凹集或凸集，两者定义正好相反。
为什么要求是凸函数呢？因为如果是下图这样的函数，则无法获得全局最优解。
为什么要求是凸集呢？因为如果可行域不是凸集，也会导致局部最优:
实际建模中判断一个最优化问题是不是凸优化问题一般看以下几点：
- 目标函数f如果不是凸函数，则不是凸优化问题
- 决策变量x中包含离散变量（0-1变量或整数变量），则不是凸优化问题
- 约束条件写成 g ( x ) ≤ 0 g(x) \le 0 g(x)≤0时，g如果不是凸函数，则不是凸优化问题
- 之所以要区分凸优化问题和非凸的问题原因在于凸优化问题中局部最优解同时也是全局最优解，这个特性使凸优化问题在一定意义上更易于解决，而一般的非凸最优化问题相比之下更难解决。
非凸优化问题如何转化为凸优化问题的方法：
1）修改目标函数，使之转化为凸函数
2）抛弃一些约束条件，使新的可行域为凸集并且包含原可行域