1. 线性规划

1.1 模型描述

目标函数为线性函数，约束条件为一组线性等式或不等式的规划问题。通式标准型一般为：
$$\min _{x} c^{T}x$$

$$s.t. = \left\lbrace
\begin{array}{ll}
Ax \leq b\newline
Aeq \cdot x = beq\newline
lb \leq x \leq ub
\end{array} \right. $$

在MATLAB中的调用函数为：
$$[x,fval] = linprog(c,A,b,Aeq,beq,lb,ub,x_{0},OPTIONS)$$

返回待求解向量$x$以及目标函数值$fval$，参数中$x_{0}$是初始值，OPTIONS是控制参数，其余的参数根据标准型可以知道其含有的意义。
需要注意的是

  1. 调用函数形式默认是求最小化问题$\min$，如果求最大化问题$\max$，则可以将函数中的$c$取反为$-c$，将最大化问题转移为最小化问题
  2. 同样地默认形式的不等式符号是$\leq$，若为$\geq$则需要两边取反使符号变反，所以$A$与$b$都需要取反。

1.2 MATLAB程序演示

MATLAB中自带有求解该模型最优解的函数，上面一节已提到，下面是一个示例，假设问题为：
$$\max z=2x_{1}+3x_{2}-5x_{3}$$

$$s.t. = \left\lbrace
\begin{array}{rl}
x_{1}+x_{2}+x_{3}&=&7\newline
2x_{1}-5x_{2}+x_{3}&\geq&10\newline
x_{1}+3x_{2}+x_{3}&\leq&12\newline
x_{1},x_{2},x_{3}&\geq&0
\end{array} \right. $$

MATLAB代码如下：

1
2
3
4
5
6
7
8
9
10
11
c=[2,3,-5];
A=[-2,5,-1;1,3,1];% 需要将>=号换成<=号，两边取反
b=[-10;12];
Aeq=[1,1,1];
beq=7;
lb=[0;0;0];
ub=[inf;inf;inf];
x0=zeros(3,1);
% 最大化问题转换为最小化，所以c取反
[x,fval]=linprog(-c,A,b,Aeq,beq,lb,ub,x0)
value=c*x

运行结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
x =

    6.4286
    0.5714
         0

fval =

  -14.5714

value =

   14.5714

2. 非线性规划

2.1 模型描述

在一组等式或不等式的约束下的最优化问题，其中至少一个为非线性函数，标准型一般为：
$$\min f(x)$$

$$s.t. = \left\lbrace
\begin{array}{ll}
Ax \leq b\newline
Aeq \cdot x = beq\newline
C(x) \leq 0\newline
Ceq(x) = 0\newline
lb \leq x \leq ub
\end{array} \right. $$

$f(x)$为标量函数，$C(x)$和$Ceq(x)$是非线性向量函数。
在MATLAB中的调用函数为：
$$[x,fval]=fmincon(fun,x_{0},A,b,Aeq,beq,lb,ub,nonlcon,options)$$

$fun$是m文件定义的$f(x)$,$nonlcon$是m文件定义的$C(x)$和$Ceq(x)$
需要注意的默认形式与线性约束一致，都是默认最小化问题，不等式为$\leq$形式。

2.2 MATLAB程序演示

示例：
$$\min f(x)=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+8$$

$$s.t. = \left\lbrace
\begin{array}{rl}
x_{1}^{2}-x_{2}+x_{3}^{2}&\geq&0\newline
x_{1}+x_{2}^{2}+x_{3}^{3}&\leq&20\newline
-x_{1}-x_{2}^{2}+2&=&0\newline
x_{2}+2x_{3}^{2}&=&3\newline
x_{1},x_{2},x_{3}&\geq&0
\end{array} \right. $$

MATLAB代码如下：
$f$函数fun.m:

1
2
3
4
% x为待求解向量
function f = fun(x)
f = x(1)^2+x(2)^2+x(3)^2+8;
end

定义了$f(x)$。
$C(x)$和$Ceq(x)$的定义在nonlcon.m:

1
2
3
4
function [c,ceq] = nonlcon(x)
c = [-x(1)^2+x(2)-x(3)^2;x(1)+x(2)^2+x(3)^3-20];% 非线性不等式约束C(x)
ceq = [-x(1)-x(2)^2+2;x(2)+2*x(3)^2-3];         % 非线性等式约束Ceq(x)
end

主文件main.m:

1
2
3
4
lb=[0;0;0];
ub=[inf;inf;inf];
x0=zeros(3,1);
[x,fval]=fmincon('fun',x0,[],[],[],[],lb,ub,'nonlcon')

执行前需要保证拥有optimization toolbox，不然会报错“函数或变量 ‘getIpOptions’ 无法识别。”添加附加功能即可。
结果如下：

1
2
3
4
5
6
7
8
9
x =

    0.5522
    1.2033
    0.9478

fval =

   10.6511

3. 二次规划

3.1 模型描述

目标函数为决策变量$x$的二次函数，且约束条件都是线性的，标准型一般为：
$$\min \frac{1}{2}x^{T}Hx+f^{T}x$$

$$s.t. Ax \leq b$$

其中$H$是实对称矩阵。关于H的确定可以参考二次型及矩阵的标准型相关知识，总体来说便是，$x_{i}x_{j}$与$x_{j}x_{i}$两项计算最终结果是标量，最终的系数是相加后的结果，因为$H$是实对称矩阵所以元素$a_{ij}$和$a_{ji}$的项是$\frac{系数}{2}$，而平方项的生成只有一种情况，系数即为对称矩阵的对角线元素，标准型前面有$\frac{1}{2}$，所以矩阵结果还需要再×2生成$H$。
在MATLAB中的调用函数为：
$$[x,fval]=quadprog(H,f,A,b,Aeq,beq,lb,ub,x_{0},options)$$

3.2 MATLAB程序演示

求解二次规划：
$$\min f(x) = 2x_{1}^{2}-4x_{1}x_{2}+4x_{2}^{2}-6x_{1}-3x_{2}$$

$$s.t. = \left\lbrace
\begin{array}{rl}
x_{1}+x_{2}&\leq&3\newline
4x_{1}+x_{2}&\leq&9\newline
x_{1},x_{2}&\geq&0
\end{array} \right. $$

MATLAB程序：

1
2
3
4
5
6
7
8
H=[4,-4;-4,8];
f=[-6;-3];
A=[1,1;4,1];
b=[3;9];
lb=[0;0];
ub=[inf;inf];
x0=zeros(2,1);
[x,fval]=quadprog(H,f,A,b,[],[],lb,ub,x0)

结果如下：

1
2
3
4
5
6
7
8
x =

    1.9500
    1.0500

fval =

  -11.0250

4. 整数规划

4.1 模型描述

特殊的线性规划，部分或全部决策变量$x$被限制为整数，标准型也与之前一致。
在MATLAB中的调用函数为：
$$[x,fval,exitflag]=intlinprog(f,intcon,A,b,Aeq,beq,lb,ub,x_{0},options)$$

$f$与线性规划的$c$一致，表示目标函数的系数;返回值多出一个$exitflag$，表示是否存在这么一个整数值;$intcon$为有整数约束的变量位置，例如如果第一个变量限制为整数，则$intcon=[1]$，如果第一个第二个均被限制为整数，则$intcon=[1,2]$。

不再演示。（懒= 。 =）

5. 目标规划

5.1 模型描述

在线性规划基础上为适应多目标决策而发展起来的。
异同点：

  • 线性规划求的是一组约束条件下的极值，目标规划是多个目标决策，可求得实际的解。
  • 线性规划-最优解，目标规划-满意解。
  • 线性规划中的约束条件重要度是一样的，而目标规划中有主次之分，重要度有优先级，即优先满足什么再满足什么。

正负偏差变量：
目标值：预先给定的某个目标的期望值
决策值：选定决策变量后的函数对应值
正偏差变量：决策值达到目标值部分，为 $d^{+}=\max \lbrace d-d_{0},0\rbrace$
负偏差变量：决策值未达到目标值部分，为 $d^{-}=-\min \lbrace d-d_{0},0\rbrace$
决策值不可能既超过目标值又未到达目标值，所以 $d^{+}\times d^{-}=0$，因为叉乘为0意味着两个向量是平行的。

当目标值确定后，所要做的是尽量靠近目标值，所以目标函数即为一个最小化问题，最小化与目标值的距离，目标函数为:
$$\min z=f(d^{+},d^{-})$$

一共有三种形式：

  1. 要求恰好达到目标值。正、负偏差变量均要小：
    $$\min z=f(d^{+}+d^{-})$$

  2. 仅不超过目标值，正偏差变量尽可能小：
    $$\min z=f(d^{+})$$

  3. 仅超过目标值，负偏差变量尽可能小：
    $$\min z=f(d^{-})$$

拥有优先级顺序的目标规划算法基本上使用序贯式算法求解，用LINGO求解。

5.2 基于遗传算法的MATLAB函数

5.2.1 遗传算法

根据目标函数构造一个适应度函数，种群中的每个个体即为问题的每个解，理论思想基于进化论，最先开始初始化种群，然后对每个个体（即问题的解）进行评估（计算适应度）、选择（基于适应度选择）、交叉和变异，不断多轮迭代以生成一个适应度最好的个体为最优解，则算法停止。

5.2.2 MATLAB程序

MATLAB自带了$gamultiobj$函数来求解多目标优化问题，它是基于遗传算法的，形式为：
$$[x,fval] = gamultiobj(fitnessfcn,nvars,A,b,Aeq,beq,lb,ub,options)$$

$fitnessfcn$表示目标函数（适应度函数）,$nvars$表示变量个数。
下面是一个实例，求解多目标最优化问题：
$$\min f_{1}(x_{1},x_{2})=x_{1}^{4}-10x_{1}^{2}+x_{1}x_{2}+x_{2}^{4}-x_{1}^{2}x_{2}^{2}$$

$$\min f_{2}(x_{1},x_{2})=x_{2}^{4}-x_{1}^{2}x_{2}^{2}+x_{1}^{4}+x_{1}x_{2}$$

$$s.t. = \left\lbrace
\begin{array}{ll}
-5\leq x_{1}\leq 5\newline
-5\leq x_{2}\leq 5\newline
\end{array} \right. $$

适应度函数在fun.m中定义：

1
2
3
4
function f = fun(x)
f(1) = x(1)^4 - 10*x(1)^2+x(1)*x(2) + x(2)^4 - (x(1)^2)*(x(2)^2);
f(2) = x(2)^4 - (x(1)^2)*(x(2)^2) + x(1)^4 + x(1)*x(2);
end

主函数main.m：

1
2
3
4
5
6
fitnessfcn = @fun;
nvars=2;
lb=[-5;-5];
ub=[5;5];
options = gaoptimset('ParetoFraction',0.3,'PopulationSize',100,'Generations',200,'StallGenLimit',200,'TolFun',1e-100,'PlotFcns',@gaplotpareto);
[x,fval] = gamultiobj(fitnessfcn,nvars,[],[],[],[],lb,ub,options)

这里设置的是最优前端个体系数ParetoFraction为0.3，种群大小PopulationSize为100，最大遗传代数Generations为200，停止代数StallGenLimit为200，适应度函数偏差TolFun为1e-100，这里绘制的是第一前端个体的分布情况。（没有理解，之后再好好看遗传算法吧= =）

需要额外添加global optimization toolbox，不然gaoptimset会报错。
结果如下：
ga

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
x =

   -0.7068    0.7069
    2.6718   -1.9767
    2.6718   -1.9767
    1.1010   -1.1090
   -0.7068    0.7069
    1.0033   -0.8825
    2.3382   -1.6462
    2.2078   -1.6127
    1.5425   -1.3584
    0.8928   -0.8851
    1.2533   -1.2192
    1.6961   -1.1779
    1.9208   -1.5240
    2.4265   -1.8077
    1.3321   -1.1060
    1.8264   -1.4294
    1.6293   -1.2674
    2.0690   -1.4104
    2.3934   -1.8064
    0.8211   -0.6350
    2.3069   -1.6462
    1.6542   -1.3731
    1.5056   -1.4106
    2.4705   -1.8969
    1.9671   -1.2967
    1.8732   -1.4172
    1.4146   -1.2315
    2.0216   -1.5813
    2.6195   -1.9283
    2.1531   -1.5368

fval =

   -5.2460   -0.2500
  -38.3334   33.0543
  -38.3334   33.0543
  -11.8524    0.2702
   -5.2460   -0.2500
  -10.1148   -0.0496
  -36.1025   18.5677
  -34.4574   14.2848
  -21.2132    2.5805
   -8.1357   -0.1656
  -14.8940    0.8139
  -24.5568    4.2121
  -29.3845    7.5102
  -37.1598   21.7182
  -16.7445    1.0014
  -27.4827    5.8762
  -23.2484    3.2983
  -31.9596   10.8491
  -36.8378   20.4479
   -6.9179   -0.1761
  -35.7722   17.4465
  -23.7514    3.6117
  -20.2049    2.4637
  -37.4830   23.5512
  -29.9510    8.7424
  -28.4455    6.6446
  -18.4840    1.5276
  -31.3289    9.5381
  -38.2733   30.3431
  -33.5465   12.8101

5.3 基于目标获得法的MATLAB函数

多目标优化问题中基于目标获得法的方法是需要先单独求得每个目标函数最优值，然后再进行计算的，MATLAB中还有$fgoalattain$函数，形式如下：
$$[x,fval] = fgoalattain(fun,x_{0},goal,weight,A,b,Aeq,beq,lb,ub,nonlcon,options)$$

$goal$为目标函数分别达到的最优值，$weight$为目标函数之间的权重，一般即为最优值的绝对值，$fun$即为目标函数。
先分别求出目标函数的最优值：
fun1.m:

1
2
3
function f = fun1(x)
f = x(1)^4 - 10*x(1)^2+x(1)*x(2) + x(2)^4 - (x(1)^2)*(x(2)^2);
end

fun2.m:

1
2
3
function f = fun2(x)
f = x(2)^4 - (x(1)^2)*(x(2)^2) + x(1)^4 + x(1)*x(2);
end

主函数main.m:

1
2
3
4
5
6
7
8
9
lb=[-5;-5];
ub=[5;5];
x0=rand(2,1);
[x1,fval1]=fmincon('fun1',x0,[],[],[],[],lb,ub,[]);
[x2,fval2]=fmincon('fun2',x0,[],[],[],[],lb,ub,[]);
% 以上先求出分别的最优值
goal=[fval1,fval2];
weight=[abs(fval1),abs(fval2)];
[x,fval]=fgoalattain('fun',goal,weight,x0,[],[],[],[],lb,ub)

结果如下：

1
2
3
4
5
6
7
x =

   -0.7071    0.7071

fval =

   -5.2500   -0.2500

使用$fgoalattain$获得一组最优解，与之前的基于遗传算法的方法不同，最优解很大程度取决于初始化值$x_{0}$（因为我发现初始化为0后它就不动了= 。 =）

（更新ing）