非线性规划参考资料
http://web.mit.edu/15.053/www/AMP-Chapter-13.pdf
以下内容翻译自上面的 PDF 文件.
非线性规划问题(Nonlinear programming problem, NLP)
决策变量(decision variables) $x_1,x_2,\ldots,x_n$
给定一个可行域 (feasible region)
使给定的目标函数(objective function) $f(x_1,x_2,\ldots,x_n)$ 取最优值(最小或最大值).
若目标函数是非线性的, 并且(或者)可行域由非线性约束所决定, 则称这样的最优化问题为非线性规划问题(nonlinear programming problem, NLP).
于是最大值优化问题的一般形式为:
\[
\mathrm{Maximize}\ f(x_1,x_2,\ldots,x_n),
\]
其中 $x_1,x_2,\ldots,x_n$ 满足
\[
\begin{cases}
g_1(x_1,x_2,\ldots,x_n)&\leqslant b_1,\\
g_2(x_1,x_2,\ldots,x_n)&\leqslant b_2,\\
\vdots & \quad\vdots\\
g_m(x_1,x_2,\ldots,x_n)&\leqslant b_m.\\
\end{cases}
\]
这里 $g_1,g_2,\ldots,g_m$ 是给定的.
注意到决策变量的非负性可以等价于添加如下约束:
\[
g_{m+i}(x_1,x_2,\ldots,x_n)=-x_i\leqslant 0,\quad(i=1,2,\ldots,n).
\]
有时这些非负性约束可以明确的写出, 如 $x_i\geqslant 0$, $i=1,2,\ldots,n$. 在其他情形, 如同上面给出的形式, 用单纯形方法隐式处理非负性约束的方法来隐式地考虑它们将会很方便.
为记号方便, 我们通常令 $x$ 为由 $x_1,x_2,\ldots,x_n$ 构成的 $n$ 维向量, 即 $x=(x_1,x_2,\ldots,x_n)$. 并且将问题明确写为:
\[
\mathrm{Maximize}\ f(x),
\]
其中 $x$ 的约束为:
\[
g_i(x)\leqslant b_i.\quad(i=1,2,\ldots,m).
\]
在线性规划中, 我们不会局限于这个公式. 为最小化 $f(x)$, 当然最大化 $-f(x)$. 等式约束 $h(x)=b$ 可以写成两个不等式约束: $h(x)\leqslant b$ 且 $-h(x)\leqslant -b$.
此外, 如果我们引入一个松弛变量(slack variable), 每个不等式约束转换为等式约束. 于是有时我们将考虑如下的等式形式:
\[
\mathrm{Maximize}\ f(x),
\]
约束为:
\[
\begin{cases}
h_i(x)&=b_i,\quad(i=1,2,\ldots,m),\\
x_j &\geqslant 0,\quad(j=1,2,\ldots,n).
\end{cases}
\]
通常问题的上下文会建议等式或不等式形式的约束(或者两者皆有), 而我们也不必强制地将问题的形式从其中一种形式转换为另一种形式.