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

相关文章

SQL中redo log 刷⼊磁盘的常见方法

《SQL中redolog刷⼊磁盘的常见方法》本文主要介绍了SQL中redolog刷⼊磁盘的常见方法,将redolog刷入磁盘的方法确保了数据的持久性和一致性,下面就来具体介绍一下,感兴趣的可以了解... 目录Redo Log 刷入磁盘的方法Redo Log 刷入磁盘的过程代码示例(伪代码)在数据库系统中,r

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Java中Switch Case多个条件处理方法举例

《Java中SwitchCase多个条件处理方法举例》Java中switch语句用于根据变量值执行不同代码块,适用于多个条件的处理,:本文主要介绍Java中SwitchCase多个条件处理的相... 目录前言基本语法处理多个条件示例1:合并相同代码的多个case示例2:通过字符串合并多个case进阶用法使用

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

html5的响应式布局的方法示例详解

《html5的响应式布局的方法示例详解》:本文主要介绍了HTML5中使用媒体查询和Flexbox进行响应式布局的方法,简要介绍了CSSGrid布局的基础知识和如何实现自动换行的网格布局,详细内容请阅读本文,希望能对你有所帮助... 一 使用媒体查询响应式布局        使用的参数@media这是常用的

Spring 基于XML配置 bean管理 Bean-IOC的方法

《Spring基于XML配置bean管理Bean-IOC的方法》:本文主要介绍Spring基于XML配置bean管理Bean-IOC的方法,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录一. spring学习的核心内容二. 基于 XML 配置 bean1. 通过类型来获取 bean2. 通过

基于Python实现读取嵌套压缩包下文件的方法

《基于Python实现读取嵌套压缩包下文件的方法》工作中遇到的问题,需要用Python实现嵌套压缩包下文件读取,本文给大家介绍了详细的解决方法,并有相关的代码示例供大家参考,需要的朋友可以参考下... 目录思路完整代码代码优化思路打开外层zip压缩包并遍历文件:使用with zipfile.ZipFil

Python处理函数调用超时的四种方法

《Python处理函数调用超时的四种方法》在实际开发过程中,我们可能会遇到一些场景,需要对函数的执行时间进行限制,例如,当一个函数执行时间过长时,可能会导致程序卡顿、资源占用过高,因此,在某些情况下,... 目录前言func-timeout1. 安装 func-timeout2. 基本用法自定义进程subp

Python列表去重的4种核心方法与实战指南详解

《Python列表去重的4种核心方法与实战指南详解》在Python开发中,处理列表数据时经常需要去除重复元素,本文将详细介绍4种最实用的列表去重方法,有需要的小伙伴可以根据自己的需要进行选择... 目录方法1:集合(set)去重法(最快速)方法2:顺序遍历法(保持顺序)方法3:副本删除法(原地修改)方法4:

Python中判断对象是否为空的方法

《Python中判断对象是否为空的方法》在Python开发中,判断对象是否为“空”是高频操作,但看似简单的需求却暗藏玄机,从None到空容器,从零值到自定义对象的“假值”状态,不同场景下的“空”需要精... 目录一、python中的“空”值体系二、精准判定方法对比三、常见误区解析四、进阶处理技巧五、性能优化