Chapter05_非线性规划

1. 试述非线性规划数学模型的一般形式及其同线性规划的主要区别
   1. 一般形式$$\begin{cases}\min f(\boldsymbol{X})\\h_{i}(\boldsymbol{X})=0,&i=1,2\cdots,m\\g_{j}(\boldsymbol{X})\ge0,&j=1,2\cdots,l\end{cases}$$
   2. 主要区别 最优解的位置：若线性规划问题有最优解，则其最优解一定在其可行域的边界上达到；而非线性规划问题的最优解则可能在其可行域中任意一点达到
2. 分别说明在什么条件下，称 $\boldsymbol{X}^*$ 为 $f(\boldsymbol{X})$ 在 $\mathbb{R}$ 上的
   1. 局部最小点 设 $f(\boldsymbol{X})$ 为定义在 $n$ 维欧式几何 $\mathbb{E}^{n}$ 的在某一区域 $\mathbb{R}$ 上的 $n$ 元实函数，其中 $\boldsymbol{X}=(x_1,x_2,\cdots,x_n)^\intercal$；对于 $\boldsymbol{X}^*\in\mathbb{R}$，若存在 $\epsilon>0$，使得所有与 $\boldsymbol{X}^*$ 的距离小于 $\epsilon$ 的 $\boldsymbol{X}\in\mathbb{R}$ （即 $\boldsymbol{X}\in\mathbb{R}$ 且 $\Vert \boldsymbol{X}-\boldsymbol{X}^*\Vert <\epsilon$）均满足不等式 $f(\boldsymbol{X}^*)\le f(\boldsymbol{X})$ 则称 $\boldsymbol{X}^*$ 为 $f(\boldsymbol{X})$ 在 $\mathbb{R}$ 上的局部最小点，$f(\boldsymbol{X}^*)$ 为局部最小值
   2. 严格局部最小点 设 $f(\boldsymbol{X})$ 为定义在 $n$ 维欧式几何 $\mathbb{E}^{n}$ 的在某一区域 $\mathbb{R}$ 上的 $n$ 元实函数，其中 $\boldsymbol{X}=(x_1,x_2,\cdots,x_n)^\intercal$；对于 $\boldsymbol{X}^*\in\mathbb{R}$，若存在 $\epsilon>0$，使得所有与 $\boldsymbol{X}^*$ 的距离小于 $\epsilon$ 的 $\boldsymbol{X}\in\mathbb{R}$ （即 $\boldsymbol{X}\in\mathbb{R}$ 且 $\Vert \boldsymbol{X}-\boldsymbol{X}^*\Vert <\epsilon$）均满足不等式 $f(\boldsymbol{X}^*) < f(\boldsymbol{X})$ 则称 $\boldsymbol{X}^*$ 为 $f(\boldsymbol{X})$ 在 $\mathbb{R}$ 上的严格局部最小点，$f(\boldsymbol{X}^*)$ 为严格局部最小值
   3. 全局最小点 设 $f(\boldsymbol{X})$ 为定义在 $n$ 维欧式几何 $\mathbb{E}^{n}$ 的在某一区域 $\mathbb{R}$ 上的 $n$ 元实函数，其中 $\boldsymbol{X}=(x_1,x_2,\cdots,x_n)^\intercal$；对于 $\boldsymbol{X}^*\in\mathbb{R},\forall\ \boldsymbol{X}\in\mathbb{R}$，均有 $f(\boldsymbol{X}^*)\le f(\boldsymbol{X})$，则称 $\boldsymbol{X^*}$ 为全局最小点，$f(\boldsymbol{X^*})$ 为全局最小值
   4. 严格全局最小点 设 $f(\boldsymbol{X})$ 为定义在 $n$ 维欧式几何 $\mathbb{E}^{n}$ 的在某一区域 $\mathbb{R}$ 上的 $n$ 元实函数，其中 $\boldsymbol{X}=(x_1,x_2,\cdots,x_n)^\intercal$；对于 $\boldsymbol{X}^*\in\mathbb{R},\forall\ \boldsymbol{X}\in\mathbb{R}$，均有 $f(\boldsymbol{X}^*) < f(\boldsymbol{X})$，则称 $\boldsymbol{X^*}$ 为严格全局最小点，$f(\boldsymbol{X^*})$ 为严格全局最小值
3. 分别写出下属概念的数学表达式
   1. 函数 $f(\boldsymbol{X})$ 在 $\boldsymbol{X}^*$ 处的梯度 $$\nabla f(\boldsymbol{X}^*)= \begin{pmatrix}\frac{\partial f(\boldsymbol{X}^*)}{\partial x_{1}} & \frac{\partial f(\boldsymbol{X}^*)}{\partial x_{2}} & \cdots & \frac{\partial f(\boldsymbol{X}^*)}{\partial x_{n}}\end{pmatrix}^{\intercal}$$
   2. $f(\boldsymbol{X})$ 在 $\boldsymbol{X}^*$ 处的海塞 (Hesse) 矩阵$$\begin{pmatrix} \frac{\partial f(\boldsymbol{X})}{\partial x_1^2 } & \frac{\partial f(\boldsymbol{X})}{\partial x_1 \partial x_2} & \cdots & \frac{\partial f(\boldsymbol{X})}{\partial x_1 \partial x_n} \\ \frac{\partial f(\boldsymbol{X})}{\partial x_2 \partial x_1} & \frac{\partial f(\boldsymbol{X})}{\partial x_2^2 } & \cdots & \frac{\partial f(\boldsymbol{X})}{\partial x_2 \partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial f(\boldsymbol{X})}{\partial x_n \partial x_1} & \frac{\partial f(\boldsymbol{X})}{\partial x_n \partial x_2} & \cdots & \frac{\partial f(\boldsymbol{X})}{\partial x_n^2 } \\ \end{pmatrix}$$
   3. 二次型$$f(\boldsymbol{X}) = \boldsymbol{X}^\intercal\boldsymbol{A}\boldsymbol{X}$$
   4. 正定、半正定、负定、半负定二次型的充要条件
      1. 正定 $\forall\ \boldsymbol{X}\in \mathbb{R},\ f(\boldsymbol{X}) = \boldsymbol{X}^{\intercal}\boldsymbol{AX} > 0$
      2. 半正定 $\forall\ \boldsymbol{X}\in \mathbb{R},\ f(\boldsymbol{X}) = \boldsymbol{X}^{\intercal}\boldsymbol{AX} \ge 0$
      3. 否定 $\forall\ \boldsymbol{X}\in \mathbb{R},\ f(\boldsymbol{X}) = \boldsymbol{X}^{\intercal}\boldsymbol{AX} < 0$
      4. 半负定 $\forall\ \boldsymbol{X}\in \mathbb{R},\ f(\boldsymbol{X}) = \boldsymbol{X}^{\intercal}\boldsymbol{AX} \le 0$
4. 试述凸函数、严格凸函数、凹函数和严格凹函数的定义；凸函数的性质及判断一个函数是否为凸函数的一阶及二阶条件
   1. 定义
      1. 凸函数和严格凸函数 设 $f(\boldsymbol{X})$ 为定义在 $n$ 维欧式几何 $\mathbb{E}^{n}$ 中某个凸集 $\mathbb{R}$ 上的函数，若 $\forall\ \alpha \in(0,1)$，都有及 $\mathbb{R}$ 上任意两点 $\boldsymbol{X}^{(1)}$ 和 $\boldsymbol{X}^{(2)}$，恒有$$f(\alpha\boldsymbol{X}^{(1)} + (1-\alpha)\boldsymbol{X}^{(2)}) \le \alpha f(\boldsymbol{X}^{(1)})+ (1-\alpha) f(\boldsymbol{X}^{(2)})$$则称 $f(\boldsymbol{X})$ 为定义在 $\mathbb{R}$ 上的凸函数；若恒有$$f(\alpha\boldsymbol{X}^{(1)} + (1-\alpha)\boldsymbol{X}^{(2)}) < \alpha f(\boldsymbol{X}^{(1)})+ (1-\alpha) f(\boldsymbol{X}^{(2)})$$则称 $f(\boldsymbol{X})$ 为定义在 $\mathbb{R}$ 上的严格凸函数
      2. 凹函数和严格凹函数 设 $f(\boldsymbol{X})$ 为定义在 $n$ 维欧式几何 $\mathbb{E}^{n}$ 中某个凸集 $\mathbb{R}$ 上的函数，若 $\forall\ \alpha \in(0,1)$，都有及 $\mathbb{R}$ 上任意两点 $\boldsymbol{X}^{(1)}$ 和 $\boldsymbol{X}^{(2)}$，恒有$$f(\alpha\boldsymbol{X}^{(1)} + (1-\alpha)\boldsymbol{X}^{(2)}) \ge \alpha f(\boldsymbol{X}^{(1)})+ (1-\alpha) f(\boldsymbol{X}^{(2)})$$则称 $f(\boldsymbol{X})$ 为定义在 $\mathbb{R}$ 上的凹函数；若恒有$$f(\alpha\boldsymbol{X}^{(1)} + (1-\alpha)\boldsymbol{X}^{(2)}) > \alpha f(\boldsymbol{X}^{(1)})+ (1-\alpha) f(\boldsymbol{X}^{(2)})$$则称 $f(\boldsymbol{X})$ 为定义在 $\mathbb{R}$ 上的严格凹函数
   2. 性质
      1. 性质一 若 $f(\boldsymbol{X})$ 为定义在凸集 $\mathbb{R}$ 上的凸函数，则对任意实数 $\beta \ge 0$，函数 $\beta f(\boldsymbol{X})$ 也是定义在 $\mathbb{R}$ 上的凸函数
      2. 性质二 设 $f_1(\boldsymbol{X})$ 和 $f_2(\boldsymbol{X})$ 均为定义在凸集 $\mathbb{R}$ 上的两个凸函数，则其和 $f(\boldsymbol{X})=f_1(\boldsymbol{X})+f_2(\boldsymbol{X})$ 也为定义在 $\mathbb{R}$ 上的凸函数；
         • 推论 有限个凸函数的非负线性组合$$\sum_{i=1}^{m}\beta_{i}f_{i}(\boldsymbol{X});\quad\beta_{i}\ge0,(i=1,2,\cdots,m)$$仍为凸函数
      3. 性质三 设 $f(\boldsymbol{X})$ 为定义在凸集 $\mathbb{R}$ 上的凸函数，则对任意实数 $\beta$，集合$$S_{\beta} = \{\boldsymbol{X}\vert \boldsymbol{X}\in\mathbb{R},f(\boldsymbol{X})\le \beta\}$$为凸集
   3. 条件
      1. 一阶条件：设 $\mathbb{R}$ 为 $n$ 维欧式空间 $\mathbb{E}^n$ 上的开凸集，$f(\boldsymbol{X})$ 在$\mathbb{R}$ 上具有一阶连续偏导数，则 $f(\boldsymbol{X})$ 为 $\mathbb{R}$ 上的凸函数的充要条件是，对任意两个不同点 $\boldsymbol{X}^{(1)},\boldsymbol{X}^{(2)}\in\mathbb{R}$，恒有$$f(\boldsymbol{X}^{(2)})\ge f(\boldsymbol{X}^{(1)}) + \nabla f(\boldsymbol{X}^{(1)})^{\intercal}(\boldsymbol{X}^{(2)}-\boldsymbol{X}^{(1)})$$
      2. 二阶条件 设 $\mathbb{R}$ 为 $n$ 维欧式空间 $\mathbb{E}^n$ 上的开凸集，$f(\boldsymbol{X})$ 在$\mathbb{R}$ 上具有二阶连续偏导数，则 $f(\boldsymbol{X})$ 为 $\mathbb{R}$ 上的凸函数的充要条件是：$f(\boldsymbol{X})$ 的海塞矩阵 $\boldsymbol{H}(\boldsymbol{X})$ 在 $\mathbb{R}$ 上处处半正定
5. 何为凸规划?
   1. 考虑非线性规划$$\begin{cases}\displaystyle\min_{\boldsymbol{X}\in\mathbb{R}} f(\boldsymbol{X})\\\mathbb{R} = \{\boldsymbol{X}\vert g_i(\boldsymbol{X})\ge 0, j=1,2,\cdots,l\}\end{cases}$$若
      1. $f(\boldsymbol{X})$ 为凸函数
      2. $g_{j}(\boldsymbol{X})\quad(j=1,2,\cdots,l)$ 为凹函数 （或 $-g_{j}(\boldsymbol{X})$ 为凸函数） ，这样的非线性规划称为凸规划
6. 为什么求解有约束的极值问题相较于求解无约束的极值问题要困难得多？对具体约束的极值问题，为简化其优化工作，通常可采取哪些方法？
   1. 原因 对于有约束的极值问题，相较于无约束的极值问题，除了要使得每次迭代都有所下降外，还要注意解的可行性的问题，因此，要困难得多
   2. 简化方法
      1. 将约束问题化为无约束问题
      2. 将非线性问题化为线性规划问题
7. 试解释以下概念
   1. 不起作用的约束，起作用的约束 设 $\boldsymbol{X}^{(0)}$ 为非线性规划的一个可行解，其满足所有约束。先考虑某一不等式约束 $g_j(\boldsymbol{X})\ge 0$，$\boldsymbol{X}^{(0)}$ 满足其有两种可能：
      1. 其一，$g_j(\boldsymbol{X}^{(0)})>0$，这时，点$\boldsymbol{X}^{(0)}$ 不是处于这一约束条件形成的可行域边界上，因而这一约束对$\boldsymbol{X}^{(0)}$点的微小摄动不起限制作用，因此，称此约束为$\boldsymbol{X}^{(0)}$点的不起作用约束（无效约束）
      2. 其二，$g_j(\boldsymbol{X}^{(0)})=0$，这时$\boldsymbol{X}^{(0)}$点处于该约束条件形成的可行域边界上，它对$\boldsymbol{X}^{(0)}$的摄动起到某种限制作用，故称此约束为$\boldsymbol{X}^{(0)}$的起作用约束（有效约束）
   2. 可行方向 假定$\boldsymbol{X}^{(0)}$是非线性规划的一个可行点，现考虑此点的某一方向$\boldsymbol{D}$，若存在实数$\lambda_{0}>0$，使得对于任意$\lambda\in[0,\lambda_0]$均有$$\boldsymbol{X}^{(0)}+\lambda\boldsymbol{D}\in\mathbb{R}$$则称方向$\boldsymbol{D}$为$\boldsymbol{X}^{(0)}$点的一个可行方向
   3. 下降方向 假定$\boldsymbol{X}^{(0)}$是非线性规划的一个可行点，对该点的任一方向$\boldsymbol{D}$ 来说，若存在实数 $\lambda_{0}'>0$，对任意$\lambda\in[0,\lambda_0']$，均有$$f(\boldsymbol{X}^{(0)}+\lambda\boldsymbol{D}) < f(\boldsymbol{X}^{(0)})$$则称 $\boldsymbol{D}$ 为 $\boldsymbol{X}^{(0)}$ 的一个下降方向
   4. 可行下降方向 若方向 $\boldsymbol{D}$ 既是 $\boldsymbol{X}^{(0)}$ 的可行方向，又是这个点的下降方向，则称其是该点的可行下降方向
8. 什么是库恩－塔克 Kuhn-Tucker 条件和库恩－塔克点？为什么满足库恩－塔克条件是点 $\boldsymbol{X}^*$ 成为最优点的必要条件？
   1. 定义
      1. Kuhn-Tucker 条件：设 $\boldsymbol{X}^{*}$ 是非线性规划的极小点，而且在 $\boldsymbol{X}^{*}$ 点的各起作用的约束的梯度线性无关，则存在向量 $\boldsymbol{\Gamma}^{*}=(\gamma_{1}^*,\gamma_{2}^*,\cdots,\gamma_{l}^*)^\intercal$，使得下述条件成立$$\begin{cases}\displaystyle \nabla f(\boldsymbol{X}^{*}) － \sum_{j=1}^{l}\gamma_{j}^{*}\nabla g_{j}(\boldsymbol{X}^{*}) = 0 \\ \gamma_{j}^*g_{j}(\boldsymbol{X}^{*}) = 0, &j=1,2,\cdots,l\\\gamma^{*}_j\ge0,& j=1,2,\cdots,l\end{cases}$$此式常称为库恩-塔克条件，满足此条件的点称为库恩塔克点
   2. 为什么是必要条件？ 设 $\boldsymbol{X}^{*}$ 位于某个约束条件形成的可行域边界上 $g_j(\boldsymbol{X}^{*})=0$；若 $\boldsymbol{X}^{*}$ 为极小点，则 $g_j(\boldsymbol{X}^{*})$ 必与 $-f(\boldsymbol{X}^{*})$ 在一条直线上且方向相反；否则该点就一定存在下降可行方向，因此，存在实数 $\gamma_j\ge 0$，使得$$\nabla f(\boldsymbol{X}^{*}) - \gamma_{j}\nabla g_j(\boldsymbol{X}^{*}) = 0$$以此类推可得到$$\nabla f(\boldsymbol{X}^{*}) － \sum_{j=1}^{l}\gamma_{j}^{}\nabla g_{j}(\boldsymbol{X}^{*}) = 0$$因此，只有满足库恩塔克条件，该解才有可能为极小点，因此为极小点的必要条件
9. 写出二次规划数学模型的一般表达式，又在满足什么条件时二次规划属于凸规划？
   1. 一般表达形式$$\begin{cases}\displaystyle \min f(\boldsymbol{X}) = \sum_{j=1}^{n}c_jx_j + \frac{1}{2}\sum_{j=1}^{n}\sum_{k=1}^n c_{jk}x_jx_k\\\begin{array}{ll}&c_{jk} = c_{kj} &k=1,2\cdots,n\\&\displaystyle\sum_{j=1}^na_{ij}x_j + b_i \ge 0,&i=1,2,\cdots,m\\&x_j\ge0,\quad &j=1,2,\cdots,n\end{array}\end{cases}$$
   2. 当二次型 $f(\boldsymbol{X})$ 正定（或半正定）时，该函数为严格凸函数（或凸函数）；因为，二次规划的可行域为凸集，因此，其为凸规划
10. 如何将一个二次规划问题转化为线性规划问题？试写出转化后的线性规划问题的数学模型，并说明模型中各个符号的意义。
    1. 转化
       1. 根据库恩塔克条件$(1)$，并用 $y$ 代替 $\gamma$ 可得$$-\sum_{k=1}^{n}c_{jk}x_{k} + \sum_{i=1}^{m}a_{ij}y_{n+i} + y_{j}=c_{j},\quad j =1,2,\cdots,n$$
       2. 对于约束可加入，松弛变量，使其成为等式$$\sum_{j=1}^{n}a_{ij}x_{j} + b_{i} - x_{n+i} = 0,\quad i = 1,2,\cdots,m$$
       3. 再将库恩塔克条件第二个条件应用于如上问题，得到$$x_jy_j=0,\quad j=1,2,\cdots,n+m$$
       4. 由于$c_j$ 有正有负，因此，引入人工变量$z_{j}$，使得$$\sum_{i=1}^{m}a_{ij}y_{n+i} + y_{j} -\sum_{k=1}^{n}c_{jk}x_{k} +\text{sgn}(c_{j})z_{j}= c_{j},\quad j =1,2,\cdots,n$$
       5. 由此变为如下规划问题$$\begin{split}&\min \varphi(\boldsymbol{Z})= \sum_{i=1}^n z_{j}\\&\text{s.t}\begin{cases}\displaystyle\sum_{i=1}^{m}a_{ij}y_{n+i} + y_{j} -\sum_{k=1}^{n}c_{jk}x_{k} +\text{sgn}(c_{j})z_{j}= c_{j},& j =1,2,\cdots,n\\\displaystyle \sum_{j=1}^{n}a_{ij}x_{j} + b_{i} - x_{n+i} = 0,&i=1,2,\cdots,m\\x_{j}\ge 0,y_{j}\ge 0,&j=1,2,\cdots,n+m\\z_{j}\ge 0,&j=1,2,\cdots,n\end{cases}\end{split}$$