Lyapunov optimization 李雅普诺夫优化

文章目录

  • 正文
    • 引言
    • Lyapunov drift for queueing networks 排队网络的Lyapunov漂移
      • Quadratic Lyapunov functions 二次李雅普诺夫函数
      • Bounding the Lyapunov drift 李亚普诺夫漂移的边界
      • A basic Lyapunov drift theorem 一个基本的李雅普诺夫漂移定理
    • Lyapunov optimization for queueing networks 排队网络的Lyapunov优化
  • 参考资料

正文

本文描述了动力系统的李雅普诺夫优化。(动力系统:随时间变化的系统)
给出了在排队网络最优控制中的应用实例。

引言

李雅普诺夫优化是指利用李雅普诺夫函数对动力系统进行最优控制。
李雅普诺夫函数在控制理论中被广泛应用于保证不同形式的系统稳定性。
系统在特定时间的状态通常用多维向量来描述。
李雅普诺夫函数是这种多维状态的一个非负标量度量(a nonnegative scalar measure)。
通常,函数被定义为当系统走向不希望的状态时变大
系统稳定性是通过采取控制动作使李雅普诺夫函数在负方向上向零漂移来实现的。

在这里插入图片描述

李雅普诺夫漂移是研究排队网络最优控制的核心。
一个典型的目标是稳定所有网络队列,同时优化某些性能目标,例如最小化平均能量或最大化平均吞吐量。
最小化二次Lyapunov函数的漂移对应用于网络稳定性的backpressure routing算法,也称为最大权重算法。[1][2]
在Lyapunov漂移中加入加权惩罚项并使其和最小化,得到了用于联合网络稳定性和惩罚最小化的漂移+惩罚算法。[3][4][5]
漂移加惩罚过程也可用于计算凸规划和线性规划的解。[6]

Lyapunov drift for queueing networks 排队网络的Lyapunov漂移

考虑一个随着具有标准化时隙 t ∈ { 0 , 1 , 2 , . . . } t∈\{0,1,2,...\} t{0,1,2,...}的离散时间变化的排队网络。
假设网络中有 N N N 个队列,并定义在时间 t t t 时队列积压向量为
在这里插入图片描述

Quadratic Lyapunov functions 二次李雅普诺夫函数

对于每个时隙,定义
在这里插入图片描述

该函数是网络中总队列积压的标量度量。它被称为关于队列状态的二次Lyapunov函数。

将李雅普诺夫漂移定义为该函数从一个时隙到下一个时隙的变化
在这里插入图片描述

Bounding the Lyapunov drift 李亚普诺夫漂移的边界

假设队列积压根据以下等式随时间变化:
在这里插入图片描述

其中, a i ( t ) a_{i}(t) ai(t) b i ( t ) b_{i}(t) bi(t)分别为时隙 t t t 上队列 i i i 的到达和服务机会。该式可用于计算任意时隙 t t t 上的Lyapunov漂移的边界:

由上式推出:
Δ L ( t ) = L ( t + 1 ) − L ( t ) = 1 2 ∑ i = 1 N ( Q i ( t + 1 ) 2 − Q i ( t ) 2 ) ≤ 1 2 ∑ i = 1 N ( ( Q i ( t ) + a i ( t ) − b i ( t ) ) 2 − Q i ( t ) 2 ) ≤ 1 2 ∑ i = 1 N ( a i ( t ) + b i ( t ) ) 2 + ∑ i = 1 N Q i ( t ) ( a i ( t ) − b i ( t ) ) \Delta L(t)= L(t+1)-L(t)\\=\frac{1}{2}\sum_{i=1}^{N}(Q_i(t+1)^2-Q_i(t)^2)\\\le\frac{1}{2}\sum_{i=1}^{N}((Q_i(t)+a_i(t)-b_i(t))^2-Q_i(t)^2)\\\le\frac{1}{2}\sum_{i=1}^{N}(a_i(t)+b_i(t))^2+\sum_{i=1}^{N}Q_i(t)(a_i(t)-b_i(t)) ΔL(t)=L(t+1)L(t)=21i=1N(Qi(t+1)2Qi(t)2)21i=1N((Qi(t)+ai(t)bi(t))2Qi(t)2)21i=1N(ai(t)+bi(t))2+i=1NQi(t)(ai(t)bi(t))
B ( t ) = 1 2 ∑ i = 1 N ( a i ( t ) + b i ( t ) ) 2 B(t)=\frac{1}{2}\sum_{i=1}^{N}(a_i(t)+b_i(t))^2 B(t)=21i=1N(ai(t)+bi(t))2,则有

在这里插入图片描述
其中:在这里插入图片描述

假设每个队列的到达和服务这两项是有界的,因此存在一个有限常数 B > 0 B>0 B>0,使得对于所有 t t t 和所有可能的队列向量 Q ( t ) Q(t) Q(t) 都成立如下性质:
在这里插入图片描述

取(Eq. 1)的条件期望,得到Lyapunov漂移的条件期望的边界如下:
在这里插入图片描述

A basic Lyapunov drift theorem 一个基本的李雅普诺夫漂移定理

在许多情况下,网络可以被控制,因此每个队列的到达和服务之间的差异对某个实数 ε > 0 \varepsilon>0 ε>0 满足以下的性质:
在这里插入图片描述
如果上式对于所有队列 i i i、所有时隙 t t t 和所有可能的向量 Q ( t ) \displaystyle Q(t) Q(t) 对相同ε成立,则(等式2)简化为以下李亚普诺夫漂移定理中使用的漂移条件。
下面的定理可以看作是马尔可夫链的Foster定理的一个变体。然而,它不需要马尔可夫链结构。


定理(Lyapunov Drift)
假设存在常数 B ≥ 0 , ε > 0 B\ge0,\varepsilon>0 B0,ε>0 使得对于所有的 t t t 和可能的向量 Q ( t ) Q(t) Q(t) ,条件李雅普诺夫漂移满足:

在这里插入图片描述

注等式2.在这里插入图片描述

则对所有的时隙 t > 0 t>0 t>0,网络中的时间平均队列大小满足:
在这里插入图片描述


证明
取漂移不等式两边的期望,利用迭代期望定律,得到:
在这里插入图片描述
将上式对 τ ∈ { 0 , 1 , . . . , t − 1 } \tau∈\{0,1,...,t-1\} τ{0,1,...,t1} 求和,利用可伸缩和定律,得到:
在这里插入图片描述
利用 L ( t ) L(t) L(t) 非负的事实,重新排列上式中的各项,证明了结果。

Lyapunov optimization for queueing networks 排队网络的Lyapunov优化

考虑与上一节相同的排队网络。
现在定义 p ( t ) p(t) p(t) 作为在时隙 t t t 上产生的网络惩罚。
假设目标是稳定排队网络,同时最小化 p ( t ) p(t) p(t) 的时间平均值。

例如,为了稳定网络,同时最小化时间平均功率, p ( t ) p (t) p(t) 可定义为网络在时隙 t t t 上产生的总功率。处理某些理想报酬 r ( t ) r(t) r(t) 的时间平均值最大化的问题,可以定义惩罚 p ( t ) = − r ( t ) p(t)=-r(t) p(t)=r(t)。这对于在保证稳定性的前提下最大化整个网络的效用是很有用的。

在稳定网络的同时最小化惩罚 p ( t ) p(t) p(t) 的平均时间,网络算法可以设计成使控制动作贪婪地最小化下面每个时隙上的漂移加惩罚表达式的边界:
在这里插入图片描述
其中 V V V 是一个非负的权重,可以根据需要选择它来影响性能权衡。这种方法的一个关键特征是,它通常不需要了解随机网络事件(例如随机作业到达或通道实现)的概率。选择 V = 0 V=0 V=0 可简化为最小化每个槽漂移的边界,对于多跳队列网络中的路由,可简化为Tassiulas和Ephremides开发的背压路由算法。

使用 V = 0 V=0 V=0 并定义 p ( t ) p(t) p(t) 为插槽 t t t 上的网络功耗引出了Neely提出的在保证网络稳定性的前提下最小化平均功率的漂移加惩罚算法[8]。
使用 V = 0 V=0 V=0 并使用 p ( t ) p(t) p(t) 作为允许控制效用度量的负值,引出了Neely、Modiano和Li开发的用于联合流量控制和网络路由的漂移加惩罚算法。


在这种情况下,前一节的李雅普诺夫漂移定理的推广是重要的。为了说明简单,假设 p ( t ) p(t) p(t) 有界于下:
在这里插入图片描述
例如,上面满足 p m i n = 0 p_{min}=0 pmin=0 在这种情况下 p ( t ) p(t) p(t) 总是非负的。让 p ∗ p^{*} p 表示 p ( t ) p(t) p(t) 的时间平均值的期望目标。
V V V 是一个参数,用来衡量达到目标的重要性。以下定理表明,如果满足漂移+惩罚条件,则时间平均惩罚最多比期望目标高出O(1/V),而平均队列大小为O(V)。
V V V 参数可以调优,使平均时间惩罚尽可能接近(或低于)所需的目标,并进行相应的队列大小权衡。


定理(Lyapunov Optimization)

假设存在常数 ε > 0 , V , B ≥ 0 \varepsilon>0,V,B\ge0 ε>0,V,B0 以及 p ∗ p^* p 对于所有的 t t t 和所有可能的向量 Q ( t ) Q(t) Q(t) ,以下漂移加惩罚条件成立:
在这里插入图片描述

则对于所有 t > 0 t>0 t>0 ,时间平均惩罚和时间平均队列大小满足:
在这里插入图片描述
在这里插入图片描述


证明
取假定漂移加惩罚的两边的期望并使用迭代期望定律,我们得到:
在这里插入图片描述
在前 t t t 个时隙上求和,并且使用伸缩和定律给出:
在这里插入图片描述
除以 V t {\displaystyle Vt} Vt 并且重新排列项证明了时间平均惩罚边界。一个类似的论证证明了时间平均队列大小边界。

参考资料

https://en.wikipedia.org/wiki/Lyapunov_optimization

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/141922.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

STM32实现PMBus从机程序

最近在野火的STM32F103VET6开发板上实现PMBus从机程序,这个程序参考了以下这篇博客的关于使用中断法实现I2C从机程序:STM32设置为I2C从机模式_iic从机_柒壹漆的博客-CSDN博客 ,实测这个程序是可以正常运行的,感谢博主的分享&#…

MDK工程转换Vscode+EIDE方法

MDK工程转换VscodeEIDE方法 1、VscodeEIDE环境搭建方法 请按下方视频完成环境搭建,并编译成功。下载,单步调试如无视频中芯片可暂不执行。 https://www.bilibili.com/video/BV1Zu4y1f72H/?spm_id_from333.337.search-card.all.click&vd_source73…

Prometheus+Grafana监控K8S集群(基于K8S环境部署)

文章目录 一、环境信息二、部署前准备工作三、部署Prometheus监控系统四、部署Node_exporter组件五、部署Kube_state_metrics组件六、部署Grafana可视化平台七、Grafana可视化显示Prometheus收集数据八、Grafana添加监控模板九、拓展 一、环境信息 1、服务器及K8S版本信息&…

3D科研绘图与学术图表绘制:从入门到精通

💂 个人网站:【工具大全】【游戏大全】【神级源码资源网】🤟 前端学习课程:👉【28个案例趣学前端】【400个JS面试题】💅 寻找学习交流、摸鱼划水的小伙伴,请点击【摸鱼学习交流群】 3D科研绘图和学术图表绘…

面试官问:大量的 TIME_WAIT 状态 TCP 连接,对业务有什么影响?怎么处理?

几个方面: 问题描述:什么现象?什么影响? 问题分析 解决方案 底层原理 1.问题描述 模拟高并发的场景,会出现批量的 TIME_WAIT 的 TCP 连接: 短时间后,所有的 TIME_WAIT 全都消失&#xff0…

git的基本操作

git的基本操作 一般思路: 新建个人分支加粗样式–克隆远程仓库代码—编辑本地分支代码–合入master分支(先切换到master分支)–master分支代码push到远程仓库 1、安装好git之后必须设置用户和邮箱信息之后才能提交代码到缓存区、本地库 git …

(避开网上复制操作)最详细的树莓派刷机配置(含IP固定、更改国内源的避坑操作、SSH网络登录、VNC远程桌面登录)

一、准备工作 SD卡格式化 二、 树莓派系统环境搭建(官方) 官方镜像 1.1、 必备的配件 读卡器, 内存卡(强烈推荐 32GB 内存卡, #lite 命令行界面版本至少需要 8G, 图形化带桌面版镜像需要 16GB&#xf…

气球派对服务小程序商城的效果是什么

气球派对包含多种场景,除了线下服务如生日布置、浪漫小礼、婚礼布置、周岁礼等,还有相关产品销售属性;同时这些服务具备较高的同城场景和定制化需求,在实际生活中,这些服务的需求度较高,但同样需要商家不断…

【C++】手撕string(string的模拟实现)

手撕string目录: 一、 Member functions 1.1 constructor 1.2 Copy constructor(代码重构:传统写法和现代写法) 1.3 operator(代码重构:现代写法超级牛逼) 1.4 destructor 二、Other mem…

在Pyppeteer中实现反爬虫策略和数据保护

爬虫是我们获取互联网数据的神奇工具,但是面对越来越严格的反爬虫措施,我们需要一些我们获取数据的利器来克服这些障碍。本文将带您一起探索如何使用Pyppeteer库来应对这些挑战。 Pyppeteer是一个基于Python的无头浏览器控制库,它提供了与Chr…

MySQL 连接查询(多表查询 二)

基本介绍 作用:连接查询(Join)操作,用于联结多个表以获取更全面和准确的数据 基本分类: 内连接:相当于查询A、B交集部分数据(去掉迪卡尔积无效组合)外连接: 左外连接&…

VmWare16+Ubuntu安装教程

文章目录 前言一、前期软件和系统镜像准备二、VmWare16安装三、Ubuntu安装(1)下载Ubuntu镜像(2)打开VmWare16,点击创建新的虚拟机(3)选择典型,下一步(4)选择刚…

MySQL 内部组件结构以及SQL执行逻辑

目录 一、MySQL的的内部组件结构二、连接器三、查询缓存四、分析器五、优化器六、执行器 一、MySQL的的内部组件结构 Server层 主要包括连接器、查询缓存、分析器、优化器、执行器等,涵盖 MySQL 的大多数核心服务功能,以及所有的内置函数 (如…

【算法思想】贪心

💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学…

Linux基础知识 总结

Linux基础知识 总结 1、Clion的简单介绍 CLion是以IntelliJ为基础,专为开发C及C所设计的跨平台IDE,可以在Windows、Linux及MacOS使用,这里我是在ubuntu 16.0.4基础上安装。2、下载 Linux版Clion的.tar.gz的压缩包 wget https://download.j…

这本书竟然把JAVA讲的如此透彻!漫画JAVA火爆出圈!

亲爱的粉丝们,你是否曾经为学习JAVA而苦恼?繁复的代码和复杂的逻辑常常让人感到头大。不过,今天我要为大家介绍一本神奇的书——《漫画JAVA》,它以图文并茂的方式,轻松诙谐地讲解了JAVA的方方面面。在这篇文章中&#…

【postgresql】ERROR: cannot alter type of a column used by a view or rule

修改字段类型 由varchar 改为int8。 具体sql alter table company alter column city_id type int8 using city_id::int8; 返回错误信息 > ERROR: cannot alter type of a column used by a view or rule DETAIL: rule _RETURN on view search_qy depends on column …

nodejs+vue 医院病历管理系统

系统使用权限分别包括管理员、病人和医生,其中管理员拥有着最大的权限,同时管理员的功能模块也是最多的,管理员可以对系统上所有信息进行管理。用户可以修改个人信息,对医院病历信息进行查询,对住院信息进行添加、修改…

【操作系统笔记十四】科普:POSIX 是什么

注:本文转载自该文章posix是什么都不知道,还好意思说你懂Linux? Linux开发者越来越多,但是仍然有很多人整不明白POSIX是什么。本文就带着大家来了解一下到底什么是POSIX,了解他的历史和重要性。 一、什么是 POSIX&…

RK3568驱动指南|第五期-中断-第44章 共享工作队列实验

瑞芯微RK3568芯片是一款定位中高端的通用型SOC,采用22nm制程工艺,搭载一颗四核Cortex-A55处理器和Mali G52 2EE 图形处理器。RK3568 支持4K 解码和 1080P 编码,支持SATA/PCIE/USB3.0 外围接口。RK3568内置独立NPU,可用于轻量级人工…