凸优化问题，凸二次规划问题QP，凸函数 - 好文

*
*
* 约束优化问题 <https://blog.csdn.net/promisejia/article/details/81241201#约束优化问题>
* 凸函数 <https://blog.csdn.net/promisejia/article/details/81241201#凸函数>
* 凸优化问题 <https://blog.csdn.net/promisejia/article/details/81241201#凸优化问题>
* 凸二次规划问题 <https://blog.csdn.net/promisejia/article/details/81241201#凸二次规划问题>

约束优化问题

min w  f(w)min w  f(w)

s.t.   gi(w)≤0    (i=1,...,k)         (1)s.t.   gi(w)≤0    (i=1,...,k)
(1)

        hj(w)=0    (j=1,...,l)         (2)        hj(w)=0    (j=1,...,l)
  (2)

注：

* 这是一个最小化问题.
* 不等式约束严格执行的含义是“小于等于号”变成“小于号”。
凸函数

对区间 [a,b][a,b] 上定义的函数 f，若它对区间中任意两点 x1,x2x1,x2均有：

f(x1+x22)≤f(x1)+f(x2)2f(x1+x22)≤f(x1)+f(x2)2

则称f为区间 [a,b][a,b]上的凸函数，这和高数上讲图形的形状时是不同的概念。

形曲线的函数如f(x)=x2f(x)=x2就是凸函数。

对实数集上的函数，可通过求解二阶导数来判别：

* 若二阶导数在区间上非负，则称为凸函数
* 若二阶导数在区间上恒大于0，则称严格凸函数
仿射函数也是凸函数，只是不是严格凸函数。

凸优化问题

凸优化问题是特殊的约束最优化问题。其一般形式形式和约束最优化问题一样。

假设f、g、h在定义域内是连续可微的，且目标函数f和不等式约束函数g是凸函数，等式约束h是仿射函数（线性函数），则这种约束最优化问题称为凸优化问题。
因此凸优化问题特征的重要特征：

* 目标函数f，不等式约束函数g是凸函数
* 等式约束h是仿射函数
* 满足约束最优化问题的一般形式
凸二次规划问题

凸二次规划问题是凸优化问题的一个特殊形式，当目标函数是二次型函数且约束函数 g 是仿射函数时，就变成一个凸二次规划问题。凸二次规划问题的一般形式为:

minxs.t.12xTQx+cTxWx⩽bminx12xTQx+cTxs.t.Wx⩽b

*
若 Q 为半正定矩阵
，则上面的目标函数是凸函数，相应的二次规划为凸二次规划问题；此时若约束条件定义的可行域不为空，且目标函数在此可行域有下界，则该问题有全局最小值。

*
若Q为正定矩阵，则该问题有唯一的全局最小值。
例如，最简单的正定矩阵就是单位矩阵。

凸二次规划问题的特征：

* 目标函数f是二次型函数函数
* 等式约束h是仿射函数
* 等式约g是仿射函数
* 满足约束最优化问题的一般形式
常用的二次规划问题求解方法有：

* 椭球法
* 内点法
* 增广拉格朗日法 <https://www.cnblogs.com/crackpotisback/p/6588947.html>
* 梯度投影法

热门工具换一换