最优化设计了以下方面：

  • 最优化方法及其应用（含计算机模拟）
  • 最优化模拟、最优化建模案例、最优化方法、
  • 典型算法（穷举法、贪心、爆搜、蒙特卡罗法、模拟退火法、粒子群算法、蚁群算法）、随机系统模拟

数模一般使用 MATLAB 进行编程，MATLAB 自带的函数可在 MATLAB 函数 中查看。

如何学习？

  1. 听课、了解、练习

  2. 借阅书籍 1：最优化方法（线性规划——单纯形，非线性规划——一维方法、无约束、有约束）、运筹学（线性规划、非线性规划、图论等）、随机系统模拟/离散系统仿真/系统仿真/系统模拟/计算机模拟

  3. 借阅书籍 2：数学模型、建模案例、建模优秀论文集

需要欣赏：

  • 写法、风格、文法
  • 论文框架：理解模型的思想，体会模型的建立过程、步骤

三个人都要对论文优秀论文有研究。

  1. 了解一些算法（如上的典型算法：穷举法等），变成的同学要熟悉，体现我们的工作量

经典算法

比较简单的就一笔带过。

  • 直接搜索法：用两个变量存储 f(x) 最小值和对应的 x 取值，并初始化最小值为无限大 inf。规定上下界和步长，枚举所有 x 值，如果 x 在范围内且 f(x) 值小于目前的最小值，则更新 f(x) 最小值及对应 x 取值。
  • 蒙特卡罗法：与上述大体相同，只是取值的过程从“按上下界和步长枚举所有点”改为“在上下界内随机投大量点”，投点数量可由运行效率调整。

最优化相关基础概念

  • 极大值、极小值、充要条件 blah blah
  • 向量范数：即（二维上）两点距离在高维上的叫法。

p - 范数：

$$||x||_p=(|x_1|^p+|x_2|^p+ \cdots + |x_p|^p)^{1/p}$$

更多向量范数知识见链接

  • 等值线及其性质
  • 全微分、方向导数、梯度

例题一：1996 全国赛 B 题 洗衣机节水问题

保证洗衣机的洗涤效果，如何减少用水。

建模前期分析报告模板：

  • 明确建模目标
  • 抓关键词
  • 抓条件
  • 列建模方向
  • 建模难点
  • …

对于这个题来说，其实是一个化学题，建立了多次加水时，每次加水量和最后剩余污渍量的函数关系，建立了非线性最优化模型，使用 fmincon 求解。

例题二：2005 全国赛 B 题 DVD 租赁问题

略。主要看建模过程（列最优化模型）的过程。

线性规划

后面部分是 2019.11.2 的讲座，笔记作者为 OrangeRain.

  • 问题一：无脑题，三原料两产品，高中数学
  • 问题二也挺无脑的

线性规划模型中，约束条件为不等式时，可以 $f(x)+yi=0, yi \geq 0$ 化为等式约束
一般会直接丢到 matlab 中求解。

一类切割问题，一类指派问题
对于切割钢条问题
我们先分析一根钢条切完。
一通分析上 intlinprog

整数约束
一道课后思考题：先用 linprog 找到一个近似解 + 蒙特卡洛法

背包

ccc，究极傻逼背包，正解不讲的

遗传算法

模仿遗传的过程
蚁群算法代码量少，模拟蚁群找食物，完事了，基本上不考。
模拟退火代码量少，很好写的，简单介绍。
就是个建模，把决策变量取值当做个体，
要用约束条件限制变异，但这里讲的遗传算法不用约束（有约束也可以带进去处理）
交叉之后可能发生变异，

准备工作：
概念：基因、染色体
进制转换：二进制转十进制、十进制转二进制

生物遗传学 最优化模型
种群 可行集的一些元素
个体 可行集的一个元素
染色体 同上
基因 同上
二进制编码 同上

在这个模型中，后四个其实在同一个层面上

先进行模块化设计，设计出一个较为通用的遗传算法的 MATLAB 语言实现

可是不是有工具箱吗

有约束优化

$$\min f(x) \\
s.t.\begin{cases}
g_i(x) \geq 0 & i = 1,2,…,m \\
h_j(x) = 0 & j = 1,2,…,l
\end{cases}$$

有约束优化常用罚函数法转化为无约束优化：当函数即将达到可行域边界/超出边界时，急剧增加其函数值作为“惩罚”，对可行域内的点不予惩罚。前者是内点法，后者是外点法。

外点罚函数法

可构造以下函数，将对 $f(x)$ 的有约束优化转为对 $F(x,\sigma)$ 的无约束优化：

$$F(x,\sigma) = f(x) + \sigma P(x)$$

其中惩罚因子 $\sigma$ 是很大的正数， $P(x)$是连续函数。

$$P(x)=\sum_{j=1}^l\phi(h_j(x)) + \sum_{i=1}^m\psi(g_i(x))$$

其中 $\phi$ 和 $\psi$ 是满足以下条件的连续函数：

$$
\phi(y)
\begin{cases}
=0 & y=0 \\
>0 & y \neq 0
\end{cases} \qquad
\psi(y)
\begin{cases}
=0 & y \geq 0 \\
>0 & y<0
\end{cases}
$$

一个可行的取法为：

$$\phi(h_j(x))=|h_j(x)|^\beta \qquad \psi(g_i(x))=[\max\{0,-g_i(x)\}]^\alpha$$

常取 $\alpha = \beta = 2$。显然在可行域内，$P(x)=0$，否则 $P(x)>0$。

  1. $\sigma P(x)$ 被称为罚项，$F(x,\sigma)$ 被称为罚函数。
  2. 注意，惩罚因子 $\sigma$ 越大，找到的点就越接近极值点；但并不是 $\sigma$ 越大就越好，因为 $\sigma$ 越大会使得求导和 Hesse 矩阵趋向病态。
  3. 外点罚函数法要求 $f(x)$ 在可行域外也有定义，如没有定义，需要考虑内点罚函数法。

算法

算法实现上，常使用 $\sigma$ 从小取到大的方法：

  1. 初始化：
    • 选定初始点 $x^{(0)}$
    • 初始罚因子 $\sigma$
    • 设置罚因子的放大系数 $c>1$（如 $c=10$）
    • 置 $k=1$
  2. 以 $x^{(k-1)}$ 为起始点，求解无约束问题
    $$\min F(x,\sigma)$$得到极小点 $x^{(k)}$。
  3. 若 $\sigma P(x) < \varepsilon$，则输出 $x^{(k)}$ 并终止，否则转 4。
  4. 置 $\sigma = \sigma * c, k=k+1$，并返回 2。

这种通过求解一系列无约束问题来获得约束问题最优解的方法称作序列无约束极小化SUMT。

例题

下面是运用外点法求解

$$ \min f(x) = x_1^2+2x_2^2 \\
s.t. \; x_1 + x_2 >= 1$$

的 MATLAB 程序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
global sigma f P;
f=@(x)x(1)^2+2*x(2)^2;
g=@(x)x(1)+x(2)-1;
P=@(x)max(0,-g(x))^2;
x=[0,0]
sigma=1;
c=10;
epsilon=1e-5;

for k = 1:20
    x = fminunc(@F,x)
    disp(sigma*P(x))
    if (sigma*P(x) < epsilon)
        disp('answer successfully found')
        break;
    end
    sigma=sigma*c;
end

function y=F(x)
global sigma f P;
    y=f(x)+sigma*P(x);
end

最值为：

1
2
x(1) = 0.6666
x(2) = 0.3334

内点罚函数法

外点罚函数法要求 $f(x)$ 在可行域外也有定义，如没有定义，需要考虑内点罚函数法。

这次，当迭代点靠近边界点时，就迅速增加目标函数值（而不是当迭代点在可行域外时才动手），保证迭代点在可行域内。

由于内点罚函数总是从内点出发，于是不适用于有等式约束的问题。

$$\min f(x) \\
s.t. \; g_i(x) \geq 0 \quad i = 1,2,…,m$$

类似于外点法，我们定义障碍函数：

$$F(x,\mu)=f(x)+\mu B(x)$$

不同的时，当 $x$ 趋向可行域边界时，让 $B(x) \to \infty$。$B(x)$ 的设定一般如下：

$$\begin{aligned}
B(x) &= \sum_{i=1}^m \frac{1}{g_i(x)} \\
B(x) &= -\sum_{i=1}^m \ln g_i(x) \\
B(x) &= \sum_{i=1}^m \frac{1}{g_i^2(x)} \\
\end{aligned}$$

对于 $\mu$，如果 $\mu$ 越小，无约束问题的最优解越接近原问题的最优解。因此要求 $\{\mu\}$ 是单调下降序列。

实际应用中，还可以对不同的 $g_i(x)$ 施加不同的 $\mu_i$：

$$F(x,\mu)=f(x)+\sum_{i=1}^n \mu_i\frac{1}{g_i(x)}$$

算法与外点法大致相同，故略。参数选择上，可选 $r_1 = 10, C = 0.1$。

例题

$$\min f(x)=(x_1-1)^2+x_2^2 \\
s.t. \begin{cases}
x_1 \geq 0 \\
x_2 \geq 0
\end{cases}$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
global mu f B
f=@(x)(x(1)-1)^2+x(2)^2;
B=@(x)log(x(1))+log(x(2));
x=[1,1];
mu=10;
c=0.1;
epsilon=1e-9;
for k = 1:20
    x = fminunc(@F,x)
    disp(mu*B(x))
    if (abs(mu*B(x)) < epsilon)
        break;
    end
    mu=mu*c;
end

function y=F(x)
global mu f B;
    y=f(x)-mu*B(x);
end

最值为：

1
2
x(1) = 1.000
x(2) = 0.000

多目标优化

多目标优化，即需要求最优的目标函数有两个或多个。

显然不是任意问题都可以使得目标函数值全为最优。于是产生了一个词叫“非劣解”。

非劣解就是几个解，这几个解无法确定谁好谁劣。其余的解就是劣解。

~~个人感觉就是把几个目标用一个新的函数 Z 连立起来，就可以当做一个单目标优化来解了。