一、凸函数 什么是凸函数。 关于凸函数的定义： 对于任意 λ ∈ [ 0 , 1 ] \lambda∈[0,1] λ∈[0,1],如果 f ( λ x + ( 1 − λ ) y ) < λ f ( x ) + ( 1 − λ ) f ( y ) f(\lambda x+(1-\lambda)y)<\lambda f(x)+(1-\lambda) f(y) f(λx+(1−λ)y)<λf(x)+(1−λ)f(y) 我们则称，这个函数是凸函数。 什么意思呢，我们在目标函数上取两个点，然后计算出 f ( λ x + ( 1 − λ ) y ) f(\lambda x+(1-\lambda)y) f(λx+(1−λ)y)看点的值和这个值的大小来进行凸函数的比较。 （2）如果这个处处二阶可导，那么我们可以采用二阶导数来判断 即设目标函数为f(x),则f（x）是凸函数的必要条件为 f ( 2 ) ( x ) > 0 f^{(2)}(x)>0 f(2)(x)>0 即函数的斜率不断在变大。 这是凸函数的定义，那么我们用例子来看看： 所以，我们寻找凸函数一般用凸函数的定义去寻找就行了，或者采用2阶导数的条件寻找。注意一般如果采用定义1去寻找的话，会采用多个点去找寻，避免随机性导致的判断 1.2 凸集 如果在函数的定义范围内，满足对于任意 λ ∈ [ 0 , 1 ] \lambda∈[0,1] λ∈[0,1] f ( λ x + ( 1 − λ ) y ) < λ f ( x ) + ( 1 − λ ) f ( y ) f(\lambda x+(1-\lambda)y)<\lambda f(x)+(1-\lambda) f(y) f(λx+(1−λ)y)<λf(x)+(1−λ)f(y)的解的集合就被称为凸集。 如上面 f ( x ) = x 3 f(x)=x^{3} f(x)=x3的 （ 0 ， + ∞ ） （0，+∞） （0，+∞）为凸集， ( − ∞ ， 0 ) (-∞，0) (−∞，0)就不是。 1.3 如何对多元函数进行凸函数的判断 方法一： 采用定义法，采用蒙特卡洛采样了很多很多次，每次都计算一次中间值和两边值分别进行比较，如果其中有个别点满足凸函数定义，那么这个函数就是凸函数。 方法2： 采用二阶偏导，看二阶偏导是否大于0。
对于非凸函数来说，我们可能不好求得函数的最小值，或者无约束条件下并不满足函数的最小值。
二、kkt条件 kkt条件是用来解决不等值约束条件下，求解极值的最优解的问题。为了理解不等值约束我们先从最基本的求极值的思路开始。 首先从无约束的优化问题讲起，一般就是要使一个表达式取到最小值： m i n x f ( x ) \mathop{min}\limits_{x}f(x) xminf(x)。对于这类问题在高中就学过怎么做。只要对它的每一个变量求导，然后让偏导为零，解方程组就行了。 所以在极值点处一定满足 d f ( x ) / d x = 0 df(x)/dx=0 df(x)/dx=0 （只是必要条件，比如 y = x 3 y=x^3 y=x3 在 x=0 处就不是极值点），然后对它进行求解，再代入验证是否真的是极值点就行了。 1、等值优化问题最优性条件 比如有一个等式约束：
min f(x) s.t h(x)=0这时相当于我们的f(x)的负梯度方向为图中的中心，由中心向外为函数的等高线，当等高线和h（x）想切时刚好为约束条件下的极值点。但是要注意f(x)与g（x）的约束条件必须是凸函数和凸集才行，否则我们求出来的点也不一定是最小值点。 例 因为f(x)不是凸函数，且所以求出来的值不是最优解，且在约束条件g(x)所在的范围内也不是凸集。因为 当 x ∈ （ − ∞ ， + ∞ ） x∈（-∞，+∞） x∈（−∞，+∞）时， y ∈ ( − ∞ ， 0 ) y∈(-∞，0) y∈(−∞，0),而所以只要y不断减小，x不断变大，此时目标函数只有最大值，没有最小值。 如果f(x)是凸函数，h(x)=0所在的集合又是凸集。那么我们只需要对多个约束条件，分别求偏导，对求出来的多个极值点带入目标函数进行检验，最后选出一个极小值解就行了。 即： 2、不等式约束优化问题 此时g(x)<0。 （2）边界解：当解集在边界时，此时λ>0。且g(x)=0。 但不管解集是否在边界，一定满足一下条件： 这些条件合称为Karush-Kuhn-Tucker (KKT)条件。但是我们在运用kkt条件时一般会有一些约束条件。 当然kkt条件的使用必须有一定的限制，即regularity条件。
2、regularity条件。 （1）如果h（x）与g(x)都是形如 a x + b ax+b ax+b这样的映射函数，则kkt条件的值一定是最小值 （2）起作用的g(x)和h（x)的在极值处的梯度要线性无关 （3）优化问题是凸优化问题 3、 缺少regularity条件KKT还是最优解的必要条件吗？ 若满足regularity条件，KKT就是最优解的必要条件。所谓必要条件的意思是满足KKT条件的不一定是最优解（例如鞍点就满足KKT，但鞍点就不是最优解），但是如果不满足KKT条件就一定不是最优解，缺少了regularity条件，KKT条件就并非最优解的必要条件。 那么我们怎么判断，这个目标函数的优化是否是符合regularity条件的呢。我们可以采用fritz条件来判断 3、fritz条件 即我们要求利用kkt条件求出来的解为最小解，那么在目标函数前的 μ 0 \mu_0 μ0一定是大于0的。此时 若满足fritz条件，那么求出的解为最优解。若 μ 0 \mu_0 μ0=0代表此时目标函数不受约束，即无最小值。 4、例子
