二次规划-Lagrange方法
已于 2023-06-30 14:37:16 修改
阅读量1k
收藏
10
点赞数
2
Lagrange方法
基本理论
Lagrange方法是求解等式约束二次规划问题的一种方法.
等式约束的二次规划问题
考虑
min
1
2
x
T
H
x
+
c
T
x
s
.
t
.
A
x
=
b
,
\begin{align*} & \min \quad \frac{1}{2}x^THx+c^Tx\\ & s.t. \quad Ax=b, \end{align*}
min21xTHx+cTxs.t.Ax=b,
其中
H
H
H是
n
n
n阶对称矩阵,
A
A
A是
m
×
n
m\times n
m×n阶矩阵,
r
a
n
k
(
A
)
=
m
,
x
∈
R
n
rank(A)=m, x\in \mathcal{R}^n
rank(A)=m,x∈Rn,
b
∈
R
m
b\in \mathcal{R}^m
b∈Rm.
Lagrange乘子法
定义Lagrange函数
L
(
x
,
λ
)
=
1
2
x
T
H
x
+
c
T
x
−
λ
T
(
A
x
−
b
)
,
L(x,\lambda)=\frac{1}{2}x^THx+c^Tx-\lambda^T(Ax-b),
L(x,λ)=21xTHx+cTx−λT(Ax−b),
令
∇
x
L
(
x
,
λ
)
=
0
,
∇
λ
L
(
x
,
λ
)
=
0
,
\nabla_x L(x,\lambda)=0,\quad \nabla_{\lambda} L(x,\lambda)=0,
∇xL(x,λ)=0,∇λL(x,λ)=0,
可得
H
x
+
c
−
A
T
λ
=
0
,
−
A
x
+
b
=
0.
\begin{align*} & Hx+c-A^T\lambda=0,\\ & -Ax+b=0. \end{align*}
Hx+c−ATλ=0,−Ax+b=0.
即
[
H
−
A
T
−
A
0
]
[
x
λ
]
=
[
−
c
−
b
]
,
\begin{bmatrix} H & -A^T\\ -A & 0 \end{bmatrix} \begin{bmatrix} x \\ \lambda \end{bmatrix} =\begin{bmatrix} -c\\ -b \end{bmatrix},
[H−A−AT0][xλ]=[−c−b],
此时的系数矩阵
[ H − A T − A 0 ] \begin{bmatrix} H & -A^T\\ -A & 0 \end{bmatrix} [H−A−AT0]
称为Lagrange矩阵.
假设Lagrange矩阵是可逆的, 其中系数矩阵
H
H
H可逆, 引入以下记号
Q
=
H
−
1
−
H
−
1
A
T
(
A
H
−
1
A
T
)
−
1
A
H
−
1
,
R
=
(
A
H
−
1
A
T
)
−
1
A
H
−
1
,
S
=
−
(
A
H
−
1
A
T
)
−
1
.
\begin{align*} & Q=H^{-1}-H^{-1}A^T(AH^{-1}A^T)^{-1}AH^{-1},\\ & R=(AH^{-1}A^T)^{-1}AH^{-1},\\ & S=-(AH^{-1}A^T)^{-1}. \end{align*}
Q=H−1−H−1AT(AH−1AT)−1AH−1,R=(AH−1AT)−1AH−1,S=−(AH−1AT)−1.
根据广义初等变换, 原二次规划问题的解为
x
^
=
−
Q
c
+
R
T
b
,
λ
^
=
R
c
−
S
b
.
\begin{align*} & \hat{x}=-Qc+R^Tb,\\ & \hat{\lambda}=Rc-Sb. \end{align*}
x^=−Qc+RTb,λ^=Rc−Sb.
设
x
(
k
)
x^{(k)}
x(k)是原问题的任一可行解, 即满足
A
x
(
k
)
=
b
Ax^{(k)}=b
Ax(k)=b. 在此点目标函数的梯度
g
k
=
∇
f
(
x
(
k
)
)
=
H
x
(
k
)
+
c
,
g_k=\nabla f(x^{(k)})=Hx^{(k)}+c,
gk=∇f(x(k))=Hx(k)+c,
则可以给出
x
^
,
λ
^
\hat{x},\hat{\lambda}
x^,λ^的另一种表达式
x
^
=
x
(
k
)
−
Q
g
k
,
λ
^
=
R
g
k
.
\begin{align*} & \hat{x}=x^{(k)}-Qg_k,\\ & \hat{\lambda}=Rg_k. \end{align*}
x^=x(k)−Qgk,λ^=Rgk.
Code
代码主要参考了 Dsp Tian的博客.
clear all;
close all;
clc;
% min x1^2+2*x2^2+x3^2+x2^2-2*x1*x2+x3
% s.t. x1+x2+x3 = 4
% 2*x1-x2+x3 = 2
%{
H=[2 -2 0;
-2 4 0;
0 0 2];
c = [0 0 1]';
A=[1 1 1;
2 -1 1];
b=[4 2]';
%}
%min 2*x1^2+x2^2+x1*x2-x1-x2
%s.t. x1+x2 = 1
H=[4 1;
1 2];
c=[-1 -1]';
A=[1 1];
b=1;
%min 1.5*x1^2-x1*x2+x2^2-x2*x3+0.5*x3^2+x1+x2+x3
%s.t. x1+2*x2+x3 = 4
%{
H=[3 -1 0;
-1 2 -1;
0 -1 1];
c=[1 1 1]';
A=[1 2 1];
b=4;
%}
invH = inv(H);
S = -inv(A*invH*A');
R = -S*A*invH;
Q = invH-invH*A'*R;
x = -Q*c+R'*b;
[x1,x2]=meshgrid(0:0.02:0.7,0:0.02:1.5);
z1 = 2*x1.^2+x2.^2+x1.*x2-x1-x2;
mesh(x1,x2,z1);
x1 = 0:0.02:0.7;
x2 = -x1 + 1;
hold on;
plot3(x1,x2,zeros(1,length(x1)),'r');
plot3(x(1),x(2),0,'r*')
plot3(x(1),x(2),2*x(1).^2+x(2).^2+x(1).*x(2)-x(1)-x(2),'b*')
legend('待求问题函数','约束条件','最优解','最小值')
Reference_bib
@book{陈宝林2005最优化理论与算法,
title={最优化理论与算法},
author={陈宝林},
publisher={最优化理论与算法},
year={2005},
}
扫一扫
2039
暂无认证
到【灌水乐园】发言
哥哥能送个会员吗: 请问在运行时显示patch的参数不足是什么原因呀
Markzzp: 博主您好，可以看一下你载入的流场数据吗，就是第一行的那个.mat文件
CSDN-Ada助手: 恭喜您撰写第17篇博客！标题《拉普拉斯特征映射(Laplacian-Eigenmaps)》引人入胜。您的文章内容深度剖析了拉普拉斯特征映射的原理和应用，让我对这个主题有了更深入的理解。非常感谢您的分享。 在未来的创作中，我谦虚地建议您考虑加入一些实例或案例，以便更好地帮助读者理解和应用拉普拉斯特征映射。此外，您还可以探讨一些与拉普拉斯特征映射相关的扩展方法或应用领域，这将进一步丰富您的博客内容。期待您的下一篇文章，继续为我们带来更多有价值的知识！
CSDN-Ada助手: 非常祝贺您写了第11篇博客！标题“二次规划-Lagrange方法”听起来非常有深度和挑战性。您的持续创作精神令人钦佩。我希望您能继续分享更多关于二次规划和Lagrange方法的知识，这对于我们这些对数学和优化问题感兴趣的读者来说将是非常有价值的。在下一篇博客中，如果可能的话，我希望您可以通过实际案例或者更多图表来解释Lagrange方法的具体应用，这将使读者更容易理解和运用这一方法。再次恭喜您，并期待您的下一篇文章！
CSDN-Ada助手: 恭喜你写了第13篇博客！标题中的“约束优化问题--乘子法”听起来很有深度和挑战性。你对这个话题的研究让我印象深刻。希望你能继续保持创作的热情和努力，分享更多有关优化问题的知识。 在下一步的创作中，我建议你可以尝试将乘子法与实际问题结合，探索如何应用它解决现实生活中的约束优化问题。这样的实际案例会使你的博客更具实用性和吸引力。当然，这只是一个建议，期待你能根据自己的兴趣和专业知识，继续为我们带来精彩的内容。祝愿你在未来的创作中取得更大的成就！