非线性规划

约 2778 个字 预计阅读时间 9 分钟

Abstract

前面介绍的都是目标函数和约束条件都是自变量的线性函数，如果目标函数或约束条件中包含一个或者若干自变量的非线性函数，那么这样的规划问题就属于非线性规划（Nonlinear Programming)

5.1 概述

5.1.1 举例

• 某化学反应生成物浓度和时间t之间的关系是经验函数 \(\chi = c_1 + c_2 t + e^{c_3 t}\)，需要确定参数 \(c_1, c_2, c_3\) 使得理论曲线尽可能地和n个测试点吻合。

• 仓库选址问题：\(n\)个市场，第\(j\)个市场的位置\((a_j, b_j)\)，对某种货物的需求为\(q_j ( j = 1,2,...,n)\)。现在计划建立\(m\)个仓库，第\(i\)个仓库的容量为\(c_i ( i = 1,2,...,m)\)，试确定仓库位置，使各个仓库到各个市场的运输量和路程的乘积之和最小。

\[ \mathop{\min} \hspace{4pt} \sum \limits^{m}_{i = 1} \sum \limits^{n}_{j=1} w_{ij} \sqrt{(x_i - a_j)^2 + (y_i - b_j)^2}\]

\[s.t. \hspace{4pt} \left\{ \begin{aligned} \sum \limits^{n}_{j = 1} w_{ij} & \leq c_i, i = 1,..,m  \\ \sum \limits^{m}_{i=1} w_{ij} & = q_j, j = 1,2,...,n \\ w_{ij} & \geq 0, i = 1,..,m;j =1,2,...,n  \end{aligned} \right. \]

5.1.2 非线性规划的数学模型

非线性规划数学模型的一般形式是： \(min \hspace{4pt} f(x)\)

\[s.t. \left\{ \begin{aligned} g_i(x) & \geq 0, i = 1,2,...,l \\ h_j(x) & = 0, j = 1,2,...,m \end{aligned} \right. \tag{5.2}\]

这里的\(x = (x_1, x_2,...,x_n)^{T}\) 是\(n\)维空间\(R^{n}\)的点（向量），目标函数\(f(x)\)和约束函数\(g_i(x)，h_j(x)\) 是\(x\)的实函数，且其中至少有一个是\(x\)的非线性函数。\(g_i(x)\) 称为不等式约束，\(h_j(x)\) 是等式约束，若某个不等式是小于等于约束，同乘-1即可，同样，目标函数是极大的话，乘-1变号即可，如果是等式约束\(h_j(x) = 0\)，则用 \(h_j(x) \leq 0\) 和 \(h_j(x) \leq 0\)替换即可。

• 若令 \(\Omega\) 为问题的可行解集合（可行域），则上述模型可写为

\[\mathop{\min}\limits_{x \in \Omega} \hspace{2pt}f(x) \tag{5.4}\]

若\(\Omega = \{ x| g_i(x) \geq 0, i = 1,2,..,l \}\) 是 \(R^n\) 的一个子集。若 \(\Omega = R^n\) ，那么该问题就是一个无约束优化问题(Unconstrained Optimization Problem)，求目标函数极小值或极大值的优化问题也称为极值问题。

5.2 非线性规划问题的解

5.2.1 解（极值点）的定义

• 局部极小点：若存在某个 \(\varepsilon > 0\)，使得对于所有与x^{*} 的距离小于\(\varepsilon\) 的\(x \in \Omega\)，即在\(x^{*}\) 的某个邻域 \(N_{\varepsilon}(x^{*}) = \{ x \in \Omega | \hspace{6pt} \Vert x - x^{*} \Vert < \varepsilon \}\)中，任意\(x \in N_{\varepsilon}(x^{*})\)，都有\(f(x) \geq f(x^{*})\)，则称点\(x^{*}\) 为非线性规划问题(5.4)的局部极小点。如果对于任意 \(x \in N_{\varepsilon} (x^{*})\)且\(x \neq x^{*}\)，都有\(f(x) > f(x^{*})\)，则称点\(x^{*}\) 为严格局部极小点。

• 严格局部极小点：若对任意 \(x \in N_{\varepsilon}(x^{*})\) 且 \(x \neq x^{*}\)，都有\(f(x) > f(x^{*})\)，那么点\(x^{*}\)为严格局部极小点。

• 全局极小点：【补充】

5.2.2 多元函数极值点的存在条件

• 可行方向：对于给定点 \(x \in \Omega\)， 向量\(p\)称为是在点 \(x\) 处的一个可行方向，如果存在 \(\overline{\alpha} > 0\)，使得任意\(0 \leq \alpha \leq \overline{\alpha}\)，有 \(x + \alpha p \in \Omega\)。
• 定理5.1: 设 f 是定义在集合 \(\Omega \in R^n\) 上的一阶连续可微函数，如果 \(x^*\) 是\(f\)在 \(\Omega\) 上的局部极小点，那么对 \(x^{*}\) 的任意可行方向 \(p \in R^{n}\)，有:

\[\nabla f(x^*)^{T}p \geq 0\]

其中

\[\nabla f(x^{*}) = \{ \dfrac{\partial f(x^{*})}{\partial x_1}, \dfrac{f(x^{*})}{\partial x_2}, ..., \dfrac{\partial f(x^{*})}{\partial x_n}\}\]

是函数\(f\)在点\(x^*\)处的梯度(Gradiant)，也就是一阶偏导数，梯度方向是函数f在点x的等值线的法线方向，沿着这个方向函数值增加最快。

• 对于无约束优化问题，\(\Omega = R^n\)的情形，显然所有方向\(p\)都应该是可行的，也就是 \(\nabla f(x^*)^T \geq 0\)，对于任意 \(p \in R^{n}\)都是成立的，所以 \(\nabla f(x^*) = 0\) 被称为无约束情形下极小点 \(x^{*}\) 的一阶必要条件。

• 定理5.2 无约束情形下的一阶必要条件：设\(f\)是定义在\(R^n\) 上的一阶可微函数，如果\(x^{*}\) 是\(f\)在\(R^n\)上的局部极小点，那么必有 \(\nabla f(x^*) = 0\)。

不是充分条件，满足上式的点被称为函数的驻点，可能是局部极小，也可能局部极大，也可能都不是。既不是局部极小也不是局部极大的驻点，称为鞍点。

要从驻点中分出那些是局部极小，还需要检验二阶导数的信息：

\[\nabla^{2}f(x^{*}) = 
    \begin{pmatrix}
     \dfrac{\partial^{2}f(x^*)}{\partial x^{2}_{1}} &  \dfrac{\partial^{2}f(x^*)}{\partial x_{1} \partial x_{2}}&\cdots & \dfrac{\partial^{2}f(x^*)}{\partial x_{1} \partial x_{n}} \\ 
      \vdots & \vdots &  & \vdots \\ 
      \dfrac{\partial^{2}f(x^*)}{\partial x_{n} \partial x_{1}} &  \dfrac{\partial^{2}f(x^*)}{\partial x_{n} \partial x_{2}}&\cdots & \dfrac{\partial^{2}f(x^*)}{\partial x^{2}_{n}}   
    \end{pmatrix}\]

• 上是\(f\)在\(x^{*}\)处的二阶偏导数，该矩阵被称为 Hessian 矩阵。

• 定理 5.3 二阶必要条件——无约束情形：设函数\(f\)在 \(R^{n}\) 上具有二阶连续偏导数，如果\(x^{*}\) 是\(f\)在\(R^{n}\)上的局部极小点，那么必然有：

  • \(\nabla f(x^* ) =0\)
  • 对任意\(p \in R^n， p^{T} \nabla^2 f(x^*) p \geq 0\)，也就是Hessian 矩阵半正定。
• 定理 5.4 二阶充分条件——无约束情形：设函数\(f\)在 \(R^{n}\) 上具有二阶连续偏导数，如果满足\(\nabla f(x^* ) =0\)，且对任意\(p \in R^n\)， \(p^{T} \nabla^2 f(x^*) p \geq 0\)，也就是Hessian 矩阵正定，那么\(x^{*}\) 是\(f\)在\(R^{n}\)上的严格局部极小点。

---

5.3 凸函数和凸规划

5.3.1 凸函数的定义

• 凸函数: 设\(f\)是定义在凸集 \(\Omega\) 上的函数，若对任意实数 \(0 \leq \alpha \leq 1\)，以及任意两点 \(x, y \in \Omega\)，有

\[f ( \alpha x + (1-\alpha) y) \leq \alpha f(x) + (1-\alpha) f(y)\]

• 则称 \(f\) 是凸集 \(\Omega\) 上的凸函数。

• 严格凸函数：设 \(f\) 是定义在凸集 \(\Omega\) 上的函数，若对任意实数 \(0 < \alpha < 1\) 以及任意两点 \(x, y \in \Omega\)，且 \(x \neq y\) 有：

\[f(\alpha x + (1-\alpha) y) < \alpha f(x) + (1-\alpha) f(y)\]

则称\(f\)是凸集 \(\Omega\) 上的严格凸函数。

5.3.2 凸函数的性质

• 性质5.1 ： 设\(f\)是定义在凸集 \(\Omega\) 上的凸函数，\(x_1, x_2,..,x_m\) 是 \(\Omega\) 中的\(m\)个点，数 \(\alpha_1, \alpha_2,..,\alpha_m \geq 0\)，且 \(\sum \limits^{m}_{i = 1} a_i = 1\)，则：

\[f(a_1 x_1 + a_2 x_2 + ,..., + a_m x_m) \leq a_1 f(x_1) + a_2 f(x_2) + ,..., +a_m f(x_m)\]

• 性质5.2 : 设\(f\)是定义在凸集 \(\Omega\) 上的凸函数，那么对于任意实数 \(\beta \geq 0\)，函数 \(\beta f(x)\)也是定义在 \(\Omega\) 上的凸函数。

• 性质5.3 : 设 \(f_1, f_2\) 是定义在凸集 \(\Omega\) 上的两个凸函数，那么\(f_1 + f_2\) 仍然是定义在 \(\Omega\) 上的凸函数。

• 性质5.4 : 设 \(f\)是定义在凸集 \(\Omega\) 上的凸函数，那么对任意实数 \(c\)，集合 \(\Gamma_c = \{ x | f(x) \leq c, x \in \Omega \}\) 是凸集 .

5.3.3 凸函数的判定条件

• 性质 5.5 设\(f\)是在开凸集 \(\Omega\) 上是可微函数，则\(f\)在 \(\Omega\) 上是凸函数的充分必要条件是对于任意 \(x_1, x_2 \in \Omega\)，有：

\(f(x_2) \geq f(x_1) + \nabla f(x_1)^{T}(x_2 - x_1)\)

如果上式是严格不等式，那么就是严格凸函数的充要条件。

• 性质 5.6 设\(f\)在开凸集 \(\Omega\) 上是二阶可微函数，那么\(f\)在 \(\Omega\) 上是凸函数的充要条件是对于任意 \(x \in \Omega\)， Hessian 矩阵 \(H(x) = \nabla^2 f(x)\) 是半正定的。如果对于任意 \(x \in \Omega\)，\(H(x)\) 是正定的，那么\(f\)在 \(\Omega\)上是严格凸函数。

5.3.4 凸规划

• 考虑下面的数学规划:

\[\mathop{\min} \limits^{}_{x \in \Omega} \hspace{4pt} f(x)\]

若其中\(f(x)\) 是凸函数，\(\Omega\) 是凸集，那么上式是 凸规划。

由于线性函数既是凸函数也是凹函数，因此线性规划属于凸规划。

• 性质 5.7 凸规划的最优解具有如下性质
• 如果最优解存在，那么最优解为凸集；
• 任何局部最优解也就是全剧最优解；
• 如果目标函数为严格凸函数，且最优解存在，那么最优解唯一。

5.4 下降迭代算法

• 对于一般\(n\)元函数\(f(x)\)，一阶必要条件等于0往往很难求出其偏导数，难以应用，因此多采用下降迭代算法：

• 从初始估计点\(x_0\)出发，按照一定规则，找到一个比\(x_0\) 更好的点\(x_1\)，再从\(x_1\) 出发，找到一个比\(x_1\) 更好的点\(x_2\)，如此继续，得到一个解的点序列\(\{ x_k\}\)。若该点序列有一个极限点 \(x^{*}\)， 也就是:

\[\mathop{\lim} \limits_{k \to \infty} \Vert x_k - x^* \Vert = 0\]

就称该点列收敛于\(x^{*}\)。

步骤如下：

1. 选取初始点\(x_0\)， 令 \(k:=0\);
2. 确定搜索方向，如果已经得出某一迭代点\(x_k\)，且 \(x_k\) 是极小点，那么就要根据一定的规则，从\(x_k\) 点出发确定一个搜索方向\(d_k\)，沿着该方向能找到是的目标函数值下降的可行点。
3. 确定步长，沿着方向\(d_k\) 前进一个步长，得到新点\(x_{k + 1}\)，通过选择合适的步长 \(\alpha_k\)，使得下一个迭代点

\[x_{k+1} = x_k + \alpha_k d_k\]

满足:

\[f(x_{k+1}) = f(x_k +  \alpha_k d_k) < f(x_k)\]

1. 最优性检验，检验新得到的点是否是极小点或者达到近似极小点的要求，如果满足，就迭代停止，否则令 \(k := k + 1\)，返回步骤二迭代。

2. 迭代终止准则：由于真正的极值点不知道，所以在下降迭代算法中根据两次迭代得到的计算结果来判断是否达到要求，常用的迭代终止准则：

   • 绝对误差
   • 相对误差
   • 目标函数梯度的模

5.5 一维搜索

• 一维搜索是单变量函数在某个区间上求极值点的问题

5.5.1 斐波那契法和牛顿法

5.5.2 牛顿法

如果单变量函数在\(x^*\) 取到局部极值，并且在\(x^*\) 可微，那么函数在该点的一阶导数为0。为了求解\(f^{'}(x) = 0\)，需要用到迭代方法：牛顿法（切线法），在一个迭代点附近用切线代替曲线，用切线方程的零点作为新的迭代点，逐步逼近最优。

\[x_{k + 1} = x_k + \dfrac{f^{'}(x_k)}{f^{''}(x_k)}\]

上式即为牛顿迭代公式。

Tip

牛顿法需要计算目标函数二阶导数，如果迭代序列收敛，则速度较快，但是其收敛性依赖于初始值\(x_0\)的选取，如果偏离真值较远，那么牛顿法可能发散。

5.5.3 函数逼近法

5.6 无约束极值问题的求解算法

无约束极值问题表示为:

\[\mathop{\min} \limits_{x \in R^n} f(x) \tag{5.24}\]

5.6.1 梯度法

假设5.24中目标函数\(f\)在\(R^n\)上一阶连续可微，存在极小点\(x^{*}\)，用\(x_k\) 表示极小点的第\(k\)次近似，为了找到\(k+1\)次的迭代点，需要在\(x_k\) 沿着方向\(d_k\)做射线

\[x = x_k + \alpha d_k, \alpha \geq 0\]

满足 \(\nabla f(x_k)^{T} d_k < 0\)的方向称为下降方向。考虑：\(\Vert \nabla f(x_k) \Vert \cdot \Vert d_k \Vert \cdot \cos \theta\)，当 \(\theta = \pi\) 时，上述值最小，此时搜索方向为负梯度方向。

选定负梯度方向后，还需要确定步长 \(\alpha_k\)。可以选择：

1. 试算：任取一个值，检验是否满足 \(f(x_k + \alpha_k d_k) < f(x_k)\)，如果不满足就减小 \(\alpha_k\)；
2. 沿着搜索方向进行一维搜索，也就是求使得 \(f(x)\) 最小的 \(\alpha_k\)：

\[\mathop{\min} \limits_{\alpha_k \geq 0} f(x_k + \alpha_k d_k)\]

方向 \(d_{k + 1}\) 和 \(d_{k}\) 正交，其迭代过程实际上是沿着“之”字形前进的。

• 总结如下：

  1. 给定初始点\(x_0\)和误差容限 \(\varepsilon > 0\);
  2. 计算负梯度方向\(d_k = - \nabla f(x_k)\)
  3. 检验是否满足收敛性准则 \(\Vert \nabla f(x_k) \Vert < \varepsilon\)，如果满足就停止迭代，否则进入4；
  4. 进行一维搜索，求解单变量极值问题，得到步长 \(\alpha_k\)；
  5. 令\(x_{k + 1} = x_k + \alpha_k d_k，k:= k + 1\)，转化到步骤二；

• 在所有下降方向中，某点负梯度方向是函数下降最快的方向，因此被称为最速下降方向，梯度法也被称为“最速下降法”。在实际计算中，常常在前期使用梯度法，在接近极小点的时候再改用其他收敛方法。

• 梯度Gradiant： 上升最快的方向：nabla算子：各个方向求偏导组成向量；函数在梯度这个方向的方向导数是最大的，换句话说，一个函数在各个方向都有方向导数，其中梯度这个方向的导数为最大； 梯度方向总是垂直于等值面的；

5.6.2 牛顿法

假定函数\(f(x)\)有二阶连续偏导数，在给定点\(x_k\)附近取 \(f(x)\) 的二阶Taylor多项式逼近。

• 步骤
  1. 给定初始点\(x_0\)和误差容限 \(\varepsilon > 0\);
  2. 检验是否满足收敛性准则 \(\Vert \nabla f(x_k) \Vert < \varepsilon\)，如果满足条件就停止迭代，否则进入步骤3；
  3. 计算牛顿方向： \(d_k = - [ \nabla^{2} f(x_k) ]^{-1} \nabla f(x_k)\).
  4. 令\(x_{k + 1} = x_k + d_k\)，令\(k := k + 1\)，转入步骤2；

5.6.3 拟牛顿法

5.7 约束极值问题的最优性条件

• 有效约束
• 有效约束下标记集
• 正则点：对于约束优化问题(5.4)，如果在可行点\(\overline{x}\)处，各个有效约束的梯度向量，也就是 \(\{ \nabla g_i ( \overline{x}), i \in A(\overline{x}) \}\) 线性无关，就称\(\overline{x}\)是约束条件的一个正则点。

5.7.2 可行方向和下降方向

• 考虑非线性规划问题：

\[\mathop{\min} f(x) \\  s.t. \hspace{4pt}  g_i(x) \geq 0, i = 1,2,...,l\]

• 可行方向：如果任取一个\(x_0\)，对方向\(d \in R^n\)，存在 \(\alpha_0 > 0\)，当 \(0 \leq \alpha \alpha_0\)，下式成立：\(g_i(x_0 + \alpha d) \geq 0, i = 1,2,...,l\)，则称\(d\)为 \(x_0\) 的可行方向。

如果 \(x_0\) 的某一方向既是该点的可行方向，又是该点的下降方向，那么称它是这个点的可行下降方向，有：

\[\left\{ \begin{aligned}  \nabla f(x_0)^{T} d  & < 0 \\ \nabla g_i(x_0)^T d & > 0, i \in A(x_0) \end{aligned} \right.\]

5.7.3 库恩-塔克条件（KKT条件）

K-T 条件是确定某点为局部最优解的一阶必要条件，只要是最优点、同时也是正则点就必须满足这个条件。但是一般来说，它不是充分条件，满足这个条件的点不一定是最优点。不过对于凸规划来说，KT条件既是必要条件也是充分条件。

对于此类问题：

\[\mathop{\min} f(x) \\ s.t. \hspace{4pt} g_i(x) \geq 0, \hspace{4pt} i = 1,2,...,l\]

有如下定理：

• 定理 5.5 设 \(x^*\) 是如上约束优化问题的局部极小点，\(f(x)\) 和 \(g_i(x)\) 在点 \(x^*\) 处有一阶连续偏导，并且\(x^*\) 是约束条件的一个正则点，则存在向量 \(\mu = (u^{*}_{1}, u^{*}_{2}, ..., u^{*}_{l} )^{T}\)，使得下述条件成立：

\[\left\{ \begin{aligned} \nabla f(x^{*}) - \sum \limits^{l}_{i = 1} \mu^{*}_{i} \nabla g_i(x^{*}) = 0 \\ u^{*}_{i}g_i(x^{*}) = 0, \hspace{4pt} i = 1,2,...,l  \\ u^{*}_{i} \geq 0, \hspace{4pt} i = 1,2,...,l \end{aligned} \right. \tag{5.39}\]

上述就是K-T条件。

如果同时含有等式和不等式约束的情形，如：

\[ \mathop{\min} f(x) \\ s.t. \left\{ \begin{aligned} \hspace{4pt} g_i(x) \geq 0, \hspace{4pt}i = 1,2,...,l  \\  h_j(x) = 0, \hspace{4pt} j = 1,2,...,m  \end{aligned} \right.\]

有定理：

• 定理 5.6 设 \(x^{*}\) 是约束优化问题的局部极小点，\(f(x),g_i(x)\) 和 \(h_j(x)\)在点\(x^*\) 处有一阶连续偏导数，并且\(x^{*}\) 是约束条件的一个正则点，则存在向量 \(\mu = (u^{*}_{1}, u^{*}_{2}, ..., u^{*}_{l} )^{T}\)，使得下述条件成立：

\[\left\{ \begin{aligned} \nabla f(x^{*}) - \sum \limits^{l}_{i = 1} \mu^{*}_{i} \nabla g_i(x^{*}) - \sum \limits^{m}_{j = 1} \lambda^{*}_j \nabla h_j(x^*) = 0 \\ u^{*}_{i}g_i(x^{*}) = 0, \hspace{4pt} i = 1,2,...,l  \\ u^{*}_{i} \geq 0, \hspace{4pt} i = 1,2,...,l \end{aligned} \right. \tag{5.42}\]

• KT条件是确定某点为最优点的必要条件，只要是最优点，且此处起作用约束的梯度线性无关，就会满足这个条件。但是一般来说，它不是充分条件。特别地，对于凸规划问题，KT条件既是最优点的必要条件，同时也是充分条件。

KKT条件（Karush-Kuhn-Tucker conditions）是最优性理论中的一个概念。它是描述有约束最优性问题中最优解的一组充分必要条件。KKT条件是线性规划和非线性规划的一般形式，常用于数学优化、计算机科学、经济学等领域。

KKT条件的意义在于，它可以确保满足约束条件的同时找到最优解。在实际应用中，KKT条件可以用于验证最优解的正确性，也可以用于求解最优性问题的算法。