二次规划问题
是一种典型的优化问题，包括凸二次规划和非凸二次规划，在此类问题中，目标函数是变量的二次函数，约束条件是变量的线性不等式。

假定变量的个数为 d <script type="math/tex" id="MathJax-Element-1">d</script>，约束条件的个数为m<script type="math/tex" id="MathJax-Element-2">m</script>，则标准的二次规划问题形如：

<script type="math/tex; mode=display" id="MathJax-Element-3">\begin{matrix} \min_{x} &\frac{1}{2}x^TQx+c^Tx\\ s.t.&Ax \leqslant b \end{matrix} </script>
其中 x <script type="math/tex" id="MathJax-Element-4">x</script>为d<script type="math/tex" id="MathJax-Element-5">d</script>维向量， Q∈Rd×d <script type="math/tex" id="MathJax-Element-6">Q\in \mathbb{R^{d\times d }}</script>为实对称矩阵， A∈Rm×d <script type="math/tex" id="MathJax-Element-7">A\in \mathbb{R^{m \times d }}</script>为实矩阵， b∈Rm <script type="math/tex" id="MathJax-Element-8">b\in \mathbb{R^m}</script>和 c∈Rd <script type="math/tex" id="MathJax-Element-9">c\in \mathbb{R^d}</script>为实向量， Ax⩽b <script type="math/tex" id="MathJax-Element-10">Ax \leqslant b</script>的每一行对应一个约束。

• 若 Q <script type="math/tex" id="MathJax-Element-11">Q</script>为半正定矩阵，则上面的目标函数是凸函数，相应的二次规划为凸二次规划问题；此时若约束条件定义的可行域不为空，且目标函数在此可行域有下界，则该问题有全局最小值。
• 若Q<script type="math/tex" id="MathJax-Element-12">Q</script>为正定矩阵，则该问题有唯一的全局最小值。
• 若 Q <script type="math/tex" id="MathJax-Element-13">Q</script>为非正定矩阵，则目标函数是有多个平稳点和局部极小点的NP难问题。

常用的二次规划问题求解方法有：

• 椭球法
• 内点法
• 增广拉格朗日法
• 梯度投影法
  等。若Q<script type="math/tex" id="MathJax-Element-14">Q</script>为正定矩阵，则相应的二次规划问题可由椭球法在多项式时间内求解。

凸函数：

对区间 [a,b] <script type="math/tex" id="MathJax-Element-15">[a,b]</script>上定义的函数 f <script type="math/tex" id="MathJax-Element-16">f</script>，若它对区间中任意两点x1,x2<script type="math/tex" id="MathJax-Element-17">x_1,x_2</script>均有：

<script type="math/tex; mode=display" id="MathJax-Element-18">f\left ( \frac{x_1+x_2}{2} \right )\leqslant \frac{f(x_1)+f(x_2)}{2}</script>则称 f <script type="math/tex" id="MathJax-Element-19">f</script>为区间[a,b]<script type="math/tex" id="MathJax-Element-20">[a,b]</script>上的凸函数。

U <script type="math/tex" id="MathJax-Element-21">U</script>形曲线的函数如f(x)=x2<script type="math/tex" id="MathJax-Element-22">f(x)=x^2</script>，通常是凸函数。

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

• 若二阶导数在区间上非负，则称为凸函数
• 若二阶导数在区间上恒大于0，则称严格凸函数

矩阵的正定及半正定：
正定矩阵是一种实对称矩阵。正定二次型 f(x1，x2，…，xn)=XTAX <script type="math/tex" id="MathJax-Element-23">f(x_1，x_2，…，x_n)=X^TAX</script>的矩阵A(或A的转置)称为正定矩阵。

1. 广义定义：设 M <script type="math/tex" id="MathJax-Element-24">M</script>是n阶方阵，如果对任何非零向量z<script type="math/tex" id="MathJax-Element-25">z</script>，都有 zTMz>0 <script type="math/tex" id="MathJax-Element-26">z^TMz> 0</script>，其中 zT <script type="math/tex" id="MathJax-Element-27">z^T</script> 表示 z <script type="math/tex" id="MathJax-Element-28">z</script>的转置，就称M正定矩阵。

2. 狭义定义：一个n阶的实对称矩阵M<script type="math/tex" id="MathJax-Element-29">M</script>是正定的的条件是当且仅当对于所有的非零实系数向量z，都有 zTMz>0 <script type="math/tex" id="MathJax-Element-30">z^TMz> 0</script>。其中 zT <script type="math/tex" id="MathJax-Element-31">z^T</script>表示 z <script type="math/tex" id="MathJax-Element-32">z</script>的转置。

当考虑矩阵的特征值时：

• 若所有特征值均不小于零，则称为半正定。
• 若所有特征值均大于零，则称为正定。

任意给一个对称阵，做他的特征分解：M=QTΛQ<script type="math/tex" id="MathJax-Element-33">M=Q^T \Lambda Q</script>，那么, xTMx=(Qx)TΛQx <script type="math/tex" id="MathJax-Element-34">x^TMx=(Qx)^T \Lambda Qx</script>。这里，由于Q是一个正交阵，则Qx为x的一个线性变换。考虑到定义中x具有任意性，显然Qx也具有任意性。令 y=Qx <script type="math/tex" id="MathJax-Element-35">y=Qx</script>，即原定义等价于分析是否存在任意的y，使得 yTΛy≥0 <script type="math/tex" id="MathJax-Element-36">y^T \Lambda y \ge0</script>恒成立。也就是说：分析对称阵的正定性，等价于分析其特征值对角阵的正定性。
为了叙述方便，记 Λ=diag(λ1,…,λi,…,λn) <script type="math/tex" id="MathJax-Element-37">\Lambda = diag(\lambda_1, \dots, \lambda_i, \dots,\lambda_n)</script>。容易知道，特征值对角阵 Λ <script type="math/tex" id="MathJax-Element-38">\Lambda</script>是正定阵必须要求所有特征值为正，半正定则要求所有特征值非负。关键在于正定性定义中x具有任意性。

从几何的角度看的话：
首先半正定矩阵定义为: XTMX≥0 <script type="math/tex" id="MathJax-Element-39"> X^TMX \geq 0</script>其中X 是向量，M 是变换矩阵
矩阵变换中， MX <script type="math/tex" id="MathJax-Element-40">MX</script>代表对向量 X进行变换，我们假设变换后的向量为Y，记做 Y=MX <script type="math/tex" id="MathJax-Element-41">Y=MX</script>。于是半正定矩阵可以写成： XTY≥0 <script type="math/tex" id="MathJax-Element-42"> X^TY \geq 0</script>
又因为： cos(θ)=XTY||X||∗||Y|| <script type="math/tex" id="MathJax-Element-43">cos(\theta) = \frac{X^TY}{||X||* ||Y||}</script>
所以： cos(θ)≥0 <script type="math/tex" id="MathJax-Element-44">cos(\theta)\geq 0</script>
正定、半正定矩阵的直觉代表一个向量经过它的变化后的向量与其本身的夹角小于等于90度。

参考：

https://www.zhihu.com/question/22098422?sort=created

《机器学习》–周志华