线性规划max

凸集合：$\alpha x+(1-\alpha)y∈S$

凸函数：$f(\alpha x+(1-\alpha)y)≤\alpha f(x)+(1-\alpha)f(y)$

标准型：一般都是max，使用单纯形和大M都化成max

image-20240412012644131

基本解：对于系数矩阵A,找出所有的子矩阵B（比如A的第一列&第三列就可以组成一个子矩阵，子矩阵的size等于未知数个数n），然后基本解的备选就是$B^{-1}b$（基本解的组成就是$x_1$&$x_3$对应结果的取值，其他的都是0），然后要求基本解所有的元素都是$≥0$

单纯形：

image-20240412114442384

什么时候直接单纯形不可以：（$x_5$必须是0）

image-20240412013059554

大M法：$Max:z=4x_1+2x_2+8x_3-Mx_5$

两阶段法：第一步$Max:z=-x_5$，保留表格的数据之后，第二步$Max:z=4x_1+2x_2+8x_3$

写在非线性规划前面

什么是非线性规划问题：求解目标函数或约束条件中包含一个或几个非线性函数的最优化问题的方法。

如何理解梯度在非线性规划当中的重要性：

梯度/导数的计算：

非线性规划的共同思路：

而面对这个问题的求解，就是“线性搜索过程/一维搜索过程”

一些在正式学习各种算法之前，你应该知道的概念：

  • 共轭函数：

非线性规划问题之无约束优化

一维搜索min：步长的确定

一维搜索方法分为：

  • 区间收缩法：找出包含极小点的搜索区间，并且通过不同的方式去不断的缩小搜索区间，直至区间小到精度范围之内，那么$\frac{1}{2}(a_n+b_n)$即为极小点$\lambda^*$的近似值，每一步迭代是区间

  • 函数逼近法：对目标函数进行近似替换，每一步迭代的就是$x^k$

单谷函数相关知识：

  • 黄金分割法

    对于任何一个区间$[a_0,b_0]$当中，两个试点$x_1,x_1’$的取值，由黄金分割法规定如下：

    当我们的最后考虑的区间，相比于最初区间足够小的时候，我们终止搜索：
    $$
    \frac{b_k-a_k}{b_0-a_0}<\delta
    $$

  • 牛顿法 ：使用泰勒公式展开来代替目标函数

  • 使用加步探索法（进退法）来探索：黄金分割法和牛顿法所需的包含极小点的初始探索区间

    加步探索法的具体步骤（理解即可）：

    举例：
    $$
    x_1=0\quad x_2=1\quad x_3=2\quad x_4=3
    $$

  • 抛物线法/插值法：

    怎么记上面的蓝色公式：$f(x_1)$：是$x_2$和$x_3$相减，是紧跟在$x_1$后面的$x_2$减别人

无约束优化min：搜索方向的确定

考虑的问题：$min f(x),x∈R^n$

常见的无约束优化算法的列举：

  • 变量轮换法：

    本质上来讲，就是把多变量的优化问题转化为一系列单变量函数的优化问题。基本思路是：认为有利的搜索方向是各个坐标轴的方向，因此它轮流按照各个坐标轴的方向搜索最优点

    也就是说，变量轮换法规定搜索方向就是各个坐标轴方向

    举例：

  • 最速下降法/梯度法：

    也就是说，最速下降法规定的搜索方向是梯度方向的负数/负梯度

    以下举例：

  • 牛顿法（同一维搜索的牛顿法）

    牛顿法规定搜索方向和步长分别是：$p=-\frac{f’(x)}{f’’(x)}\quad \lambda=1$

  • 修正牛顿法

非线性规划问题之有约束优化min（重点）

考虑问题：

一些必须掌握的知识：

即对于约束条件$g_i(x)≥0$来说，其在最优点$\overline x$处约束是0，那么就是起作用的约束

下面这个是很重要的结论：

==K-T条件：是局部最优解的一阶必要条件，对于凸优化来说，是充要条件！==

首先介绍只含有不等式约束的K-T条件：

如果$-\nabla f(x^*)$和$\nabla g_1(x^*)$不是共线且方向相反的话，在$x^*$这一点一定存在可行下降方向，这与定理2矛盾了：

同样使用反证法，可以证明上述结论。

==这就是只含有不等式约束下的K-T条件！需要特别记住！！！==

（要求$x^$是一个正则点）*
$$
\begin {cases}
\nabla f(x^*)-\sum_{i=1}^{m}\gamma_i\nabla g_i(x^*)=0\ \

\gamma_ig_i(x^*)=0,i=1,2,..,m\ \

\gamma_i\geq0,i=1,2,…,m
\end {cases}
$$
下面考虑含有等式约束和不等式约束的K-T条件：（把等式约束转成不等式约束）

对K-T条件应用的举例：

接下来要讨论两个约束是否是起作用的约束（也就是讨论$\gamma_1$和$\gamma_2$是否为0）：

其中，正则点的定义是：

如果只是讨论某一点是否为KT点，会更加简单：

可行方向法：使用线性规划来确定搜索方向

情况1：约束为线性函数的非线性规划问题

又有下面的结论（需要记住）：

总结可行方向法的步骤：

举例：

==注意：上图当中的 $\leq$ 还是 $\geq$ ，取决于原问题当中是哪个符号==

情况2：约束为非线性函数的非线性规划问题：

、

总结可行方向法的步骤：