凸优化问题

原文链接:http://www.cnblogs.com/nxf-rabbit75/p/11452907.html

一、无约束优化

对于无约束的优化问题,直接令梯度等于0求解。

如果一个函数$f$是凸函数,那么可以直接通过$f(x)$的梯度等于0来求得全局极小值点。

?

二、有约束优化

?

?

  • 若$f(x),h(x),g(x)$三个函数都是线性函数,则该优化问题称为线性规划。若任意一个是非线性函数,则称为非线性规划
  • 若目标函数为二次函数,约束条件全为线性函数,称为二次规划
  • 若$f(x)$为凸函数,$g(x)$为凸函数,$h(x)$为线性函数,则该问题称为凸优化。注意这里不等式约束$g(x)<=0$则要求$g(x)$为凸函数,若$g(x)>=0$则要求$g(x)$为凹函数。

1.只含有等式约束

对于含有等式约束的优化问题,拉格朗日乘子法,构造拉格朗日函数,令偏导为0求解。

(1)优化问题是凸优化

通过下图两个条件求得的解就是极小值点(而且是全局极小)

(2)优化问题不是凸优化

上面两个条件只是极小值点的必要条件,还需要附加多一个正定的条件才能变成充要条件

?

2.只含有不等式约束

对于含有不等式约束的优化问题,同样构造拉格朗日函数,利用KKT条件求解。

对于不等式约束$g(x)<=0$,和等式约束$h(x)=0$不一样,$h(x)=0$可以在平面上画出一条等高线,而$g(x)<=0$是一个区域,很多个等高线堆叠而成的一块区域,我们把这块区域称为可行域。

  • (不考虑可行域限制时的)极小值点落在可行域内(不包含边界)

这个时候可行域的限制不起作用,相当于没有约束,直接$f(x)$的梯度等于0求解,这个时候$g(x极小值点)<0$(因为落在可行域内)。

  • (不考虑可行域限制时的)极小值点落在可行域外(包含边界)

可行域的限制起作用,极小值点应该落在可行域边界上即$g(x)=0$,类似于等值约束,此时有$g(x)$的梯度和$f(x)$的负梯度同向。

总结以上两种情况,可以构造拉格朗日函数来转换求解问题。

(1)优化问题是凸优化

对于不等式约束的优化,需要满足三个条件,满足这三个条件的解x*就是极小值点。

这三个条件就是着名的KKT条件,它整合了上面两种情况的条件。

特别注意:优化问题是凸优化的话,KKT条件就是极小值点(而且是全局极小)存在的充要条件。

?

(2)优化问题不是凸优化

约束问题不是凸优化,KKT条件只是极小值点的必要条件,不是充分条件,KKT点是驻点,是可能的极值点。也就是说,就算求得的满足KKT条件的点,也不一定是极小值点,只是说极小值点一定满足KKT条件。

不是凸优化的话,还需要附加多一个正定的条件才能变成充要条件,如下图所示

?

?

?3.既有等式约束也有不等式约束

?

?

?4.凸优化的应用

?

?

?

?

?

?

?

参考文献:

【1】Lagrange Multipliers and the Karush-Kuhn-Tucker conditions

【2】拉格朗日对偶性

转载于:https://www.cnblogs.com/nxf-rabbit75/p/11452907.html

原文地址: