1、最优化理论的基础

多情剑客无情剑yu 2024-06-07 原文

以下的内容是关于多元函数知识，也是最优化理论的基础，仅仅是需要《数学分析》的知识。

1、梯度与黑塞矩阵

定义1：设元函数对自变量 $~x=(x_1,x_2,\dots,x_n)^T~$ 各自分量的一阶偏导数为
$\frac{\partial f(x)}{\partial x_i},~~~i=1,2,\dots,n$
那么称向量
$\nabla f(x)=(\frac{\partial f(x)}{\partial x_1},\frac{\partial f(x)}{\partial x_2},\dots,\frac{\partial f(x)}{\partial x_n})^T$
为函数在处的一阶导数或梯度

定义2：设元函数对自变量 $~x=(x_1,x_2,\dots,x_n)^T~$ 各自分量的二阶偏导数为
$\frac{\partial^2 f(x)}{\partial x_i x_j},~~~i,j=1,2,\dots,n$
那么称矩阵
$\nabla^2 f(x)=\begin{pmatrix} \frac{\partial^2 f(x)}{\partial x_1^2 }&\frac{\partial^2 f(x)}{\partial x_1 x_2}&\dots&\frac{\partial^2 f(x)}{\partial x_i x_n}\\ \frac{\partial^2 f(x)}{\partial x_2 x_1}&\frac{\partial^2 f(x)}{\partial x_2^2 }&\dots&\frac{\partial^2 f(x)}{\partial x_2 x_n}\\ \vdots&\vdots&&\vdots\\ \frac{\partial^2 f(x)}{\partial x_n x_1 }&\frac{\partial^2 f(x)}{\partial x_n x_2 }&\cdots&\frac{\partial^2 f(x)}{\partial x_n ^2 } \end{pmatrix}$
为函数在处的二阶导数矩阵或矩阵

定义3：如果梯度的所有分量函数在都连续，则称在连续可微；如果的矩阵的各个分量函数都连续，则在二阶连续可微。

定义4：如果在开集上每一点都连续可微，则称在上一阶连续可微；如果如果在开集上每一点上二阶连续可微，则称在上二阶连续可微

注：(1)、定义4中之所以选择开集，而不是闭集，是因为闭集的边界不可微
(2)、如果在二阶连续可微，则
$\frac{\partial^2 f(x)}{\partial x_i x_j }=\frac{\partial^2 f(x)}{\partial x_j x_x }$
即表明 $~\nabla^2 f(x)~$ 是一个对称矩阵

例1：设 $A\in\mathbb{R}^{nxn}$ , $~b\in\mathbb{R}^n~$ ,求二次函数
$f(x)=\frac{1}{2}x^TAx+b^Tx$
在的梯度和矩阵
解：由于 $\begin{aligned} f(x)&=\frac{1}{2}\sum_{i=1}^{i=n}\sum_{j=1}^{j=n}a_{ij}x_ix_j+\sum_{i=1}^{i=n}b_ix_i\\ \end{aligned}$
则 $~k=1,2,\cdots,n~$ 时
$\begin{aligned} \frac{\partial f(x)}{\partial x_k}&=\frac{1}{2}\sum_{j=1,j\neq k}^{j=n}a_{kj}x_j+\frac{1}{2}\sum_{i=1,i\neq k}^{i=n}a_{ik}x_i+a_{kk}x_k+b_k\\ &=\frac{1}{2}\sum_{j=1}^{j=n}a_{kj}x_j+\frac{1}{2}\sum_{i=1}^{i=n}a_{ik}x_i+b_k \end{aligned}$
故 $~\frac{\partial f(x)}{\partial x}=\frac{1}{2}(A+A^T)x+b~$
和上面的分析类似，我们可以证明 $~\nabla^2f(x)=\frac{1}{2}(A+A^T)~$

2、方向导数

定义5：设 $~f:\mathbb{R}^n\rightarrow\mathbb{R}~$ 在开集上连续可微，对于 $~x\in\mathbb{R}^n,d\in\mathbb{R}^n~$ ,则在点关于方向的方向导数定义为
$\frac{\partial f}{\partial d}(x)=\lim_{\theta\rightarrow0}\frac{f(x+\theta d)-f(x)}{\theta}$
上述定义的方向导数等于 $~\nabla f(x)^Td~$ ,其中 $~\nabla f(x)~$ 表示在处的梯度，为方向.

注：(1)、显然方向导数是偏导数的推广，偏导数刻画的函数沿着特定方向的微商,而方向导数是任意方向的微商
(2)、就是关于这里方向导数的定义，采用的我后面参考的几本书上其中的定义，不过我当时一看觉得有问题，我当时认为方向导数应该这样定义
$\frac{\partial f}{\partial d}(x)=\lim_{\theta\rightarrow0}\frac{f(x+\theta d)-f(x)}{\theta \Vert d\Vert}$
上面的范数我们就取欧式范数，或者原始的定义方向选取的是单位方向。后来在维基百科发现方向导数的定义，它认为两者都可以，仔细一想，才是我狭隘了。如果有人留意此贴，希望大家思考一下。

3、多元函数的泰勒公式

定义6：若在上一阶连续可微，对任何 $~x,x+d\in D~$ 则有
$f(x+d)=f(x)+\nabla f(x)^Td+o(\Vert d\Vert)~~~~~~~麦克劳林余项$
$f(x+d)=f(x)+\nabla f(x+td)^Td,~~t\in(0,1)~~~柯西余项$
$f(x+d)=f(x)+\int_{0}^{1}\nabla f(x+td)^Tddt~~~~积分余项$
定义7：若在上二阶连续可微，对任何 $~x,x+d\in D~$ 则有
$f(x+d)=f(x)+\nabla f(x)^Td+\frac{1}{2}d^T\nabla^2f(x)d+o(\Vert d\Vert^2)~~~~~~~麦克劳林余项$
$f(x+d)=f(x)+\nabla f(x)^Td+\frac{1}{2}d^T\nabla^2f(x+td)d~~t\in(0,1)~~~柯西余项$
$f(x+d)=f(x)+\nabla f(x)^Td+\int_{0}^{1}(1-t)[d^T\nabla^2 f(x+td)d]dt~~~~积分余项$
证明：因为这个不是很显然
我们利用一元函数的泰勒展开证明，令 $~\phi(t)=f(x+td)~$
则 $~\phi'(t)=\nabla f(x+td)^Td~$ , $~\phi''(t)=d^T\nabla ^2f(x+td)d~$ ，由 $~\phi(1)-\phi(0)=\int_{0}^{1}\phi'(t)dt~$ 知
$\begin{aligned} f(x+d)-f(x)&=\int_{0}^{1}[\nabla f(x+td)^Td]dt=-\int_{0}^{1}[\nabla f(x+td)^Td]d(1-t)\\ &=(t-1)\nabla f(x+td)^Td|_0^1+\int_0^1(1-t)d[\nabla f(x+td)^Td]\\ &=\nabla f(x)^Td+\int_0^1(1-t)[d^T\nabla f(x+td)^Td]dt \end{aligned}$

4、两个普通公式的证明

此处是我临时起意加上的，肯定很多书上也找不到，主要的是
定义8：若在 $~开集D~\in\mathbb{R}^n$ 上二阶连续可微，对任何 $~x,x+td\in D~$ 则有
$\frac{d f(x+td)}{d t}=\nabla f(x+td)^Td$
$\frac{d^2 f(x+td)}{d t^2}=d^T\nabla^2 f(x+td)d$
这个公式我们在上面的证明中用到，但是看起来却不是那么显然，我来证明一下：
证明： $\begin{aligned} \frac{d f(x+td)}{d t}&=\frac{df(x_1+td_1,x_2+td_2,\cdots,x_n+td_n)}{dt}\\ &=\frac{\partial f(x+td)}{\partial (x_1+td_1)}d_1+\frac{\partial f(x+td)}{\partial (x_2+td_2)}d_2+\cdots+\frac{\partial f(x+td)}{\partial (x_n+td_n)}d_n\\ &=(\frac{\partial f(x+td)}{\partial (x_1+td_1)},\frac{\partial f(x+td)}{\partial (x_2+td_2)},\cdots,\frac{\partial f(x+td)}{\partial (x_n+td_n)})\begin{pmatrix} d_1\\d_2\\\vdots\\d_n \end{pmatrix}\\ &=(\frac{\partial f(x+td)}{\partial x_1},\frac{\partial f(x+td)}{\partial x_2},\cdots,\frac{\partial f(x+td)}{\partial x_n})\begin{pmatrix} d_1\\d_2\\\vdots\\d_n \end{pmatrix}\\ &=\nabla f(x+td)^Td \end{aligned}$
$\begin{aligned} \frac{d^2 f(x+td)}{d t^2}&=\frac{d^2f(x_1+td_1,x_2+td_2,\cdots,x_n+td_n)}{dt^2}\\ &=\frac{\partial^2 f(x+td)}{\partial^2(x_1+td_1)}d_1^2+\frac{\partial^2 f(x+td)}{\partial (x_1+td_1)\partial (x_2+td_2)}d_1d_2+\cdots+\frac{\partial^2 f(x+td)}{\partial (x_1+td_1)\partial (x_n+td_n)}d_1d_n\\ &+\frac{\partial^2 f(x+td)}{\partial(x_2+td_2)\partial(x_1+td_1)}d_2d_1+\frac{\partial^2f(x+td)}{\partial^2(x_2+td_2)}d_2^2+\cdots+\frac{\partial^2 f(x+td)}{\partial(x_2+td_2)\partial(x_n+td_n)}d_2d_n\\ &~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\vdots\\ &+\frac{\partial^2 f(x+td)}{\partial(x_n+td_n)\partial(x_1+td_1)}d_nd_1+\frac{\partial^2 f(x+td)}{\partial(x_n+td_n)\partial(x_2+td_2)}d_nd_2+\cdots+\frac{\partial^2 f(x+td)}{\partial^2(x_n+td_n)}d_2d_n\\ &=\begin{pmatrix} d_1&d_2&\cdots&d_n \end{pmatrix}\begin{pmatrix} \frac{\partial^2 f(x+td)}{\partial^2x_1}&\frac{\partial^2 f(x+td)}{\partial x_1\partial x_2}\cdots&\frac{\partial^2 f(x+td)}{\partial x_1\partial x_n}\\ \frac{\partial^2 f(x+td)}{\partial x_2\partial x_1}&\frac{\partial^2 f(x+td)}{\partial^2x_2}\cdots&\frac{\partial^2 f(x+td)}{\partial x_2\partial x_n}\\ \vdots&\vdots&\vdots&\\ \frac{\partial^2 f(x+td)}{\partial x_n\partial x_1}&\frac{\partial^2 f(x+td)}{\partial x_n\partial x_2}\cdots&\frac{\partial^2 f(x+td)}{\partial^2x_n} \end{pmatrix}\begin{pmatrix} d_1\\d_2\\\vdots\\d_n \end{pmatrix}\\ &=d^T\nabla^2f(x+td)d \end{aligned}$

此次内容参考书籍：
[1]、倪勤：最优化方法与程序设计
[2]、袁亚湘,孙文瑜：最优化理论与方法

最优化最优 math 5Cpartial Cpartial

有关1、最优化理论的基础的更多相关文章

postman接口测试工具-基础使用教程 - 2
1.postman介绍Postman一款非常流行的API调试工具。其实，开发人员用的更多。因为测试人员做接口测试会有更多选择，例如Jmeter、soapUI等。不过，对于开发过程中去调试接口，Postman确实足够的简单方便，而且功能强大。2.下载安装官网地址:https://www.postman.com/下载完成后双击安装吧，安装过程极其简单，无需任何操作3.使用教程这里以百度为例,工具使用简单，填写URL地址即可发送请求，在下方查看响应结果和响应状态码常用方法都有支持请求方法:getpostputdeleteGet、Post、Put与Delete的作用get：请求方法一般是用于数据查询，
软件测试基础 - 2
Ⅰ软件测试基础一、软件测试基础理论1、软件测试的必要性所有的产品或者服务上线都需要测试2、测试的发展过程3、什么是软件测试找bug，发现缺陷4、测试的定义使用人工或自动的手段来运行或者测试某个系统的过程。目的在于检测它是否满足规定的需求。弄清预期结果和实际结果的差别。5、测试的目的以最小的人力、物力和时间找出软件中潜在的错误和缺陷6、测试的原则28原则：20%的主要功能要重点测（eg：支付宝的支付功能，其他功能都是次要的）80%的错误存在于20%的代码中7、测试标准8、测试的基本要求功能测试性能测试安全性测试兼容性测试易用性测试外观界面测试可靠性测试二、质量模型衡量一个优秀软件的维度①功能性功
ES基础入门 - 2
ES一、简介1、ElasticStackES技术栈：ElasticSearch：存数据+搜索；QL；Kibana：Web可视化平台，分析。LogStash：日志收集，Log4j:产生日志；log.info(xxx)。。。。使用场景：metrics：指标监控…2、基本概念Index（索引）动词：保存（插入）名词：类似MySQL数据库，给数据Type（类型）已废弃，以前类似MySQL的表现在用索引对数据分类Document（文档）真正要保存的一个JSON数据{name:"tcx"}二、入门实战{"name":"DESKTOP-1TSVGKG","cluster_name":"elasticsear
【网络】-- 网络基础 - 2
（本文是网络的宏观的概念铺垫）目录计算机网络背景网络发展认识"协议"网络协议初识协议分层OSI七层模型TCP/IP五层(或四层)模型报头以太网碰撞路由器IP地址和MAC地址IP地址与MAC地址总结IP地址MAC地址计算机网络背景网络发展是最开始先有的计算机，计算机后来因为多项技术的水平升高，逐渐的计算机变的小型化、高效化。后来因为计算机其本身的计算能力比较的快速：独立模式：计算机之间相互独立。如：有三个人，每个人做的不同的事物，但是是需要协作的完成。而这三个人所做的事是需要进行协作的，然而刚开始因为每一台计算机之间都是互相独立的。所以前面的人处理完了就需要将数据
Ruby 缺少常量表达式优化？ - 2
我希望Ruby的解析器会进行这种微不足道的优化，但似乎并没有(谈到YARV实现，Ruby1.9.x、2.0.0):require'benchmark'deffib1a,b=0,1whileb由于这两种方法除了在第二种方法中使用预定义常量而不是常量表达式外是相同的，因此Ruby解释器似乎在每个循环中一次又一次地计算幂常数。是否有一些Material说明为什么Ruby根本不进行这种基本优化或只在某些特定情况下进行？最佳答案很抱歉给出了另一个答案，但我不想删除或编辑我之前的答案，因为它下面有有趣的讨论。正如JörgWMittag所说，
ruby-on-rails - 优化读取数据库和写入csv文件 - 2
我正在尝试从数据库中读取大量单元格(超过100.000个)并将它们写入VPSUbuntu服务器上的csv文件。碰巧服务器没有足够的内存。我正在考虑一次读取5000行并将它们写入文件，然后再读取5000行，等等。我应该如何重构我当前的代码以使内存不会被完全消耗？这是我的代码:defwrite_rows(emails)File.open(file_path,"w+")do|f|f该函数由sidekiqworker调用:write_rows(user.emails)感谢您的帮助! 最佳答案这里的问题是，当您调用emails.each时，
软约束、硬约束、Minimum Snap的轨迹优化方法 - 2
文章目录前言约束硬约束的轨迹优化Corridor-BasedTrajectoryOptimizationBezierCurveOptimizationOtherOptions软约束的轨迹优化Distance-BasedTrajectoryOptimization优化方法前言可以看看我的这几篇Blog1，Blog2，Blog3。上次基于MinimumSnap的轨迹生成，有许多优点，比如：轨迹让机器人可以在某个时间点抵达某个航点。任何一个时刻，都能数学上求出期望的机器人的位置、速度、加速度、导数。MinimumSnap可以把问题转换为凸优化问题。缺点：MnimumSnap可以控制轨迹一定经过中间的
ruby-on-rails - 负载测试期间 Unicorn CPU 使用率激增，优化方法 - 2
我对为我的RubyonRails3.1.3应用优化我的Unicorn设置的方法很感兴趣。我目前正在高CPU超大实例上生成14个工作进程，因为我的应用程序在负载测试期间似乎受CPU限制。在模拟负载测试中，每秒大约20个请求重放请求，我的实例上的所有8个内核都达到峰值，盒子负载飙升至7-8个。每个unicorn实例使用大约56-60%的CPU。我很好奇可以通过哪些方式对其进行优化？我希望能够每秒将更多请求汇集到这种大小的实例上。内存和所有其他I/O一样完全正常。在我的测试过程中，CPU越来越低。最佳答案如果您受CPU限制，您希望使用
美团外卖搜索基于Elasticsearch的优化实践 - 2
美团外卖搜索工程团队在Elasticsearch的优化实践中，基于Location-BasedService（LBS）业务场景对Elasticsearch的查询性能进行优化。该优化基于Run-LengthEncoding（RLE）设计了一款高效的倒排索引结构，使检索耗时（TP99）降低了84%。本文从问题分析、技术选型、优化方案等方面进行阐述，并给出最终灰度验证的结论。1.前言最近十年，Elasticsearch已经成为了最受欢迎的开源检索引擎，其作为离线数仓、近线检索、B端检索的经典基建，已沉淀了大量的实践案例及优化总结。然而在高并发、高可用、大数据量的C端场景，目前可参考的资料并不多。因此
【Elasticsearch基础】Elasticsearch索引、文档以及映射操作详解 - 2
文章目录概念索引相关操作创建索引更新副本查看索引删除索引索引的打开与关闭收缩索引索引别名查询索引别名文档相关操作新建文档查询文档更新文档删除文档映射相关操作查询文档映射创建静态映射创建索引并添加映射概念es中有三个概念要清楚，分别为索引、映射和文档（不用死记硬背，大概有个印象就可以）索引可理解为MySQL数据库；映射可理解为MySQL的表结构；文档可理解为MySQL表中的每行数据静态映射和动态映射上面已经介绍了，映射可理解为MySQL的表结构，在MySQL中，向表中插入数据是需要先创建表结构的；但在es中不必这样，可以直接插入文档，es可以根据插入的文档（数据），动态的创建映射（表结构），这就