图解数学:拉格朗日松弛方法的直观理解

昨晚写了拉格朗日松弛方法的原理分析,今天意犹未尽,图解一下,从直观上进一步理解这种方法。

一、一个简单例子

我们先来看一个简单的例子,下面数学规划问题没有约束条件:
min ⁡ f ( x ) = − x 2 + 8 x − 10 \begin{align*}\tag1 \min \quad & f(x) = -x^2 + 8x - 10 \\ \end{align*} minf(x)=x2+8x10(1)
目标函数图像如下:
在这里插入图片描述

在无约束条件下,最大值点在 ( 4 , 6 ) (4,6) (4,6)

下面加上约束条件:

min ⁡ f ( x ) = − x 2 + 8 x − 10 s.t. x − 5 ≥ 0 \begin{align*}\tag2 \min \quad & f(x) = -x^2 + 8x - 10 \\ \text{s.t.} \quad & x -5\ge 0 \end{align*} mins.t.f(x)=x2+8x10x50(2)

这时图像如下:

在这里插入图片描述

最大值点变成了 ( 5 , 5 ) (5,5) (5,5)。显然,在约束条件下,目标函数最大值比无约束条件时变小了。

能否找到一个函数,在无约束条件下的自由极值与数学规划 (2) 相同?这是拉格朗日松弛方法要解决的问题。

二、构造拉格朗日松弛函数

拉格朗日松弛方法的基本思路是,把约束条件作为一个惩罚项与原有目标函数一起构造一个新的无约束目标函数。这个惩罚项的作用是,当约束条件不成立时(即 x > 3 x>3 x>3 时),松弛函数的最大值

1. 松弛函数要达成的目标

拉格朗日松弛函数的目的有两点:

  • 拉格朗日松弛函数的无约束最小值点要满足 x − 5 ≥ 0 x-5\ge0 x50
  • 拉格朗日松弛函数的无约束最小值要与原规划问题 min ⁡ x 2 − 2 x + 1 , s . t . x − 5 ≥ 0 \min\quad x^2-2x+1, \quad s.t. \quad x-5\ge0 minx22x+1,s.t.x50 保持一致。
2. 构造方法

构造下面的拉格朗日松弛函数, λ ≥ 0 \lambda\ge0 λ0 是待定参数:

L ( x , λ ) = f ( x ) + λ ( x − 5 ) (3) \tag3 L(x,\lambda)=f(x)+\lambda(x-5) L(x,λ)=f(x)+λ(x5)(3)
添加的这个松驰项 λ ( x − 5 ) \lambda(x-5) λ(x5) 是单调增函数,它让 f ( x ) f(x) f(x) 最大值点向右方向移动,移动的幅度取决于 λ \lambda λ
λ = 1 \lambda=1 λ=1 时,函数图像变化如下。由于移动幅度偏小,导致 L ( x , λ ) L(x,\lambda) L(x,λ) 的最大值点没有移动到可行解区间,此时的取得的最大值是大于原问题实际最大值 ( 5 , 5 ) (5,5) (5,5) 的。

在这里插入图片描述
λ = 3 \lambda=3 λ=3 时,图像如下:

在这里插入图片描述
此时移动幅度过大,也导致松弛函数的最大值比实际问题的最优解要大。

由此可见,我们只需要用 λ \lambda λ 表示松弛函数的最大值,然后看 λ \lambda λ 取什么值时,松弛函数的最大值去的最小值即可。求解方法如下:

由(2)、(3)可知:

L ( x , λ ) = f ( x ) + λ ( x − 5 ) = − x 2 + 8 x − 10 + λ ( x − 5 ) (4) \tag4 L(x,\lambda)=f(x)+\lambda(x-5)= -x^2 + 8x - 10+\lambda(x-5) L(x,λ)=f(x)+λ(x5)=x2+8x10+λ(x5)(4)

于是,

∂ L ∂ x = − 2 x + 8 + λ \frac{\partial L}{\partial x} =-2x+8+\lambda xL=2x+8+λ

所以,
x = 4 + λ 2 x=4+\frac{\lambda}2 x=4+2λ
时,松弛函数取得最大值。带入(4),最大值为:

max ⁡ ( L ( x , λ ) ) = 1 4 λ 2 − λ + 6 \max(L(x,\lambda)) = \frac14\lambda^2-\lambda+6 max(L(x,λ))=41λ2λ+6

λ = 2 \lambda=2 λ=2
时,松弛函数的最大值取得最小值。此时,
x = 5 , y = 5 x=5,y=5 x=5,y=5

三、最优解不在约束边界上的情形

1、问题

max ⁡ f ( x ) = − x 3 + 3 x + 1 s . t . x ≥ 0 \begin{align*} \max\quad & f(x)=-x^{3}+3x+1\\ s.t. \quad &x \ge 0 \end{align*} maxs.t.f(x)=x3+3x+1x0
图像如下:
在这里插入图片描述

2. 松弛函数

L ( x , λ ) = − x 3 + 3 x + 1 + λ x L(x,\lambda)=-x^{3}+3x+1+\lambda x L(x,λ)=x3+3x+1+λx
λ = 0 , 0.1 , 0.2 , 0.3 , 0.4 \lambda=0,0.1,0.2,0.3,0.4 λ=0,0.1,0.2,0.3,0.4,函数图像变化如下:

在这里插入图片描述
我觉得 λ \lambda λ 无论如何变化,都不可能得到无约束条件的松弛函数。看样子拉格朗日松弛方法还需要继续认真学习!

3. 求解

首先,我们明确原问题是一个带约束的优化问题,即:

max ⁡ f ( x ) = − x 3 + 3 x + 1 s . t . x ≥ 0 \begin{align*} \max \quad & f(x) = -x^3 + 3x + 1 \\ s.t. \quad & x \geq 0 \end{align*} maxs.t.f(x)=x3+3x+1x0

拉格朗日松弛方法通常用于处理约束优化问题,它将约束条件通过拉格朗日乘子加入到目标函数中,从而将有约束优化问题转化为无约束优化问题。

对于这个问题,我们可以定义拉格朗日函数 L ( x , λ ) L(x, \lambda) L(x,λ) 如下:

L ( x , λ ) = f ( x ) − λ g ( x ) = − x 3 + 3 x + 1 − λ ( − x ) L(x, \lambda) = f(x) - \lambda g(x) = -x^3 + 3x + 1 - \lambda (-x) L(x,λ)=f(x)λg(x)=x3+3x+1λ(x)

其中, g ( x ) = − x g(x) = -x g(x)=x 是原问题的约束条件 x ≥ 0 x \geq 0 x0 的不等式形式( x ≥ 0 x \geq 0 x0 等价于 − x ≤ 0 -x \leq 0 x0), λ \lambda λ 是拉格朗日乘子,且 λ ≥ 0 \lambda \geq 0 λ0

现在,我们需要找到 L ( x , λ ) L(x, \lambda) L(x,λ) 的极值点。为此,我们对 L ( x , λ ) L(x, \lambda) L(x,λ) 求偏导,并令其为0:

∂ L ∂ x = d d x ( − x 3 + 3 x + 1 ) − λ d d x ( − x ) = − 3 x 2 + 3 + λ = 0 \frac{\partial L}{\partial x} = \frac{d}{dx}(-x^3 + 3x + 1) - \lambda \frac{d}{dx}(-x) = -3x^2 + 3 + \lambda = 0 xL=dxd(x3+3x+1)λdxd(x)=3x2+3+λ=0

解这个方程,我们得到:

x 2 = λ + 3 3 x^2 = \frac{\lambda + 3}{3} x2=3λ+3

由于 λ ≥ 0 \lambda \geq 0 λ0,我们可以得出 x x x 的可能取值为非负数。

接下来,我们分析拉格朗日乘子的意义。在这个问题中, λ \lambda λ 代表了对约束 x ≥ 0 x \geq 0 x0 的“重视程度”。如果 λ = 0 \lambda = 0 λ=0,则表示约束不起作用,即解在无约束条件下就是最优的。如果 λ > 0 \lambda > 0 λ>0,则表示约束是有效的,且 λ \lambda λ 越大,表示约束越重要。

现在,我们需要检查边界条件和可能的极值点来确定全局最大值。由于原函数 f ( x ) f(x) f(x) 是一个三次函数,且系数为负,因此它是一个倒开口的抛物线,在 x = 1 x = 1 x=1 处有一个极大值点(可以通过求导得出)。同时,我们需要考虑约束条件 x ≥ 0 x \geq 0 x0

  1. x < 0 x < 0 x<0 时,不在可行域内,因此不考虑。
  2. x = 0 x = 0 x=0 时, f ( x ) = 1 f(x) = 1 f(x)=1
  3. x = 1 x = 1 x=1 时(这是无约束情况下的极值点), f ( x ) = 3 f(x) = 3 f(x)=3
  4. x > 1 x > 1 x>1 时,函数值将逐渐减小。

综上所述,全局最大值出现在 x = 1 x = 1 x=1 处,此时 f ( x ) = 3 f(x) = 3 f(x)=3,且满足约束条件 x ≥ 0 x \geq 0 x0。因此,原问题的最优解是 x = 1 x = 1 x=1,最大值为 3。

在这个特定问题中,拉格朗日松弛方法实际上并没有引入新的解,因为原问题的约束条件非常简单( x ≥ 0 x \geq 0 x0),且目标函数在可行域内只有一个极值点。然而,在更复杂的问题中,拉格朗日松弛方法可以帮助我们将约束优化问题转化为无约束优化问题,从而简化求解过程。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

全排列问题

日升时奋斗&#xff0c;日落时自省 目录 1、全排列 2、全排列II 3、子集 4、组合 1、全排列 首先要了解全排列是怎么样的 例如:数组[1,2,3]的全排列&#xff08;全排列就是不同顺序排列方式&#xff09; 例子所有的排列方式如&#xff1a;[1,2,3],[1,3,2],[2,1,3],[2,3…

Leetcode876_链表的中间结点

1.leetcode原题链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 2.题目描述 给你单链表的头结点 head &#xff0c;请你找出并返回链表的中间结点。 如果有两个中间结点&#xff0c;则返回第二个中间结点。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5…

PTA 编程题(C语言)-- 判断素数

题目标题&#xff1a; 判断素数 题目作者 陈越 浙江大学 本题的目标很简单&#xff0c;就是判断一个给定的正整数是否素数。 输入格式&#xff1a; 输入在第一行给出一个正整数N&#xff08;≤ 10&#xff09;&#xff0c;随后N行&#xff0c;每行给出一个小于…

康耐视visionpro-CoglntersectLineLineTool操作说明工具详细说明

◆CogIntersectLineLineTool功能说明&#xff1a; 创建两条线的交点 备注&#xff1a;在“Geometry-Intersection”选项中的所有工具都是创建两个图形的交点工具&#xff0c;其中包括圆与圆的交点、线与圆的交点、线与线的交点、线与圆的交点等&#xff0c;工具使用的方法相似。…

C++ - set 和 map详解

目录 0. 引言 1. 关联式容器 2. 键值对 3. 树形结构 4. set 4.1 set 的定义 4.2 set 的构造 4.3 set 的常用函数 4.4 set 的特点 5. multiset 5.1 multiset 插入冗余数据 5.2 multiset - count 的使用 6. map 6.1 map 的定义 6.2 map 的构造 6.3 map的常…

dcoker+nginx解决前端本地开发跨域

步骤 docker 拉取nginx镜像跑容器 并配置数据卷nginx.conf nginx.conf文件配置 这里展示server server {listen 80;listen [::]:80;server_name localhost;#access_log /var/log/nginx/host.access.log main;location / {# 当我们访问127.0.0.1:8028就会跳转到ht…

软件2班20240415

快速引用类选择器 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdevi…

二进制离散无记忆对称信道

目录 引言 二进制离散无记忆对称信道 引言 在无线通信中&#xff0c;信源与信宿是分开的&#xff0c;两者间的通信环境的复杂度通常会随着距离 的增加而提升。信道是用来连接信源与信宿的媒介。信源与信宿之间的信息传递则需要 借助于信道&#xff0c;因此信道质量的优劣通常…

移动端web适配方案

以下是移动端适配的多个方案&#xff0c;也可以说说你是怎么做的。 正文 自适应&#xff1a;根据不同的设备屏幕大小来自动调整尺寸、大小 响应式&#xff1a;会随着屏幕的实时变动而自动调整&#xff0c;是一种更强的自适应 为什么要做移动端适配&#xff1f; 目前市面上…

【深度剖析】曾经让人无法理解的事件循环,前端学习路线

先自我介绍一下&#xff0c;小编浙江大学毕业&#xff0c;去过华为、字节跳动等大厂&#xff0c;目前阿里P7 深知大多数程序员&#xff0c;想要提升技能&#xff0c;往往是自己摸索成长&#xff0c;但自己不成体系的自学效果低效又漫长&#xff0c;而且极易碰到天花板技术停滞…

Redis入门到通关之ZSet命令

文章目录 ⛄概述⛄常见命令有⛄RedisTemplate API❄️❄️ 向集合中插入元素&#xff0c;并设置分数❄️❄️向集合中插入多个元素,并设置分数❄️❄️按照排名先后(从小到大)打印指定区间内的元素, -1为打印全部❄️❄️获得指定元素的分数❄️❄️返回集合内的成员个数❄️❄…

最优算法100例之49-链表环-计算环的长度

专栏主页:计算机专业基础知识总结(适用于期末复习考研刷题求职面试)系列文章https://blog.csdn.net/seeker1994/category_12585732.html 题目描述 定义两个指针,一个指针走两步,一个指针走一步,第一次相遇时开始计数,第二次相遇时停止计数,最后计数器的值就是环的长度…

STM32H7上实现AD5758驱动

目录 概述 1 下载ADI 5758 Demo 2 AD5758驱动的移植 2.1 使用STM32CubeMX创建工程 2.2 接口函数实现 2.2.1 驱动接口列表 2.2.2 函数实现 2.2.3 修正ad5758驱动 3 AD5758应用程序 3.1 编写测试程序 3.1.1 配置参数结构 3.1.2 配置参数函数 3.1.3 读取参数函数 3.…

【max材质addtive叠加模式特效渲染不出通道的解决办法】

max材质addtive叠加模式特效渲染不出通道的解决办法 2021-12-22 18:15 max的scanline扫描线&#xff0c;vray渲染可以&#xff0c;红移不行(只支持它自己的材质&#xff0c;它自己的材质没有additive模式)。据说mr是可以的。 右侧的球体使用附加不透明度。 附加不透明度通过将…

CentOS:执行make命令时报错g++: Command not found

报错截图&#xff1a; 其实很简单只需要安装一下 yum -y install gcc automake autoconf libtool make yum install gcc gcc-c

​LeetCode解法汇总2924. 找到冠军 II

目录链接&#xff1a; 力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目&#xff1a; https://github.com/September26/java-algorithms 原题链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 一场比赛中共有 n 支队伍&#xff0c;按从…

J垃圾回收

J垃圾回收 1 概述2 方法区的回收3 如何判断对象可以回收3.1 引用计数法3.2 可达性分析法 4 常见的引用对象4.1 软引用4.2 弱引用4.3 虚引用4.4 终结器引用 5 垃圾回收算法5.1 垃圾回收算法的历史和分类5.2 垃圾回收算法的评价标准5.3 标记清除算法5.4 复制算法5.5 标记整理算法…

【深入理解】width 的默认值,2024年最新面试复盘

先自我介绍一下&#xff0c;小编浙江大学毕业&#xff0c;去过华为、字节跳动等大厂&#xff0c;目前阿里P7 深知大多数程序员&#xff0c;想要提升技能&#xff0c;往往是自己摸索成长&#xff0c;但自己不成体系的自学效果低效又漫长&#xff0c;而且极易碰到天花板技术停滞…

如何使用pytorch进行图像分类

如何使用pytorch进行图像分类https://featurize.cn/notebooks/5a36fa40-490e-4664-bf98-aa5ad7b2fc2f

实时传输,弹性优先——物联网通讯打造数据上传新标杆

随着信息技术的飞速发展&#xff0c;物联网技术已经成为连接物理世界和数字世界的桥梁。在物联网领域&#xff0c;数据上传的速度、稳定性和灵活性是评价通讯技术优劣的重要指标。近年来&#xff0c;物联网通讯在实时传输、弹性优先方面取得了显著进展&#xff0c;为数据上传树…