运筹说 第95期 | 非线性规划奠基人——库恩与塔克

经过之前的学习,相信大家已经对运筹学的网络计划的内容有了一定的了解,接下来小编将带你学习新一章——非线性规划的内容,让我们先来了解一下非线性规划的诞生和发展历程,然后共同走近非线性规划领域的代表人物——库恩和塔克,去领略他们精彩的一生。

1、非线性规划的发展起源(标志着非线性规划诞生的历史性事件)

非线性规划是一种优化问题,它的目标函数和约束条件包含非线性的数学表达式。它的发展历史可以追溯到20世纪早期,但其正式诞生可以追溯到1940年代末和1950年代初期的工作。

非线性规划模型

首先,我们先来回顾一下线性规划是如何诞生的,在此基础上再去探究非线性规划的起源。线性规划(Linear Program)的萌芽出现于第二次世界大战前后。1939年前苏联数学家康托洛维奇(Leonid V. Kantorovich)出版了著作《生产组织和计划中的数学方法》,在书中提出了线性规划模型,用来解决下料问题和运输问题,这标志着线性规划的诞生。随着线性规划领域的不断深耕与发展,人们开始意识到线性规划方法的局限性,即它只适用于目标函数和约束条件是线性的问题。

随着这一发现,人们开始寻找解决非线性规划问题的方法。1951年,美国数学家乔治·丹齐克(George Dantzig)在一篇论文中提出了求解线性规划问题的第一个有效方法,称为“单纯形法”。这种方法扩展了求解线性规划问题的思路,并在此基础上得出了可分离规划和二次规划的n种解法。丹齐克提出的单纯形法具有划时代的意义,也为后续各种非线性规划问题的求解方法的提出和发展奠定了基础。同年,哈罗德·库恩 (Harold Kuhn)和阿尔伯特·W·塔克(Albert W. Tucker)发表了一篇关于最优性条件(即库恩塔克条件)的论文,标志着非线性规划的诞生。

2、非线性规划的发展历程(有时间节点的发展阶段描述)

  1. 初期阶段(20世纪早期-1950年代)

在非线性规划问题的发展初期,主要集中在问题的形式化和求解方法的探索上。其中一些重要的事件如下:

  • 1917年,俄国数学家A.D.亚历山德罗夫(A. D. Александров)提出了非线性规划问题,他将非线性规划问题转化为求解最大值或最小值的问题。

  • 1939年,安斯特尼(Hestenes)和斯蒂菲尔(Stiefel)发表了一篇论文,提出了梯度投影法,这是非线性规划中最早的求解方法之一。该方法通过投影操作将约束条件转化为线性形式,从而得到一个可求解的问题。

  • 1951年,乔治·丹齐克(George      Danzick)提出了线性规划的单纯性算法,为优化问题的求解提供了更为高效的方法。

  • 1951年,哈罗德·库恩      (Harold Kuhn)和阿尔伯特·W·塔克(Albert W. Tucker)发表了一篇关于最优性条件(后来称为库恩-塔克条件)的论文,是非线性规划正式诞生的一个重要标志。

  1. 研究进展(1960年代-1970年代)

在这一时期,非线性规划问题的研究进展迅速,主要集中在理论分析和算法的改进上。其中一些重要的事件如下:

  • 1960年代,库恩(Kuhn)和塔克(Tucker)提出了对偶理论,将线性规划的理论扩展到了非线性规划中。他们发现非线性规划的对偶问题可以通过求解原始问题的拉格朗日函数最小化问题来得到,从而得到原始问题的最优解。

  • 1963年,鲍威尔(Powell)提出了逐步优化算法,该算法是目前最有效的非线性规划优化方法之一。该算法通过迭代地求解一系列线性规划子问题来逼近非线性规划问题的最优解。

  • 1978年,洛克菲勒(Rockafellar)发表了《凸分析》,该书成为凸优化的标志性著作。凸优化是非线性规划中一个重要的子领域,该书的出版对凸优化理论和算法的发展做出了重要贡献。

  1. 新的进展(1980年代-1990年代)

在这一时期,随着计算机技术的发展,非线性规划问题的求解能力得到了进一步的提高。其中一些重要的事件如下:

  • 1983年,格瑞万克(Griewank)和科利斯(Corliss)发表了一篇论文,介绍了自适应正则化方法,该方法用于求解非线性规划中的约束问题。该方法通过将罚函数参数调整为自适应值,从而避免了罚函数参数选取不当导致的数值不稳定问题。

  • 1987年,诺赛达尔(Nocedal)和赖特(Wright)发表了《数值优化》,该书成为了现代优化算法的重要参考书。该书涵盖了各种优化算法的理论基础和实现方法,包括非线性规划的优化算法。

  • 1988年,鲍威尔(Powell)发表了一篇论文,提出了新的信赖域算法,该算法通过迭代求解一系列局部二次近似模型来逼近非线性规划问题的最优解。这个算法适用于具有复杂结构和多个局部最优解的问题。

  • 1990年代,人工神经网络和遗传算法等新的算法开始应用于非线性规划问题的求解。这些算法具有一定的鲁棒性和全局搜索能力,可以用于求解具有复杂结构和非凸约束的非线性规划问题。

  1. 现代发展(21世纪)

在21世纪,随着计算机性能的不断提高和优化算法的发展,非线性规划问题的求解能力得到了进一步的提高。其中一些重要的事件如下:

  • 2001年,诺赛达尔(Nocedal)和赖特(Wright)合著了《数值优化》,该书第二版更新了现代优化算法的理论和应用,涵盖了更多的数值算法和计算实例。

  • 2006年,鲍伊德(Boyd)和范登贝格(Vandenberghe)合著了《凸优化》,该书介绍了凸优化的理论和算法,并将其应用于机器学习和信号处理等领域。

  • 2014年,有关学者提出了一种新的非线性规划算法,称为两阶段方法。该方法通过将非线性规划问题转化为两个子问题,一个是最优性子问题,一个是可行性子问题,从而在不需要求解KKT条件()的情况下得到非线性规划问题的最优解。

  • 2020年,Google发表了一篇论文,介绍了他们开发的一个基于机器学习的非线性规划求解器。该求解器使用神经网络对非线性规化问题进行建模和求解,通过学习已有问题实例的解决方法,从而更快速、准确地求解新问题。

注:KKT最优化条件是卡罗需(Karush)以及库恩(Kuhn)和塔克(Tucker)先后独立发表出来的,但在库恩(Kuhn)和塔克(Tucker)发表之后才逐渐受到重视,因此多数情况下记载成库恩-塔克条件(Kuhn-Tucker conditions)。

        KKT(Karush-Kuhn-Tucker)条件,是非线性规划领域里最重要的理论成果之一,是确定某点为极值点的必要条件。对于凸规划,KKT点就是优化极值点(充分必要条件)。

3、非线性规划领域的风云人物(库恩和塔克的生平介绍)

简单了解过非线性规划的起源和发展历程后,想必各位读者朋友对上文提到的对非线性规划的诞生与发展作出重大贡献的两位著名科学家——库恩和塔克感到十分好奇,下面小编将带着大家一起去了解一下库恩和塔克。

库恩:

基本介绍

哈罗德·W·库恩(Harold W. Kuhn),1925年7月29日-2014年7月2日)是美国著名数学家,主要研究领域是优化理论、博弈论和组合数学等方面。

生平纪事

哈罗德·库恩 (Harold Kuhn) 于1925年出生于加利福尼亚州圣莫尼卡。尽管1944年至1946年在美国陆军服役,但他仍于1947年从加州理工学院毕业,之后他进入普林斯顿大学攻读数学研究生。于1948年获得硕士学位,然后获得博士学位。毕业后,他在普林斯顿大学任教并继续从事数学研究,直到1959年转到普林斯顿高等研究院。他在普林斯顿高等研究院工作了大约30年,并在此期间成为数学、经济学和计算机科学领域的重要人物。

塔克:

基本介绍

阿尔伯特·W·塔克(Albert W. Tucker)(1905年11月28日—1995年1月25日)是一位美国著名的数学家、运筹学家和经济学家。他是20世纪50年代最杰出的运筹学家之一,被誉为“运筹学之父”。

阿尔伯特·W·塔克(Albert W. Tucker)


生平纪事

阿尔伯特·塔克(Albert William Tucker),加拿大人,1905年出生于加拿大,1928年获得多伦多大学学士,1932年获得普林斯顿大学博士,博士导师是所罗门·莱夫谢茨。1932-33年他在哈佛大学和芝加哥大学做研究,1933年他开始长期在普林斯顿大学数学系任教,1974年退休,1995年去世。他担任普林斯顿大学数学系的系主任长达20年。1961-62年他担任美国数学协会(MAA)主席。在晚年,他继续从事运筹学和组合优化等领域的研究,并且与其他著名的数学家,如约翰·冯·诺伊曼(John von Neumann)和乔治·达内(George Dantzig)合作。阿尔伯特·W·塔克于1995年去世,享年80岁。他留下了许多具有重要意义的数学贡献和著作,对运筹学和组合优化领域产生了深远的影响。

库恩与塔克

说起库恩与塔克的关系,就不得不提到一个关键人物——约翰·冯·诺伊曼(John von Neumann),两人都是约翰·冯·诺伊曼的学生,也就是师兄弟。有趣的是,美国著名数学家、经济学家、《美丽心灵》男主角原型约翰·福布斯·纳什(John Forbes Nash)是库恩一生的朋友和同事,而塔克又是纳什在普林斯顿大学的研究生论文导师。库恩与塔克师出同门,两人虽相差20岁,却痴迷于相同的研究领域,他们受到老师约翰·冯·诺伊曼的影响,将博弈论和优化理论相结合,开创了博弈论在经济学和管理学等领域的应用。在非线性规划领域,也提出了具有划时代意义的KKT条件,标志着非线性规划的正式诞生。库恩与塔克在自己的专业领域不断深耕,学术成果在相关领域影响深远,两人也一起获得了1980年约翰·冯·诺依曼理论奖,名垂青史。

库恩与纳什(左一为库恩)

结语:作为每一章的第一篇推文,引出下面的推文内容。

看到这里,大家是不是对非线性规划的诞生和发展过程以及做出突出贡献的名家有了更深入的了解呢?下面就让我们继续探索非线性规划世界的其他内容吧!

作者 | 葛彦泽  张巧英

责编 | 陈梦

审核 | 徐小峰

YUNCHOUSHUO!

·知乎|运筹说·

·bilibili|运筹说·

·CSDN|运筹说·

·抖音|运筹说·

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

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

相关文章

深度学习记录--归—化输入特征

归化 归化输入(normalizing inputs),对特征值进行一定的处理,可以加速神经网络训练速度 步骤 零均值化 通过x值更新让均值稳定在零附近,即为零均值化 归化方差 适当减小变量方差 解释 归化可以让原本狭长的数据图像变得规整,梯度下降的…

WSL2 git clone命令无法克隆远程仓库

问题描述 最近在往WSL2里拉取git仓库的时候,突然出现了这个问题,WSL2无法连接到git服务器,导致代码无法拉取下来,可能是因为我最近不小心修改了windows的防火墙设置,导致出现了这个问题。 解决办法 在查阅了很多篇…

在uni-app中使用sku插件,实现商品详情页规格展示和交互。

商品详情 - SKU 模块 学会使用插件市场,下载并使用 SKU 组件,实现商品详情页规格展示和交互。 存货单位(SKU) SKU 概念 存货单位(Stock Keeping Unit),库存管理的最小可用单元,通…

uniapp踩坑之项目:canvas第一次保存是空白图片

在ctx.draw()回调生成图片,参考canvasToTempFilePath接口文档 // data imgFilePath: null,// 缓存二维码图片canvas路径//js // 首先在draw()里进行本地存储 ...... ctx.draw(false, () >{uni.canvasToTempFilePath({ // 把画布转化成临时…

群晖Drive搭建云同步服务器结合内网穿透实现Obsidian笔记文件远程多端同步

文章目录 一、简介软件特色演示: 二、使用免费群晖虚拟机搭建群晖Synology Drive服务,实现局域网同步1 安装并设置Synology Drive套件2 局域网内同步文件测试 三、内网穿透群晖Synology Drive,实现异地多端同步Windows 安装 Cpolar步骤&#…

flutter 五点一:MaterialApp Theme

ThemeData factory ThemeData({bool? applyElevationOverlayColor, //material2的darkTheme下 增加一个半透明遮罩 来凸显阴影效果 material3下无效 貌似没啥用NoDefaultCupertinoThemeData? cupertinoOverrideTheme, //ios组件样式 Iterable<ThemeExtension<dyn…

计算机网络——运输层(1)暨小程送书

计算机网络——运输层&#xff08;1&#xff09;暨小程送书 小程一言专栏链接: [link](http://t.csdnimg.cn/ZUTXU) 运输层概述两个主要协议运输层和网络层的关系网络层运输层总结 多路复用与多路分解多路复用多路分解不同的技术实现时分复用&#xff08;TDM&#xff09;频分复…

Proxmox VE 8安装OpenSuse和部署JumpServer

作者&#xff1a;田逸&#xff08;formyz&#xff09; 跳板服务器Jumpserver部署起来非常容易&#xff0c;但由于其组件多&#xff0c;组件之间关联复杂&#xff0c;一旦出现故障&#xff0c;恢复起来就比较费事。为了解决这个麻烦&#xff0c;本人通常是将Jumpserver部署到Pro…

5. UE5 RPG使用GAS技能系统

之前也介绍过GAS的使用&#xff1a; UE 5 GAS Gameplay Ability System UE 5 GAS 在项目中处理AttributeSet相关 UE 5 GAS 在项目中通过数据初始化 基础的讲解这里不再诉说&#xff0c;有兴趣的可以翻我之前的博客。 接下来&#xff0c;在RPG游戏中实现GAS系统的使用。 GAS系统…

笔记本电脑如何连接显示屏?

目录 1.按下快捷键 winP,选择扩展 2.连接显示器&#xff0c;连好接线 3.笔记本驱动有问题&#xff0c;显示错误如下&#xff1a; 4.驱动已经下载完成&#xff0c; 按下快捷键&#xff0c;还是显示第3步中的错误 5.驱动已经下载完成&#xff0c; 按下快捷键&#xff0c;参照…

Redis:原理速成+项目实战——Redis实战13(GEO实现附近商铺、滚动分页查询)

&#x1f468;‍&#x1f393;作者简介&#xff1a;一位大四、研0学生&#xff0c;正在努力准备大四暑假的实习 &#x1f30c;上期文章&#xff1a;Redis&#xff1a;原理速成项目实战——Redis实战12&#xff08;好友关注、Feed流&#xff08;关注推送&#xff09;、滚动分页查…

拼多多无货源中转仓项目真的靠谱吗?发展前景如何?

阿阳最近一直在关注无货源电商这一块&#xff0c;尤其是拼多多无货源中转仓&#xff0c; 现如今也有了自己的运营团队和交付团队&#xff0c;整体来看这个项目还算不错&#xff01; 说实话&#xff0c;在考察这个项目的时候&#xff0c;看到市面上很多人在做&#xff0c;包括我…

JAVA基础-----认识异常

文章目录 1. 异常的概念与体系结构1.1 异常的概念1.2 异常的体系结构1.3 异常的分类 2. 异常的处理2.1 防御式编程2.2 异常的抛出2.3 异常的捕获2.3.1 异常声明throws2.3.2 try-catch捕获并处理2.3.3 finally 2.4 异常的处理流程 3. 自定义异常类 1. 异常的概念与体系结构 1.1…

C/C++ 基本数据类型的范围

一、常见的数据类型及其范围 数据类型Size(64位)范围int4Byteunsigned int4Bytelong4Byteunsigned long4Bytelong long8Byteunsigned long long8Byte 查询Size代码&#xff1a;sizeof(类型) 查询范围代码&#xff1a;numeric_limits<类型>::max和numeric_limits<类…

使用 mybatis-plus 的mybaits的一对多时, total和record的不匹配问题

应该是框架的问题&#xff0c;去官方仓库提了个issues&#xff0c;等回复 https://github.com/baomidou/mybatis-plus/issues/5923 回复来了&#xff1a; 背景 发现 record是两条&#xff0c;但是total显示3 使用resultMap一对多时&#xff0c;三条数据会变成两条&#xff0…

redis原理(四)redis命令

目录 一、字符串命令&#xff1a; 二、列表命令&#xff1a; 三、集合命令&#xff1a; 四、散列命令&#xff1a; 五、有序集合命令&#xff1a; 六、redis发布与订阅命令&#xff1a; 七、事务命令 八、其他命令 1、排序&#xff1a;SORT 2、键的过期时间&#xff…

代码随想录算法训练营Day23 | 455.分发饼干、376.摆动子序列、53.最大子数组和

LeetCode 455 分发饼干 本题思路&#xff1a;分发饼干的时候&#xff0c;外层循环是胃口&#xff0c;内层是饼干&#xff0c;按照大饼干满足大胃口的思维来投递饼干。 需要将 两个数组&#xff0c;一开始就进行排序处理。 class Solution {public int findContentChildren(int…

java转义字符

//转义字符的使用 public class ChangeChar{//编写一个main方法public static void main(String[] args){// \t :一个制表位&#xff0c;实现对齐的功能System.out.println("北京\t天津\t上海");// \n :换行符&#xff0c;实现换行System.out.println("jack\nsm…

SSH隧道技术

SSH隧道 简介 SSH隧道是一种通过SSH协议在两个网络节点之间建立安全通信的技术。它可以用于多种用途&#xff0c;包括加密和保护敏感数据传输、绕过防火墙限制、远程访问内部服务等。 应用&#xff1a; 端口转发&#xff1a;SSH隧道可以将本地端口转发到远程主机上&#xf…

Python学习从0到1 day5 python基础语法3 数据类型及数据类型转换

一切都会好的&#xff0c;我一直相信 ——24.1.17 一、数据类型 1.数据是有类型的 目前主要接触如下三类数据类型&#xff1a; 2.type()语句 我们可以通过type()语句来得到数据的类型 语法&#xff1a;type(被查看类型的数据) a 10 type(a) print(type(a)) print(type(11…