这波知识点分享可得接稳了！非线性模型线性化方法&技巧！
这波知识点分享可得接稳了！非线性模型线性化方法&技巧！
在电力系统优化领域，将非线性模型线性化是常见的需求。本文总结了11种非线性形式的线性化方法，包括分段函数、绝对值函数、逻辑或、含有0-1变量的乘积形式等。通过引入0-1变量和大M的方法，可以将复杂的非线性问题转化为线性规划问题，从而使用成熟的单纯形法进行求解。
现在电力系统优化方向的文章几乎都要提及将非线性模型线性化，使用的方法大致可包括分段线性化（最基础），混合整数线性化方法，绝对值法，大M方法，关于非线性模型线性化方法的文章和推文介绍也数不胜数，本文在阅读大量线性化方法文章的基础上，总结出一篇较为基础的非线性模型线性化方法，旨在用白话文说清如何进行模型线性化，让读者真正明白什么是线性化，话不多说，请看图文！
首先说一下求解线性规划问题最为成熟的方法：单纯形法！
单纯形法由乔治·丹齐格（George Dantzig）于1947年提出，是解决线性规划问题的一种经典算法。单纯形法是一种用于求解线性规划问题的数学方法。线性规划是一种数学优化技术，用于在给定约束条件下最大化或最小化线性目标函数。
单纯形法的基本思想是从一个可行解开始，通过不断移动解空间中的顶点（角点）来搜索最优解，即沿着规划区域约束的交界点搜寻。算法选择一个非基本变量进入基本变量集，同时将一个基本变量离开基本变量集，以改善目标函数的值，直到找到最优解。尽管单纯形法是一个有效的算法，但对于某些特定类型的线性规划问题，它可能不够高效。可实际在科研建模时，目标函数或是约束条件，极大概率会出现非线性的形式，下面就引出为什么要进行非线性模型线性化。
此时若选择采用启发式算法（遗传算法、模拟退火算法、粒子群算法等）求解，有很大概率会陷入局部最优解，相当于放弃了求精确解，也放弃了投Top期刊的机会。因此，了解并懂得何种形式可以转化为线性和如何线性化，It is important！
授人以鱼不如授人以渔！首先，解决如何线性化的问题可以翻书、百度或查看本文；但若不知道何种非线性数学形式可以转化为线性模型，还是等于不会；在经过诸多小伙伴的交流和广泛调研后，在解决较为复杂的非线性问题时，主要会面临以下两大类问题：
针对以上两个问题，本文指出（敲黑板！！！）：
具有分段函数形式、绝对值函数形式、最小/大值函数形式、逻辑或形式、含有0-1变量的乘积形式、混合整数形式以及分式目标函数，均可实现线性化。而线性化的主要手段其实就两点：一是引入0-1变量，二是引入很大的整数M。灵活运用这两点可以解决优化方向绝大部分的非线性问题。
其中巧妙，独躬身推演方能知晓！
下面详细说明每种问题的线性化方法：
1. 分段函数
分段函数表达式：
线性化结果：
其中，y是引入的辅助0-1变量，M是一个很大的整数，一般取值1+10e6。简单通过分类讨论y=0和y=1便能理解上述式子的含义。
举例说明：
线性化处理结果：
当x=3时，f（x）取最小值-0.25。
2. 绝对值函数
举例：要求线性化如下数学模型
方法1：用yi代替绝对值部分
注意，yi=|xi|的本质数学含义其实就是：yi≥xi和yi≥-xi。这个数学思想非常重要，可以解决很多有关绝对值的问题。
方法2：用ui、vi代替
这种方法没有那么直观，以后看到绝对值问题，脑海中有这种思路就好啦。
高中或是高数课上学过如下定理：
则之前的数学模型可以线性化为：
举例说明：
证明：
将左边|xi|转化为ui+vi，x转化为u-v。注意，这里的x是向量，对于x下标中的每个i都是成立的，可不能以为只有一个约束条件。
3. MaxMin/MinMax函数
以下图上半部分的MaxMin函数为例：基于k项minCX函数的值（矩阵写法，省略了求和号，不方便打转置符号），再取其中的最大值。
该形式下的线性化方法是：用z替代minCX函数，这样z便≤CX，又由目标函数是取最大的z，从而限制住z 不会无限小下去，而只会取满足条件的z。图中下半部分的MinMax函数同理。
这种情况类似于高数中的夹逼定理（判断极限是否存在），进一步也可能意识到，如果换为MaxMax和MinMin函数，以上这套思路就行不通了。
举例说明：
目标函数：
线性化结果：
实际也确实是这样，线性化MaxMax和MinMin函数较为复杂一些，需要借助下面第四点线性化逻辑或的思维。
4. 逻辑或
该部分主要针对约束条件（含有逻辑或）的线性化操作。通常，逻辑或两端的约束存在三种情形。
情形1.1：逻辑或两段均为≤，即：
此时线性化方法为：
情形1.2：逻辑或两边均为≥，即：
线性化结果：
情形1.3：逻辑或两段一边≤，一边≥，即：
线性化结果：
引入u 和v 两个0-1变量和大M。分类讨论u和v取0或1的四种情形便能理解以上过程。思路非常巧妙，希望大家多悟几遍并消化。
这里情形1讲了3种情形，大家理解了这个逻辑，第四种"一边≤一边≥"的情形想必大家总结规律也可以得到，线性化思路是类似的。这里总结句口诀：大减小加。含义是：
只要用了大于等于，后面M前面的符号一定是减号；
只要用了小于等于，后面M前面的符号一定是加号。
情形2：一端为≤，一端为=，即：
此时线性化方法为：
可见，多添加一个≥的式子即可。同理，“一端为≥，一端为=”、“一端为=，一端为≤”和“一端为=，一端为≥”的三种情况也可以相应得到，这里不再赘述。
情形3：两端均为=，即：
此时线性化方法为：
可见，逻辑或是通过新引入的两个0-1变量u和v来控制的，感叹此中巧妙！
5. MaxMax/MinMin函数
该部分需要运用上述技巧逻辑或。以MaxMax函数为例：
首先，令z=maxCX，但若此时约束条件写成z≥CX的形式是不行的，因为这样会让z取值到无穷大，故一定要写出“z≤某个值”的形式。
这时，就需要引入0-1变量和大M，如上式所示。yk求和≥1的含义是“至少有一个成立”。实际计算时，只会有一个k让yk=1，其余yk为0。具体原因，也是夹逼定理的思想，大家多多领会。
同理，MinMin函数的线性化过程如下。
注意，这里是加号。yk=0该约束不起作用，只有当yk=1时才会起作用。
举例说明：
目标函数：
线性化结果：
6. 含有0-1变量的乘积形式
众所周知，决策变量（连续型）乘以决策变量（连续型）即为二次型，是非线性的，在电力系统中类似于设备的投切状态。该形式无法转化为线性。
但如果将其中一个（或两个）连续型变量改为0-1变量，此时是可以进行线性化操作的。
设该非线性形式为y=x1*x2，根据x1、x2两个变量的取值范围不同，会存在以下三种情形：
情形1：x1、x2均为0-1变量
分析y=x1*x2不同取值下的计算结果如下：
总结表中呈现的规律，有：
这里很巧妙地提出变量y也为0-1变量，然后通过变量x来限制其上下界。
依此类推，大家也可以试试x1、x2、y取其他0-1对应值时的线性化构造方法。
情形2：x1为0-1变量，x2取值范围为[0，a]
同样试着计算出取值表：
总结表中呈现的规律，有：
第一个和最后一个约束主要为了限定 y 的范围属于[0, a]。第三个约束是最为巧妙的，要限制 y 的范围，必须还要写出“y ≥ 某值”的形式。该思想是需要大家领悟消化的。
情形3：x1为0-1变量，x2取值范围为[a，b]
同样试着计算出取值表：
总结表中呈现的规律，有：
其中，M可以是任意正值，因为该约束只有在x1=1时才起作用，而此时M(1-x1)=0。
7. 分式目标函数形式
原优化问题形式：
Step1：令
带入上面可得：
再令z=xy代入上式可得：
举例说明：
观察上式，只有目标函数为分式（非线性）。除法形式在数学上通常是不受欢迎，此时可以考虑转化为乘法形式。即令：
则目标函数转化为：
观察如上形式，又出现新的非线性函数：xz和yz。此时若令xz=u，yz=v，则约束条件也需要做出相应的改变（约束两边同乘z）：
可见，分式目标函数的线性化有两个步骤。一是将分母的倒数设置为新的线性参数；二是令非线性的xz 和 yz 等于新的线性参数。
该方法对分式函数具有普适性，巧妙且简单。
8. Max/Min函数
该形式虽较为常见，但其线性化方法却不那么直观。
以z=max(x,y)为例。很容易可以写出约束z≥x和z≥y。但显然这是不够的，因为该约束只约束了z的下界，未约束上界。
上界的约束可以转化为逻辑或的表述法，即：x≥z或y≥z成立。
下面介绍逻辑或两端均为≤，即：
此时线性化方法为：
此时，需引入0-1变量u、v且u+v=1，和大M来实现逻辑或的线性化，具体地：
同理，Min函数的线性化方法如下：
消化吸收以上思想后，扩展如何进行z=max(x, y, 10)的三个最值函数如何线性化：
线性化结果为：
9. 混合整数变量线性化
这里提到的混合整数指的是：某变量是整数或者是连续变量。如下：
此时，只需要用另两个变量x和y代替z即可。
基于此，构造如下的线性化方法：
不知大家发现没有，该方法也是非常巧妙的，没有直接借鉴逻辑或的线性化思路，而是仅通过引入一个0-1变量u实现。
当u=0时，前两个约束不起作用，后两个约束起作用，使得z=y；当u=1时，后两个约束不起作用，前两个约束起作用，使得z=x。
10. 含半连续变量问题
考虑约束如下：x=0或者a≤x≤b
线性化结果为：
该变量常用于带有fixed cost形式的目标函数或者约束上。
11. if-then
If
成立，then
成立
线性化结果为：
归纳而言：
（1）了解并懂得何种非线性数学形式可以线性化比知道如何转化更重要；
（2）线性化方法的主要思路是引入0-1变量和大M的方法，将等式约束转化为不等式约束。至于构造时是采用≥还是≤，是加还是减的形式（指±M(1±y），熟能生巧。
至此，介绍了11种非线性数学形式的线性化方法/技巧。如果大家了解还有其他的数学形式也可以线性化欢迎私信交流讨论，总结后再分享给大家。
感谢ZH博主《科研小飞》对本推文的大力支持！
最后，祝大家paper库库发！
参考文献：