二次规划(Lagrange 方法,起作用集方法)

2024-06-19 18:44

本文主要是介绍二次规划(Lagrange 方法,起作用集方法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

二次规划是非线性规划中一种特殊情形,它的目标函数是二次实函数,约束是线性的。由于二次规划比较简单,便于求解,且一些非线性规划可以转化为求解一系列二次规划问题,因此二次规划算法较早引起人们的重视,成为求解非线性规划的一个重要通径。二次规划的算法较多,本章介绍其中几个典型的方法,它们是 Lagrange 方法起作用集方法Lemke 方法路径路踪法

一、Lagrange 方法

考虑二次规划问题
min ⁡ 1 2 x T H x + c T x s . t . A x = b \begin{aligned} &\min\quad\quad \dfrac{1}{2} \pmb x^T\pmb H \pmb x + \pmb c^T \pmb x\\[2ex] &\mathrm{ \ s.t.}\quad\quad\ \ \pmb A\pmb x=\pmb b \end{aligned} min21xTHx+cTx s.t.  Ax=b

其中, H \pmb H H n n n 阶对称矩阵, A \pmb A A m × n m\times n m×n 矩阵, A \pmb A A 的秩为 m m m b \pmb b b m m m 维列向量。

通过 Lagrange 乘子法求解:首先定义 Language 函数
L ( x , λ ) = 1 2 x T H x + c T x − λ T ( A x − b ) L(\pmb x,\pmb\lambda) = \frac{1}{2}\pmb x^T\pmb H \pmb x + \pmb c^T \pmb x - \pmb\lambda^T(\pmb A\pmb x-\pmb b) L(x,λ)=21xTHx+cTxλT(Axb)


∇ x L ( x , λ ) = 0 , ∇ λ L ( x , λ ) = 0 \nabla_xL(\pmb x,\pmb\lambda)=0,\quad\nabla_{\pmb\lambda}L(\pmb x,\pmb\lambda)=0 xL(x,λ)=0,λL(x,λ)=0

得到方程组
H x + c − A T λ = 0 − A + b = 0 \begin{aligned} &\pmb H\pmb x + \pmb c - \pmb A^T\pmb\lambda=\pmb 0\\[1ex] &-\pmb A\pmb +\pmb b = \pmb 0 \end{aligned} Hx+cATλ=0A+b=0

将此方程组写成
[ H − A T − A − 0 ] [ x λ ] = [ − c − b ] \left[ \begin{matrix} \pmb H & - \pmb A^T\\[1ex] -\pmb A & - \pmb 0\\ \end{matrix} \right] \left[ \begin{matrix} \pmb x \\[2ex] \pmb \lambda\\ \end{matrix} \right]= \left[ \begin{matrix} -\pmb c \\[2ex] -\pmb b\\ \end{matrix} \right] [HAAT0][xλ]=[cb]

将系数矩阵称为 Lagrange 矩阵

设上述 Lagrange 矩阵可逆,且为对称矩阵,则其逆矩阵也为对称矩阵,可表示为
[ H − A T − A − 0 ] − 1 = [ Q − R T − R − S ] \left[ \begin{matrix} \pmb H & - \pmb A^T\\[1ex] -\pmb A & - \pmb 0\\ \end{matrix} \right]^{-1}= \left[ \begin{matrix} \pmb Q & - \pmb R^T\\[1ex] -\pmb R & - \pmb S\\ \end{matrix} \right] [HAAT0]1=[QRRTS]

由可逆矩阵性质,即
[ H − A T − A − 0 ] [ Q − R T − R − S ] = I m + n \left[ \begin{matrix} \pmb H & - \pmb A^T\\[1ex] -\pmb A & - \pmb 0\\ \end{matrix} \right] \left[ \begin{matrix} \pmb Q & - \pmb R^T\\[1ex] -\pmb R & - \pmb S\\ \end{matrix} \right]=\pmb I_{m+n} [HAAT0][QRRTS]=Im+n

推得
H Q + A T R = I n H R T + ( A T S ) = 0 n × m A Q = 0 m × n A R T = I m \begin{aligned} &\pmb{HQ}+\pmb{A^TR}=\pmb I_n\\[1ex] &\pmb{HR^T}+\pmb(A^TS)=\pmb0_{n\times m}\\[1ex] &\pmb{AQ}=\pmb 0_{m\times n}\\[1ex] &\pmb{AR^T} = \pmb I_m \end{aligned} HQ+ATR=InHRT+(ATS)=0n×mAQ=0m×nART=Im

假设矩阵 H \pmb H H 可逆,则可以得到矩阵 Q , R , S \pmb{Q,R,S} Q,R,S 的表达式
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{aligned} &\pmb{Q}=\pmb H^{-1} - \pmb H^{-1}\pmb A^T(\pmb A\pmb H^{-1}\pmb A^T)^{-1}\pmb A\pmb H^{-1},\\[1ex] &\pmb R = (\pmb A \pmb H^{-1}\pmb A^T)^{-1}\pmb A \pmb H^{-1},\\[1ex] &\pmb S = -(\pmb A \pmb H^{-1}\pmb A^T)^{-1} \end{aligned} Q=H1H1AT(AH1AT)1AH1,R=(AH1AT)1AH1,S=(AH1AT)1

从而可得问题的解
x ∗ = − Q c + R T b λ ∗ = R c − S b \begin{aligned} &\pmb x^\ast = -\pmb{Qc} + \pmb R^T\pmb b\\[1ex] &\pmb \lambda^\ast = \pmb {Rc}-\pmb{Sb} \end{aligned} x=Qc+RTbλ=RcSb

二、起作用集方法

1、起作用集方法的分析推导

考虑具有不等式约束的二次规划问题
min ⁡ f ( x ) = 1 2 x T H x + c T x s . t . A x ≥ b \begin{aligned} &\min\quad\quad f(\pmb x)=\dfrac{1}{2} \pmb x^T\pmb H \pmb x + \pmb c^T \pmb x\\[2ex] &\mathrm{ \ s.t.}\quad\quad\ \ \pmb A\pmb x\geq\pmb b \end{aligned} minf(x)=21xTHx+cTx s.t.  Axb

其中, H \pmb H H n n n 阶对称正定矩阵, A \pmb A A m × n m\times n m×n 矩阵, A \pmb A A 的秩为 m m m b \pmb b b m m m 维列向量。

由于不等式约束的存在,不能直接用 Lagrange 方法求解,因此需将它转化为求解等式约束问题。运用起作用集方法,在每次追代中,以已知的可行点为起点,把在该点起作用约束作为等式约束,在此约束下极小化目标函数 f ( x ) f(\pmb x) f(x),而其余的约束暂且不管。求得新的比较好的可行点后,再重复以上做法,下面加以具体分析。

设在第 k k k 此迭代中,已知可行点 x ( k ) \pmb x^{(k)} x(k),在该点起作用约束指标集用 I ( k ) I^{(k)} I(k) 表示。这时需要求解等式约束
min ⁡ f ( x ) = 1 2 x T H x + c T x s . t . a i x = b i , i ∈ I ( k ) \begin{aligned} &\min\quad\quad f(\pmb x)=\dfrac{1}{2} \pmb x^T\pmb H \pmb x + \pmb c^T \pmb x\\[2ex] &\mathrm{ \ s.t.}\quad\quad\ \ \pmb a^i\pmb x=b_i,\quad i\in I^{(k)} \end{aligned} minf(x)=21xTHx+cTx s.t.  aix=bi,iI(k)

其中 a i \pmb a^i ai 是矩阵 A \pmb A A 的第 i i i 行。

为方便起见,现将坐标原点移至 x ( k ) \pmb x^{(k)} x(k),令
δ = x − x ( k ) \pmb\delta = \pmb x - \pmb x^{(k)} δ=xx(k)


f ( x ) = 1 2 ( δ + x ( k ) ) T H ( δ + x ( k ) ) + c T ( δ + x ( k ) ) = 1 2 δ T H δ + δ T H x ( k ) + 1 2 x ( k ) T H x ( k ) + c T δ + c T x ( k ) = 1 2 δ T H δ + ∇ f ( x ( k ) ) T δ + f ( x ( k ) ) \begin{aligned} f(\pmb x) &=\dfrac{1}{2} (\pmb\delta + \pmb x^{(k)})^T\pmb H (\pmb\delta + \pmb x^{(k)}) + \pmb c^T (\pmb\delta + \pmb x^{(k)})\\[2ex] &=\dfrac{1}{2}\pmb\delta^T\pmb H \pmb\delta + \pmb\delta ^T\pmb H\pmb x^{(k)}+\frac{1}{2}{\pmb x^{(k)}}^T \pmb H\pmb x^{(k)} +\pmb c^T\pmb\delta +\pmb c^T\pmb x^{(k)} \\[2ex] &=\frac{1}{2}\pmb\delta^T\pmb H \pmb\delta +\nabla f(\pmb x^{(k)})^T\pmb\delta + f(\pmb x^{(k)}) \end{aligned} f(x)=21(δ+x(k))TH(δ+x(k))+cT(δ+x(k))=21δTHδ+δTHx(k)+21x(k)THx(k)+cTδ+cTx(k)=21δTHδ+f(x(k))Tδ+f(x(k))

于是问题转化为求校正量 δ ( k ) \pmb\delta^{(k)} δ(k) 的问题
min ⁡ 1 2 δ T H δ + ∇ f ( x ( k ) ) T δ s . t . a i δ = 0 , i ∈ I ( k ) \begin{aligned} &\min\quad\quad \frac{1}{2}\pmb\delta^T\pmb H \pmb\delta +\nabla f(\pmb x^{(k)})^T\pmb\delta\\[2ex] &\mathrm{ \ s.t.}\quad\quad\ \ \pmb a^i\pmb\delta=0,\quad i\in I^{(k)} \end{aligned} min21δTHδ+f(x(k))Tδ s.t.  aiδ=0,iI(k)

解二次规划,求出最优解 δ ( k ) \pmb\delta^{(k)} δ(k),然后区别不同情形,决定下面应采取的步骤。

  • 如果 x ( k ) + δ ( k ) \pmb x^{(k)} + \pmb\delta^{(k)} x(k)+δ(k) 是可行点,且 δ ( k ) ≠ 0 \pmb\delta^{(k)}\neq\pmb0 δ(k)=0,则在第 k + 1 k+1 k+1 次迭代中,已知点取作 x ( k + 1 ) = x ( k ) + δ ( k ) \pmb x^{(k+1)}=\pmb x^{(k)}+\pmb\delta^{(k)} x(k+1)=x(k)+δ(k)
  • 如果 x ( k ) + δ ( k ) \pmb x^{(k)} + \pmb\delta^{(k)} x(k)+δ(k) 不是可行点,则沿方向 d ( k ) = δ ( k ) \pmb d^{(k)}=\pmb\delta^{(k)} d(k)=δ(k) 搜索,令
    x ( k + 1 ) = x ( k ) + a k d ( k ) \pmb x^{(k+1)} = \pmb x^{(k)} + a_k\pmb d^{(k)} x(k+1)=x(k)+akd(k)

现在分析怎样确定步长 a k a_k ak,根据保持可行性的要求,其应满足
a i ( x ( k ) + a k d ( k ) ) ≥ b i , i ∉ I ( k ) \pmb a^i(\pmb x^{(k)} + a_k\pmb d^{(k)})\geq b_i,\quad i\notin I^{(k)} ai(x(k)+akd(k))bi,i/I(k)

由于 x ( k ) \pmb x^{(k)} x(k) 是可行点,即 a i x ( k ) ≥ b i \pmb a^i\pmb x^{(k)}\geq b_i aix(k)bi,因此
a i d ( k ) ≥ 0 \pmb a^i\pmb d^{(k)}\geq 0 aid(k)0 时,对于任意非负数 a k a_k ak,上式总成立;
a i d ( k ) < 0 \pmb a^i\pmb d^{(k)}< 0 aid(k)<0 时,只要取正数
a k ≤ min ⁡ { b i − a i x ( k ) a i d ( k ) ∣ i ∉ I ( k ) , a i d ( k ) < 0 } ⏟ a ^ k a_k\leq\underbrace{\min\Bigg\lbrace\frac{b_i-\pmb a^i\pmb x^{(k)}}{\pmb a^i\pmb d^{(k)}}\bigg|i\notin I^{(k)},\ \pmb a^i\pmb d^{(k)}<0\Bigg\rbrace}_{\hat a_k} aka^k min{aid(k)biaix(k) i/I(k), aid(k)<0}

为了在第 k k k 次迭代中得到较好可行点,应取
a k = min ⁡ { 1 , a ^ k } , a_k=\min\lbrace1,\hat a_k\rbrace, ak=min{1,a^k},

并令
x ( k + 1 ) = x ( k ) + a k d ( k ) \pmb x^{(k+1)} = \pmb x^{(k)} + a_k\pmb d^{(k)} x(k+1)=x(k)+akd(k)

如果
a k = b p − a p x ( k ) a p d ( k ) < 1 a_k=\frac{b_p-\pmb a^p\pmb x^{(k)}}{\pmb a^p\pmb d^{(k)}}<1 ak=apd(k)bpapx(k)<1

则在点 x ( k + 1 ) \pmb x^{(k+1)} x(k+1),有
a p x ( k + 1 ) = a p ( x ( k ) + a k d ( k ) ) = b p \pmb a^p\pmb x^{(k+1)}=\pmb a^p(\pmb x^{(k)} + a_k\pmb d^{(k)})=b_p apx(k+1)=ap(x(k)+akd(k))=bp

因此,在 x ( k + 1 ) \pmb x^{(k+1)} x(k+1) 处, a p x ( k ) ≥ b p \pmb a^p\pmb x^{(k)}\geq b_p apx(k)bp 为起作用约束。这时,把指标 p p p 加入 I ( k ) I^{(k)} I(k),得到在 x ( k + 1 ) \pmb x^{(k+1)} x(k+1) 处的起作用约束指标集 I ( k + 1 ) I^{(k+1)} I(k+1)

这篇关于二次规划(Lagrange 方法,起作用集方法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1075837

相关文章

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

浅谈主机加固,六种有效的主机加固方法

在数字化时代,数据的价值不言而喻,但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露,企业的数据安全面临着前所未有的挑战。为了应对这些挑战,一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案,采用先进的安全容器中间件技术,构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限,即使在管理员权限被恶意利用的情况下,也能确保服务器的安全稳定运行。 普适主机加固措施:

webm怎么转换成mp4?这几种方法超多人在用!

webm怎么转换成mp4?WebM作为一种新兴的视频编码格式,近年来逐渐进入大众视野,其背后承载着诸多优势,但同时也伴随着不容忽视的局限性,首要挑战在于其兼容性边界,尽管WebM已广泛适应于众多网站与软件平台,但在特定应用环境或老旧设备上,其兼容难题依旧凸显,为用户体验带来不便,再者,WebM格式的非普适性也体现在编辑流程上,由于它并非行业内的通用标准,编辑过程中可能会遭遇格式不兼容的障碍,导致操

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

【北交大信息所AI-Max2】使用方法

BJTU信息所集群AI_MAX2使用方法 使用的前提是预约到相应的算力卡,拥有登录权限的账号密码,一般为导师组共用一个。 有浏览器、ssh工具就可以。 1.新建集群Terminal 浏览器登陆10.126.62.75 (如果是1集群把75改成66) 交互式开发 执行器选Terminal 密码随便设一个(需记住) 工作空间:私有数据、全部文件 加速器选GeForce_RTX_2080_Ti

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

【VUE】跨域问题的概念,以及解决方法。

目录 1.跨域概念 2.解决方法 2.1 配置网络请求代理 2.2 使用@CrossOrigin 注解 2.3 通过配置文件实现跨域 2.4 添加 CorsWebFilter 来解决跨域问题 1.跨域概念 跨域问题是由于浏览器实施了同源策略,该策略要求请求的域名、协议和端口必须与提供资源的服务相同。如果不相同,则需要服务器显式地允许这种跨域请求。一般在springbo