二次规划(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

相关文章

macOS无效Launchpad图标轻松删除的4 种实用方法

《macOS无效Launchpad图标轻松删除的4种实用方法》mac中不在appstore上下载的应用经常在删除后它的图标还残留在launchpad中,并且长按图标也不会出现删除符号,下面解决这个问... 在 MACOS 上,Launchpad(也就是「启动台」)是一个便捷的 App 启动工具。但有时候,应

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

mysql出现ERROR 2003 (HY000): Can‘t connect to MySQL server on ‘localhost‘ (10061)的解决方法

《mysql出现ERROR2003(HY000):Can‘tconnecttoMySQLserveron‘localhost‘(10061)的解决方法》本文主要介绍了mysql出现... 目录前言:第一步:第二步:第三步:总结:前言:当你想通过命令窗口想打开mysql时候发现提http://www.cpp

Mysql删除几亿条数据表中的部分数据的方法实现

《Mysql删除几亿条数据表中的部分数据的方法实现》在MySQL中删除一个大表中的数据时,需要特别注意操作的性能和对系统的影响,本文主要介绍了Mysql删除几亿条数据表中的部分数据的方法实现,具有一定... 目录1、需求2、方案1. 使用 DELETE 语句分批删除2. 使用 INPLACE ALTER T

MySQL INSERT语句实现当记录不存在时插入的几种方法

《MySQLINSERT语句实现当记录不存在时插入的几种方法》MySQL的INSERT语句是用于向数据库表中插入新记录的关键命令,下面:本文主要介绍MySQLINSERT语句实现当记录不存在时... 目录使用 INSERT IGNORE使用 ON DUPLICATE KEY UPDATE使用 REPLACE

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

css中的 vertical-align与line-height作用详解

《css中的vertical-align与line-height作用详解》:本文主要介绍了CSS中的`vertical-align`和`line-height`属性,包括它们的作用、适用元素、属性值、常见使用场景、常见问题及解决方案,详细内容请阅读本文,希望能对你有所帮助... 目录vertical-ali

CentOS 7部署主域名服务器 DNS的方法

《CentOS7部署主域名服务器DNS的方法》文章详细介绍了在CentOS7上部署主域名服务器DNS的步骤,包括安装BIND服务、配置DNS服务、添加域名区域、创建区域文件、配置反向解析、检查配置... 目录1. 安装 BIND 服务和工具2.  配置 BIND 服务3 . 添加你的域名区域配置4.创建区域

mss32.dll文件丢失怎么办? 电脑提示mss32.dll丢失的多种修复方法

《mss32.dll文件丢失怎么办?电脑提示mss32.dll丢失的多种修复方法》最近,很多电脑用户可能遇到了mss32.dll文件丢失的问题,导致一些应用程序无法正常启动,那么,如何修复这个问题呢... 在电脑常年累月的使用过程中,偶尔会遇到一些问题令人头疼。像是某个程序尝试运行时,系统突然弹出一个错误提