优化入门知识

什么是优化问题

优化问题：求最优，例如获利最大、最少损失、最短路径、最小化风险等等。
例如：之前文章提到华为杯2019F题多约束条件下智能飞行器航迹快速规划，其中第一问就涉及求飞行器从A点到B点带约束下的最短路径。

如何判断是不是优化问题

题目带有优化、规划、最值、安排、分配、最合理等等。

题目涉及到图，例如三维空间飞行、二维地图上旅行。

优化模型建模

优化模型格式：决策变量+目标函数+约束条件。

决策变量：能够对目标结果产生影响的变量。
$$x_i,i=1,2,...,n$$

目标函数：通常都是一个Min或者Max求某个决策变量的函数表达式。例如：
$$Min(orMax)z=f(x),x=(x_1,...,x_n{)}^T$$
约束条件：以s.t.为开头，后面写上约束条件。
$$s.t.\{\begin{array}{l}{g}_1(x)⩽0\\ g_2(x)⩽0\\ ...\\ g_n(x)⩽0\end{array}$$

求解器

优化模型建立好之后，选择什么样的算法去解模型是比赛的关键。

求解器：用来求解模型的程序、算法之类的，在matlab里面求解器填写的其实就是函数模型。

优化问题的分类

从目标函数的个数来说：可以分成单目标和多目标。

从问题的类型来说：可以分为规划类、图论和动态规划。

规划类按照决策变量在目标函数和约束条件中是否线性：可以分为线性规划和非线性规划。
规划类中，比较特殊的是决策变量为整数的“整数规划”，和决策变量只能取0或者1的“0-1规划”。
非线性规划中比较特殊的是二次规划，目标函数是关于决策变量的二次函数，约束条件是线性函数。

图论中常见的问题有：最短路、最小生成树、网络流和排队论。

多目标规划

条件：线性规划和非线性规划只有一个目标函数，多目标函数有多个目标函数（$f_i(x)$），讲究一个既要还要。

方法：多目标转化为单目标。

• 优先因子：可以主观上给目标函数进行一个重要性排序，来使得整体的完成情况尽量好，也就是优先因子，相当于权重（$P_i$）。
  $$min\sum P_i{f}_i(x)$$
• 平方加权：知道每个目标理想值的情况下，可以求每个目标函数和理想值的平方和，可以带上权重。
  $$min\sum {\lambda }_i[f_i(x)-{f_i}^{\ast }{]}^2$$
• 乘除法：如果每个目标重要程度一样。
  $$min\frac{f_1(x)f_2(x)...f_k(x)}{f_{k+1}(x)f_{k+2}(x)...f_n(x)}$$
• 分开求最优解对比：有时候单独最优解之间差距可能不是很大，例如之前华为杯2019F题，有个论文就是分别求最优路径和最少矫正点，然后对比。

特殊：问题中存在刚性约束和柔性约束。刚性约束就是必须要满足的，否者就是不可行解。柔性约束就是可以存在偏差的，例如使目标f(x)尽可能不少于5，可以在5左右有正负偏差。这个正负偏差可以记作$d^{+}和d^{-}$， d + = m i n { f ( x ) − f ∗ , 0 } , d − = − m i n { f ∗ − f ( x ) , 0 } d^+=min\{f(x)-f^*,0\},d^-=-min\{f^*-f(x),0\} d+=min{f(x)−f∗,0},d−=−min{f∗−f(x),0}。
例子：三个目标函数$f_1(x)、f_2(x)、f_3(x)$，三个目标是柔性约束，1尽量不超过、2尽量等于、3尽量不少于，会发现柔性约束都有“尽量”两个字作为修饰。最终的多目标规划函数可以写成：
min ⁡ { P 1 d 1 + + P 2 ( d 2 − + d 2 + ) + P 3 d 3 − } \min{\{P_1{d_1}^++P_2({d_2}^-+{d_2}^+)+P_3{d_3}^-\}} min{P1​d1​++P2​(d2​−+d2​+)+P3​d3​−}
扩展一下格式：
$$min\sum P_i({w_i}^{+}{d_i}^{+}+{w_i}^{-}{d_i}^{-})$$

总结：多目标规划，可以转换成为单目标问题，然后单目标去看符合单目标中那种取套，根据情况套回规划类、图论和动态规划中。