1 非线性规划问题（nonlinear programming problems）
在可行域内选取n个变量x_1,x_2,\ldots ,x_N，组成目标函数f(x_1,x_2,\ldots,x_n)非线性规划问题是指目标函数为非线性函数或者可行域边界为非线性约束时，求解目标函数最值的问题。当求最大值时可以表示为
目标函数：\max f(x_1,x_2,\ldots,x_n)约束条件：g_1(x_1,x_2,\ldots,x_n)\leqslant b_1\\ \cdots \\g_m(x_1,x_2,\ldots,x_n)\leqslant b_n
其中函数 f,g_1,\ldots,g_m 都是已知的函数，需要做的是求出一组 x_1,x_2,\ldots,x_n 时目标函数得到最值。
为了表达方便，后面简写为
目标函数：\max f(x) 约束条件： g_i(x)\leqslant b_i \quad (j=1,2,\ldots,m)
2 可分离规划（seprable programming）
如果目标函数和约束条件中的每一个变量x_i,\ i=1,\ldots ,n都可以分离开，那么称这样的问题为可分离规划问题。
考虑问题：
目标函数\max f(x)=20x_1+16x_2-2x^2-x_2^2-(x_1+x_2)^2约束条件x_1+x_2 \leqslant 5\\x_1 \geqslant 0 \\ x_2 \geqslant 0
因为目标函数中(x_1+x_2)^2的存在所以这个问题不是可分离规划问题，但是可以通过一个简单变化变为可分离规划问题。
令x_3=x_1+x_2，重写问题：
目标函数\max f(x)=20x_1+16x_2-2x^2-x_2^2-x_3约束条件x_1+x_2 \leqslant 5\\x_1+x_2-x_3=0\\x_1 \geqslant 0 \quad x_2 \geqslant 0 \quad x_3 \geqslant 0
这样，该问题就变可分离了。f(x)=f_1(x)+f_2(x)+f_3(x)，其中f_1(x_1)=20x_1-2x_1^2，f_1(x_2)=16x_2-x_2^2，f_3(x_3)=-x_3^2。之后分别对f_1,f_2,f_3进行线性化，即可使用线性规划问题的工具解决问题。
3 Frank-Wolfe 算法（Frank-Wolfe Algorithm）
- 以任意可行的解x^0=(x_1^0,x_2^0,\ldots,x_n^0)作为算法的起始位置（k=0）。
- 列写（3.2）计算其中的c_j
- 求解（3.2），记最优解为y^k
- 计算（3.1）在x^k,y^k连线上的最优解，记为x^k+1。返回步骤二，列写新的（3.2）。
考虑有着线性约束的非线性规划问题：
目标函数：\max f(x_1,x_2,\ldots,x_n)\tag{3.1} 约束条件： \sum^n_{j=1}a_{ij}x_j\leqslant b_i \quad (i=1,2,\ldots,m)\\ x_j\leqslant b_i \quad (j=1,2,\ldots,n)用 x^0=(x_1^0,x_2^0,\ldots,x_n^0) 表示该问题任意满足约束的解。
使用下面方法近似目标函数的非线性
f(x^0)+\sum^b_{j=1}c_j(x_j-x_j^0)
其中 c_j 是函数在点 x^0 处的斜率或关于 x_j 在 x_j^0 的偏导。
因为f(x^0), \ c_j, \ x_j^0都是常数，所以目标函数的可以简化为
z=\sum^n_{j=1}c_jx_j \tag{3.2} 用y^0=(y_1^0, y_2^0, \ldots, y_n^0)表示化简后的最优解。在x^0和y^0的连线上重新求解规划问题，得到一个新的解，表示为x^1。下面就可以用迭代的方式解出x^2, x^3, \ldots随着迭代的次数的增加，得到的解也会趋近取最优解。
4 MAP（method of approximation programming）
- 以任意可行的解x^0=(x_1^0,x_2^0,\ldots,x_n^0)作为算法的起始位置（k=0）。
- 分别计算线性规划问题（4.2）中在x^{k}的a_{ij}, b_i^k, c_j
- 求解出最优解x^{k+1}。返回步骤2，用新得到x^{k+1}替代x^k
Frank-Wolfe 算法的步长比较大，可能会错过最优解。MAP 方法在其基础上进行了修改，对每一步步长进行了限制。因此 MAP 也被成为小步过程（small-setp procedure）。
考虑非线性优化问题：
目标函数：\max f(x_1.x_2,\ldots,x_n)约束条件：g_i(x_1,x_2,\ldots,x_n)\leqslant 0 \quad (i=1, 2, \ldots, m) \tag{4.1}
上节中已经讨论了目标函数的线性化，这里直接讨论非线性约束的线性化。与前面类似的将约束条件线性化成 \hat{g}_i(x) =g_i(x^0) +\sum^N_{j=1} a_{ij} (x_j-x_j^0) \leqslant 0
其中a_{ij}是g_i(x)关于x_j在x^0的偏导数。
整理下可以得到\sum^n_{j=1}a_{ij}x_j\leqslant b^0_i \equiv \sum^n_{j=1}a_{ij}x^0_j-g_i(x^0)
综合得到 MAP 算法线性化后的问题为：
目标函数：\max z=\sum^n_{j=1}c_jx_j\tag{4.2}
约束条件：\sum^n_{j=1}a_{ij}x_j \leqslant b_i^0 \quad (i=1,2,\ldots,m)\\ x_0^j -\delta_j \leqslant x_j \leqslant x_j^0 +\delta_j (j= 1,2, \ldots, n)
目标函数和第一个约束条件分别是原非线性问题的线性化结果，第二个约束条件就是本节开头说的 MAP 对每步约束步长上限的要求。
5 广义规划（generalized programming）
- 在可行域内挑选 k 个解作为候选解
- 带入问题（5.1），计算每个约束的影子价格
- 检查是否有更好的候选解，如果没有则算法结束。如果有则问题（5.1）得到作为新的候选解，返回步骤2。
同样考虑非线性问题（4.1）。从可行域中挑选一些候选解 x^j=(x_1^j, x_2^j, \ldots, x_n^j), \quad j=1,2, \ldots, k 。这些候选解通过加权（\lambda_1, \lambda_2, \ldots, \lambda_k）生成一个解：
x_i= \lambda_1 x_i^1 +\lambda_2 x_i^2 +\cdots +\lambda_k x_i^k \quad (i=1,2,\ldots ,n)使用（4.1）的线性近似问题来来决定权
目标函数：\max \lambda_1f(x^1) +\lambda_2f(x^2) +\cdots +\lambda_k f(x^k) \tag{5.1}
约束条件：\lambda_1 g_1(x^1) +\lambda_2 g_1(x^2) +\cdots +\lambda_k g_1(x^k) \leqslant 0 \\ \vdots \\ \lambda_1g_m(x^1) +\lambda_2g_m(x^2) +\cdots +\lambda_k g_m(x^k) \leqslant 0 \\ \lambda_j \geqslant 0 \quad (j=1,2,\ldots ,k)
用 y_1, y_2, \ldots, y_{m+1} 表示上面约束的最优影子价格（optimal shadow prices）
影子价格（optimal shadow prices）是指当在约束的右侧常数项加1时，目标函数的变化量。仍然以问题（4.1）为例，用f(x^*)表示最优状态下的目标函数函数值。表示仅将i=1的约束条件修改为g_1(x_1,x_2,\ldots,x_n)\leqslant 1其他的约束条件保持不变。重新计算最优解，得到新的最优目标函数函数值为f'(x^*)。那么这两个函数值的差就是该约束条件的影子价格，即y_1=f'(x^*)-f(x^*)
影子价格标志着最优解受到各个约束的程度。影子价格为0时说明目前该约束对我们的求解过程没有起到约束作用。若一个约束的影子价格显著大于其他的约束，则说明该约束作用最强。
构造一个新的规划问题v=\max[f(x) -y_1g_1(x) -y_2g_2(x) -\cdots -y_mg_m(x)]在可行域内求出最佳的解，用v^*,x^*表示。其中f(x)是前面的目标函数，g_i(x)是约束条件。因为前面讨论的规划问题中约束条件都是小于等于0的，所以需要使g_i(x)尽量小，对其求反，变成一个求最大值的问题。各个约束条件相加时使用的权就是各自的影子价格。
如果v^*-y_{m+1} \leqslant 0，那么说明没有更好的解，算法结束。如果v^*-y_{m+1} > 0，那么将（5.1）求得的最优x作为x^{k+1}，然后重新计算。
6 二次规划（quadratic programming）
二次规划是解决二次目标函数在线性约束下的求最大值问题，形如
目标函数：\max f(x)=\sum^n_{j=1}c_jx_j +\frac{1}{2} \sum^n_{j=1} \sum^n_{k=1}q_{jk}x_jx_k
约束条件：\sum^n_{j=1}a_{ij}x_j\leqslant b_i \quad (i= 1, 2, \ldots, m) \\ x_j \geqslant \quad (j=1, 2, \ldots, n)
假设q_{jk}=q_{kj}。这并不会让问题丧失一般性，如果不满足可以用q'_{jk} =q'_{kj} =\frac{1}{2}(q_{jk}+q_{kj})替换。
使用类似线性规划优化（linear-programming optimality conditions）的方法列写最优条件（optimality conditions）
原始可行性：\sum^n_{j=1}a_{ij}x_j \leqslant b_i, \quad x_j \geqslant 0
对偶可行性：\sum^m_{i=1} y_i a_{ij} \geqslant c_j + \sum^n_{k=1} q_{jk} x_k, \quad y_i \geqslant 0
互补松弛性：y_i[b_i -\sum^n_{j=1}a_{ij}x_j]=0, \quad [\sum^m_{i=1} y_i a_{ij} -c_j -\sum ^n_{k=1}q_{jk}x_k]=0
这样就转换成了一个线性规划问题，可以使用单纯形法（Phase I simplex method）解决。
7 SUMT（Squential Unrestrained Maximization Technique）
SUMT 方法是将有约束的优化问题近似成一个无约束的优化问题。有约束的优化问题
目标函数：\min f(x)
约束条件：g_i(x) \leqslant b_i, \quad i=1, 2, \ldots, m
可以近为无约束的优化问题
目标函数：\min {f(x) +rP(x)}
其中 r \rightarrow + \infty，P(x)=\sum^m_{i=1} \max (g_i(x) -b_i ,0)^2
近似后的优化问题相较于之前，增加了惩罚函数P(x)。当 x 满足约束条件时，惩罚函数为0，而不满足时非零。因为惩罚函数前的系数趋近于正无穷，所以不满足约束条件会使整个目标函数变得非常小。
此外还可以应用阻碍法（barrier method）来实现去约束。该方法使用另一个惩罚函数
P(x) = \sum^m_{i=1} \frac{1}{(g_i(x)-b_i)^2}
与 SUMT 方法不同的是阻碍法仅在约束条件边界有作用（趋近于无穷）。为了减少惩罚函数在其他位置的影响，前面的系数 r 要尽量小。阻碍法的缺点是，就像它的名字一样，仅能起到阻碍作用。也就是 x 已经到可行域外的情况下不但无法帮助其回到可行域内，反而还会起到阻碍作用。