我们知道，对于线性规划:

min z=f(x)

Subject to:Ax≤b

(此处x和b均为列向量)

通常的解法是单纯形法，它通过遍历约束区域的顶点来寻找最优解。但是当目标函数不再是一次函数，而是非线性方程时，最优解就不能确保出现在约束区域的顶点上，此时单纯形法不再适用。对于线性约束的非线性规划，使用内点法比较合适。而且就时间复杂度而言，内点法要比单纯形法更优（单纯形法是指数级的，内点法是幂级的）。

内点法的原理可以归结为上图：

假设最优点P在约束区域的边界上，我们可以选取一个起点 S_{0} ，每次确定一个使目标函数值递减的搜索向量 d_{k},k=0,1,2,3,4 。在搜索四次后找到最优点P。搜索向量 d_{k} 一般选取为负梯度，这样每次搜索的结果很大程度上会让目标函数减少，当后面我们求解的梯度为0向量时，说明我们找到了一个局部最优解。本文不讨论目标函数有多个局部最优解的情况。

但是情况并不总是如此，我们的目标函数可能没有极值点，或者说极值点不在约束区域内，这时候我们如果要搜索到最优点P，很有可能会在其中某一步就撞上了约束边界：

比如上图，我们搜索至 S_{2} 后，计算出了下一个搜索向量 d_{3} ,但是经过 d_{3} 的变换后，下一步到达 S_{3}^{'} ，跃出了边界。我们这时可以通过求交点来得到处于边界AB上的 S_{3} ，具体做法很简单，令 S_{3}=aS_{2}+(1-a)S_{3}^{'} ,带入到点线距离公式 d=\frac{|Ax+By+C|}{\sqrt{A^{2}+B^{2}}}（这个公式可以拓展到高维空间） ,最后平方得到一个关于a的二次函数，通过找对称轴来求出a的取值，从而确定 S_{3} 。

但是从 S_{3} 开始，我们很可能会求出目标函数在 S_{3} 处的梯度 g_{3} 如上图所示，此时我们计算出来的搜索向量 d_{4}^{'} 会让我们的下一步搜索结果跑到约束区域外，这时候上面的办法不再适用。我们要得到合理的搜索向量 d_{4}（沿着约束边界） ,就要想办法把向量 d_{4}^{'} 给投影到约束区域上。在如图所示的二维平面里，求解向量投影很简单，但是我们要推广到高维空间，所以这里不再进行几何求解。

我们在这里规定，当当前搜索起点处于约束区域的边界上，而且以负梯度作为搜索向量会让下一个搜索点脱离约束区域，那么我们称当前搜索起点所处的边界约束是起作用的，这些起作用的约束不等式此时成为等式约束，而且在搜索到局部最优值前，每一步的起作用的约束条件个数始终低于空间维数。

这段话其实理解起来并不困难，如果我们起点在边界上，下一步搜索向量会让起点回到约束区域内，那么我们直接按这个向量搜索就行，根本不需要花里胡哨的操作。在二维空间里的搜索，起作用约束最多一个，如果有两个约束条件起作用，那必然约束到了一个确定的点上——那说明我们找到了局部最优解。在三维空间里，有一个起作用约束，那我们的当前起点必然在这个起作用约束确定的平面上；如果有两个起作用约束，那么当前起点必然在这两个约束平面交会的棱上；如果有三个起作用约束，此时这三个平面必然会确定一点——我们找到了局部最优解。这些性质推广到高维空间也是一样。

我们知道，对于直线Ax+By+C=0,向量(A,B)是其法向量；对于平面Ax+By+Cz+D=0,向量(A,B,C)是其法向量；对于高维的线性几何体(我不知道叫啥) A_{1}x_{1}+A_{2}x_{2}.....A_{n}x_{n}+K=0 ,向量 (A_{1},A_{2}....A_{n}) 也是它的法向量(证明很简单，这里不证)。而我们搜索的当前起点如果有n-1个起作用约束，那么这n-1个约束的法向量(记为列向量 k_{i} )，必然可以通过某一个线性组合，将向量a给投影到它们的约束交集上，经过投影后的向量记为b。这里假设a,b和这些法向量均是n维向量，记作： b=a+\lambda_{1}k_{1}+\lambda_{2}k_{2}...+\lambda_{n-1}k_{n-1} （ \lambda_{k} 为系数，不是向量）,且 b^{T}k_{i}=0 (要证明很简单，我们只需要不停地在前一个等式左乘行向量 k_{i}^{T} ,得到n-1个线性方程组来证明，这些法向量都是线性无关的)。

我们清楚， 这些列向量k_{i} 必然是约束条件Ax≤b中，其系数矩阵A的某个行向量的转置，我们把这些行向量抠出来组成矩阵 A_{q} ,同时，我们把向量a替换为负梯度 d_{k}^{'} ，向量b替换为投影后的向量 d_{k} ,所有的 \lambda_{k} 按顺序排列记为列向量 \lambda ，那么我们可以得到等式1： d_{k}=d_{k}^{'}+A_{q}^{T}\lambda 。由于列向量 d_{k} 要求与 A_{q} 中每一个行向量正交，因此我们可以在等式两端左乘 A_{q} ，得到等式2： 0=A_{q}d_{k}^{'}+A_{q}A_{q}^{T}\lambda 。此时我们可以解出：

\lambda=-(A_{q}A_{q}^{T})^{-1}A_{q}d_{k}^{'} ,再把这个结果带回到等式1中，可得： d_{k}=[E-A_{q}^{T}(A_{q}A_{q}^{T})^{-1}A_{q}]d_{k}^{'} ,此时，我们令矩阵 P=E-A_{q}^{T}(A_{q}A_{q}^{T})^{-1}A_{q} ,则 d_{k}=Pd_{k}^{'} 就是我们的投影变换，我们把矩阵P 称作投影矩阵，它能确保我们的搜索不会脱离约束区域。由于矩阵 A_{q} 一般不满秩，因此我们的投影矩阵 P 一般不会是0矩阵。如果矩阵 A_{q} 满秩，那我们的的投影矩阵 P 必然是0矩阵，说明我们在当前搜索起点已经有了n个起作用约束(n是空间维数，也就是变量个数)，它们交会在了一个点上，我们找到了一个局部最优解。

当然，如果矩阵 P 不是0矩阵，但是只要负梯度经投影后为0向量，那说明我们当前的搜索点也是一个局部最优解，而且它符合KKT条件。