【最优化方法】1-最优化方法介绍

1 最优化起源

中国古代优化思想–田忌赛马(公元前340年)

18世纪L.Euler，J.L.Lagrange等对与力学相关的极值问题或者变分问题统一处理方法的研究。

线性规划与单纯形法—George Dantzig 1947，线性规划之父，师从著名统计学家J. Neyman

一个人的潜能是难以预料的，成功的障碍往往来自于心理上的畏难情绪；一定要相信自己，保持积极的态度。

2 最优化发展

Dantzig，Fulkerson和Johnson在1950年研究旅行商问题时提出了线性整数规划问题。

随后，Gomory提出的割平面方法则奠定了现代整数规划算法的基础。

1951年Kuhn和Tucker提出了约束最优化问题必要条件，后称为Karush-Kuhn-Tucker (KKT)条件，标志着现代非线性规划理论研究的开端。

1970年，Victor Klee & George Minty给出实例证明了单纯形方法不是多项式时间的，而是指数级$O(2^n)$。

3 运筹学在国外

英国称为 Operational Research，美国称为 Operations Research
起源于二战期间的军事问题，如雷达的设置、运输船队的护航舰队的规模、反潜作战中深水炸弹的深度、飞机出击队型、军事物资的存储等。二战后运筹学应用于经济管理领域（LP、计算机）
1948年英国首先成立运筹学会。
1952年美国成立运筹学会。
1952年，Morse 和 Kimball出版《运筹学方法》。
1959年成立国际运筹学联合会。

4 运筹学在国内

1956年成立运筹学小组。（1955年钱学森回国）
1958年提出运输问题的图上作业法。
1962年提出中国邮路问题。
1964年华罗庚推广统筹方法。
1982年加入国际运筹学联合会，并于1999年8月组织了第15届大会。

5 什么是最优化？

根据国际数学优化学会定义，最优化是指在一定约束条件下极大化或极小化某一目标函数的问题，其变量可能是连续或离散或随机的。

通俗解释，在所有可能中挑选最好的。

6 为什么要研究最优化问题？

最优化问题无处不在。

早在18世纪，著名数学家欧拉就曾说：宇宙万物无不与最小化或最大化的原理有关系。

可以说，最优化的原理渗入到社会发展的各个方面，甚至在我们的日常生活里也有各种各样的最优化问题。

经济金融： 最大利润、最小风险。
交通运输： 列车运行图、物流。
信息科学： 数据挖掘、图像处理。
生命科学： DNA 序列、蛋白质折叠。
工程力学： 最大载重、结构最优。
军事国防： 摆兵布阵、后勤保障。

7 最优化问题

向量优化
互补与均衡问题
组合优化
随机优化
半定规划
鲁棒优化
稀疏优化
统计优化
张量与多项式优化
非光滑优化

8 最优化问题分类

CONSTRAINED AND UNCONSTRAINED OPTIMIZATION
GLOBAL AND LOCAL OPTIMIZATION
STOCHASTIC AND DETERMINISTIC OPTIMIZATION
CONTINUOUS VERSUS DISCRETE OPTIMIZATION

9 最优化研究内容

理论

线性规划
非线性规划
一阶/二阶最优性条件
对偶理论
鞍点问题
灵敏度分析
复杂性分析

算法

最速下降方法
共轭梯度方法
牛顿方法
拟牛顿方法
投影方法
罚函数方法

应用

建立模型
理论分析
编程计算
解决实际问题