优化控制理论-Note
1 分类
1.1 按约束分类
约束优化箱子集优化无约束优化
1.2 线性与非线性
从目标函数/约束式的角度：
线性规划
求解方法：单纯形法；
有结论：若线性优化问题有有限个解，则一定有某个最优解是可行区域的一个极点。
极点：基本可行点→基本可行基→线性无关，
B
−
1
b
≥
0
B^{-1}b\geq0
B−1b≥0;
A
m
×
n
=
(
P
1
,
P
2
,
.
.
.
,
P
m
,
P
m
+
1
,
.
.
.
P
n
)
=
(
B
,
N
)
;
A_{m×n}=(P_1,P_2,...,P_m,P_{m+1},...P_n)=(B,N);
Am×n=(P1,P2,...,Pm,Pm+1,...Pn)=(B,N);其中，
B
B
B为基矩阵，
N
N
N为非基矩阵。
单纯形法思路：先找出可行域的一个极点，根据一定规则判断是否最优，否则转换到与之相邻的另一极点，并使目标函数值更优；如此下去，直到找到某一最优解为止。
非线性规划
1.3 决策变量的连续性
连续优化
x
∈
R
x\in R
x∈R
离散优化
整数规划0-1规划 混合整数规划
1.4 目标函数
单目标多目标
1.5 按决策变量的随机性
确定性优化
x
∈
R
x\in R
x∈R随机性优化
x
∼
N
(
0
,
1
)
x\sim N(0,1)
x∼N(0,1)鲁棒性优化问题
若
f
(
x
)
f(x)
f(x)为非线性、
g
(
x
)
g(x)
g(x)和
h
(
x
)
h(x)
h(x)均为线性——线性约束非线性目标优化LCNLP;
若
f
(
x
)
f(x)
f(x)线性、
g
(
x
)
g(x)
g(x)和
h
(
x
)
h(x)
h(x)均为非线性——非线性约束线性目标优化；
若
f
(
x
)
f(x)
f(x)、
g
(
x
)
g(x)
g(x)和
h
(
x
)
h(x)
h(x)均为多项式polynomials，最高幂power为2——二次优化QP问题；
etc…
2.基本定义
2.1 凸与非凸优化
凸函数：满足
f
(
α
x
1
+
(
1
−
α
)
x
2
)
≤
α
f
(
x
1
)
+
(
1
−
α
)
f
(
x
2
)
,
∀
x
∈
[
0
,
1
]
;
f(\alpha x_1+(1-\alpha) x_2)\leq \alpha f(x_1)+(1-\alpha) f(x_2),{\forall}x\in[0,1];
f(αx1+(1−α)x2)≤αf(x1)+(1−α)f(x2),∀x∈[0,1];凸集：S1,S2,S3任意线性组合均在S内，则S为凸集；
Fig 2.1 凸函数和凸集
在Fig 2.1(a)中，f1(x)为凹函数；f2(x)为既凸也凹；f3(x)为凸函数。
2.2 凸优化问题
满足：f(x)的最小化的情况下为凸的，在最大化情况下为凹的，且
S
=
{
x
∣
h
(
x
)
≤
0
,
g
(
x
)
=
0
,
∀
x
∈
S
}
S=\lbrace x|h(x)\leq 0,g(x)=0,\forall x\in S\rbrace
S={x∣h(x)≤0,g(x)=0,∀x∈S}是凸集;凸优化与凹优化相比的主要优点：凸优化的一个局部最优解也是这个凸优化的全局最优；
2.3 优化问题中考虑不确定性
Stochastic Optimization
m
i
n
x
∈
X
g
(
x
)
+
E
(
m
i
n
y
∈
Y
(
x
,
ε
)
f
(
y
)
)
min_{x \in X}g(x)+E(min_{y\in Y(x,\varepsilon)}f(y))
minx∈Xg(x)+E(miny∈Y(x,ε)f(y))
其中，
ε
\varepsilon
ε为不确定性变量，
Y
Y
Y为
x
x
x和
ε
\varepsilon
ε决定的域，从中选取
y
y
y。随机优化在由概率分布定义的可行区域内寻找最优解。
Robust Optimization
min
x
∈
X
g
(
x
)
+
m
a
x
ε
∈
U
(
m
i
n
y
∈
Y
(
x
,
ε
)
f
(
y
)
)
\min_{x \in X}g(x)+max_{\varepsilon\in U}(min_{y\in Y(x,\varepsilon)}f(y))
minx∈Xg(x)+maxε∈U(miny∈Y(x,ε)f(y))
主要区别是不确定变量
ε
\varepsilon
ε 是由不确定几个
U
U
U描述的，包括上/下限和不确定预算。鲁棒性优化实在定义的不确定性集合中寻找最坏情况下的最优解，因此带来保守性。
Interval Optimization
[
m
i
n
x
∈
X
g
(
x
)
+
m
i
n
ε
∈
U
(
m
i
n
y
∈
Y
(
x
,
ε
)
f
(
y
)
)
,
m
i
n
x
∈
X
g
(
x
)
+
m
a
x
ε
∈
U
(
m
i
n
y
∈
Y
(
x
,
ε
)
f
(
y
)
)
]
[min_{x\in X}g(x)+min_{\varepsilon\in U}(min_{y\in Y(x,\varepsilon)}f(y)),min_{x\in X}g(x)+max_{\varepsilon\in U}(min_{y\in Y(x,\varepsilon)}f(y))]
[minx∈Xg(x)+minε∈U(miny∈Y(x,ε)f(y)),minx∈Xg(x)+maxε∈U(miny∈Y(x,ε)f(y))]
区间优化的主要优点是得到的区间可以用来分析不确定性对系统的影响（给出最乐观与最悲观的情况）。
Two-stage Optimization
m
i
n
x
∈
X
g
(
x
)
+
m
i
n
y
∈
Y
f
(
y
)
s
.
t
.
l
(
x
)
≤
0
,
h
(
x
)
≤
0
min_{x\in X}g(x)+min_{y\in Y}f(y) \\ s.t. l(x)\leq0,h(x)\leq0
minx∈Xg(x)+miny∈Yf(y)s.t.l(x)≤0,h(x)≤0
Bi-level Optimization
m
i
n
x
∈
X
,
y
∈
Y
F
(
x
,
y
)
s
.
t
.
G
i
(
x
,
y
)
≤
0
,
i
∈
1
,
2
,
.
.
.
,
I
y
∈
a
r
g
m
i
n
z
∈
Y
f
(
x
,
z
)
,
g
(
x
,
z
)
≤
0
min_{x\in X,y\in Y}F(x,y) \\s.t. G_i(x,y)\leq0,i\in1,2,...,I \\ y \in arg min_{z\in Y}{f(x,z),g(x,z)\leq0}
minx∈X,y∈YF(x,y)s.t.Gi(x,y)≤0,i∈1,2,...,Iy∈argminz∈Yf(x,z),g(x,z)≤0
其中，
F
(
x
,
y
)
F(x,y)
F(x,y)表示上层目标函数，
f
（
x
,
z
）
f（x,z）
f（x,z）表示下层目标函数，
G
i
(
x
,
y
)
G_i(x,y)
Gi(x,y)与
g
(
x
,
z
)
g(x,z)
g(x,z)分别表示上下层的不等式约束函数，
y
y
y是
F
（
x
，
y
）
F（x，y）
F（x，y）的决策变量，也是
f
(
x
,
z
)
f(x,z)
f(x,z)最小的最优决策变量。
应用于[混合储能系统的多目标管理问题]1
3.实用理论
3.1 对偶原理
考虑如下线性规划模型：
原始问题：
m
a
x
c
T
x
s
.
t
.
A
x
≤
b
,
x
≥
0
max\ c^Tx\ \ s.t.\ Ax\leq b,x\geq 0
max cTx s.t. Ax≤b,x≥0；
对偶问题：
m
i
n
b
T
y
s
.
t
.
A
T
y
≥
c
,
y
≥
0
min\ b^Ty\ \ s.t.\ A^Ty\geq c,y\geq 0
min bTy s.t. ATy≥c,y≥0;
不等式方向相反，即原问题的约束不等式是"
≥
\geq
≥"，则对偶问题的对应条件则是"
≤
\leq
≤"，优化方向相反。
理解：对偶问题可看作是原始问题的”行列转置“，即
原始问题中的第
j
j
j列系数与其对偶问题中的第
j
j
j行的系数相同；原始目标函数的各个系数行与其对偶问题右侧的各常数列相同；原始问题右侧的各常数列与其对偶目标函数的各个系数行相同；在这一对问题中，不等式方向和优化方向相反。 表示：
考虑线性规划：
m
i
n
C
T
x
s
.
t
.
A
x
=
b
,
x
≥
0
min\ C^Tx\ \ \ s.t.\ Ax=b,x\geq0
min CTx s.t. Ax=b,x≥0;
把其中的等式约束变成不等式约束，即：
m
i
n
C
T
x
s
.
t
.
[
A
−
A
]
x
=
b
,
x
≥
0
min\ C^Tx\ \ s.t.\begin{bmatrix}A\\ -A\end{bmatrix}x=b,x\geq0
min CTx s.t.[A−A]x=b,x≥0;
它的最优问题，即：
m
a
x
[
b
T
−
b
T
]
[
y
1
y
2
]
,
s
.
t
.
[
A
T
−
A
T
]
[
y
1
y
2
]
≤
c
max \begin{bmatrix}b^T&-b^T\end{bmatrix} \begin{bmatrix}y_1\\y_2\end{bmatrix} ,s.t.\begin{bmatrix}A^T & -A^T\end{bmatrix} \begin{bmatrix}y_1\\y_2\end{bmatrix}\leq c
max[bT−bT][y1y2],s.t.[AT−AT][y1y2]≤c;
其中，
y
1
y_1
y1和
y
2
y_2
y2分别表示对应于约束
A
x
≥
b
Ax\geq b
Ax≥b和
−
A
x
≥
−
b
-Ax\geq -b
−Ax≥−b的对偶变量组。
令
y
=
y
1
−
y
2
y=y_1-y_2
y=y1−y2,则上式又可写成
m
a
x
b
T
y
s
.
t
.
A
T
y
≤
c
max\ b^Ty\ \ s.t.\ A^Ty\leq c
max bTy s.t. ATy≤c.
基本性质：
对称性：对偶问题的对偶原问题；弱对偶性：若
x
‾
\overline{x}
x是原问题的可行解，
y
‾
\overline{y}
y是对偶问题的可行解。则存在
c
T
x
‾
≤
b
T
y
‾
c^T\overline{x}\leq b^T\overline{y}
cTx≤bTy;无界性：若原问题（对偶问题）为无界解，则对偶问题（原问题）无可行解；
可行解释最优解时的性质：设
x
^
\hat{x}
x^是原问题的可行解，
y
^
\hat{y}
y^是对偶问题的可行解，当
c
T
x
^
=
b
T
y
^
c^T\hat{x}=b^T\hat{y}
cTx^=bTy^时，
x
^
\hat{x}
x^和
y
^
\hat{y}
y^是最优解；对偶定理：若原问题有最优解，那么对偶问题也有最优解；且目标函数值相同。互补松弛性：若
x
^
\hat{x}
x^和
y
^
\hat{y}
y^分别原问题和对偶问题的最优解，则
y
^
T
(
A
x
^
−
b
)
=
0
，
x
^
T
(
A
T
y
^
−
c
)
=
0
;
\hat{y}^T(A\hat{x}-b)=0，\hat{x}^T(A^T\hat{y}-c)=0;
y^T(Ax^−b)=0，x^T(ATy^−c)=0;
3.2 其他（待补充）
4. MATLAB求解——线性规划和非线性规划
4.1 求解线性规划
linprog命名
[x,faval]=linprog(f,A,b,Aeq,beq,lb,ub,x0)
可以输入help linprog查看官方介绍,相对应的：
min
x
f
T
x
\min _{x} f^{T} x
minxfTx 且
{
A
⋅
x
≤
b
,
Aeq
⋅
x
=
b
e
q
,
l
b
≤
x
≤
u
b
.
\left\{\begin{aligned} A \cdot x & \leq b, \\ \text { Aeq } \cdot x &=b e q, \\ l b & \leq x \leq u b . \end{aligned}\right.
⎩⎪⎨⎪⎧A⋅x Aeq ⋅xlb≤b,=beq,≤x≤ub.；
[x,faval]返回值中x为最优解，faval为最优值；
f表示目标函数中各个变量前的系数向量，如果是求最小值问题，那么f就是各个变量的系数，如果是求最大值问题，那么f就是各个变量的系数的相反数；
A和b分别表示不等式约束
A
⋅
x
≤
b
A\cdot x\leq b
A⋅x≤b中的矩阵A和向量b；
Aeq和beq分别表示等式约束
A
e
q
⋅
x
=
b
e
q
Aeq\cdot x=beq
Aeq⋅x=beq中的矩阵Aeq和向量beq;
lb和ub分别表示自变量的上下界组成的向量，如果没有上下界，该选项用[]表示，如果只有部分变量有上下界，其余的变量没有，那么可以把没有上下界的变量的上下界设为-inf或者inf，使lb或者ub的长度符合要求；
x0表示变量的初始值，可以缺省；
实例 4.1 求如下的线性规划问题：
m
i
n
z
=
−
5
x
1
−
4
x
2
−
6
x
3
s
.
t
.
{
x
1
−
x
2
+
x
3
≤
20
3
x
1
+
2
x
2
+
4
x
+
3
≤
42
3
x
1
+
2
x
2
≤
30
x
1
,
x
2
,
x
3
≥
0
min\ z=-5x_1-4x_2-6x_3\ \ s.t.\begin{cases}x_1-x_2+x_3\leq20\\ 3x_1+2x_2+4x+3\leq 42\\ 3x_1+2x_2\leq30\\ x_1,x_2,x_3\geq 0\end{cases}
min z=−5x1−4x2−6x3 s.t.⎩⎪⎪⎪⎨⎪⎪⎪⎧x1−x2+x3≤203x1+2x2+4x+3≤423x1+2x2≤30x1,x2,x3≥0
过程： f=[-5;-4;-6];#目标优化函数
A=[1 -1 1;3 2 4;3 2 0];#约束条件
b=[20;42;30];#约束条件
lb=[0;0;0];#自变量存在下界
[x,faval]=linprog(f,A,b,[],[],lb);#无等式约束条件，因此Abq和beq为[]
#运行结果
#Optimal solution found.
x =
0
15.0000
3.0000
fval =
-78
optimtool工具箱
直接在命令窗口输入optimtool，打开该工具箱。接下来，本文将对该工具箱进行基本介绍，详细描述可通过help查阅官方说明文件。
图4-1 Optimtool操作界面
如图4-1所示，根据实例4.1的问题填写参数，完成求解。上述两种方法得出的结果是相同的。
4.2 求解非线性规划
fmincon命令
fmincon('fun',x0,A,b,Aeq,beq,lb,ub,'nonlinearcondition')
各个参数的含义如下：
fun目标函数（以求最小值为目标函数）；
x0最优解迭代的初始值；
A,b线性约束不等式
A
⋅
x
≤
b
A\cdot x\leq b
A⋅x≤b；
Aeq,beq线性约束等式
A
e
q
⋅
x
=
b
e
q
Aeq\cdot x=beq
Aeq⋅x=beq；
lb,ub自变量的上下界；
nonlinearcondition非线性约束函数，它有两个返回值，一个为非线性不等式约束，另一个是非线性等式约束。在具体编写代码过程中，可以将线性约束也写在非线性约束函数nonlinearcondition中，简化代码。
实例 4.2 求如下的线性规划问题：
m
i
n
z
=
x
1
2
+
x
2
2
+
8
s
.
t
.
{
x
1
2
−
x
2
≥
0
−
x
1
−
x
2
2
+
2
=
0
x
1
,
x
2
≥
0
min z=x_1^2+x_2^2+8\ \ \ \ s.t.\begin{cases}x_1^2-x_2\geq0\\ -x_1-x_2^2+2=0\\ x_1,x_2\geq 0\end{cases}
minz=x12+x22+8 s.t.⎩⎪⎨⎪⎧x12−x2≥0−x1−x22+2=0x1,x2≥0
过程：
#首先，编写目标函数的M函数文件，并保存为fun.m
function f =fun(x)
f = x(1)^2 + x(2)^2 + 8;
end
#编写线性和非线性约束的等式或不等式，编写M函数文件，并保存为nonlinearcondition.m
function [f,ceq] = nonlinearcondition(x)
f = - x(1)^2 + x(2);
ceq = - x(1) - x(2)^2 + 2; %非线性等式约束
end
#最后，在Command窗口输入如下代码
[x,fval] =fmincon('fun',[0;0],[],[],[],[],[0;0],[],'nonlinearcondition')
#运行结果
x =
1.0000
1.0000
fval =
10.0000
optimtool工具箱
同样地，直接在命令窗口输入optimtool，打开该工具箱。建立了fun.m文件和nonlinearcondition.m文件后，在工具箱对应位置做出更改，如图4-2中的绿色箭头所示。
图4-2 实例4.2的Optimtool工具求解
可以看出，上述两种方法所得结果均是相同的。
5.小结
本文介绍了优化问题的分类情况，以及学习优化控制理论所需掌握的部分基本定义。同时，对对偶原理进行了详细介绍。最后，介绍了如何利用MATLAB求解线性规划和非线性规划问题。
小小展望：(后续更新) 2022.5.19
增加对非线性规划问题求解的方法表述；增加特殊的线性规划和非线性规划问题和求解方法的介绍，如0-1规划、二次规划；考虑组合优化以及更复杂优化问题的求解思路介绍；实例中设计的优化问题相对简单，后续将考虑进一步介绍Optimtool工具，以求解复杂问题；后期会更新用强化学习的各类方法求解多目标优化问题的方法；
参考文献
[1] Fang S, Wang H. Optimization-Based Energy Management for Multi-energy Maritime Grids[M]. Springer Singapore 2021. DOI: 10.1007/978-981-33-6734-0.
[2] 卓金武, 魏永生, 等. MATLAB在数学建模中的应用[M].北京：北京航空航天大学 2011: 18-24.