黄金分割与优化方法 中科院数学与系统科学研究院 中国科学院大学 袁亚湘 yyx@lsec.cc.ac.cn http://lsec.cc.ac.cn/~yyx 人人网： 袁亚湘 2015.5.30 – 嘉兴学院 2015.11 南京大学

美丽的五角星

毕达哥拉斯 Pythagora (约569BC—500BC)

正五边形 b:a = c:b a = b+ c

欧几里得 (约325BC—265BC) 中末比 （extreme and mean ratio）

黄金分割比例

达.芬奇与黄金分割

Leonardo da Vince (1452-1519)

黄金分割比例 开普勒 （Johannes Kepler） (1571–1630 欧姆 （Martin Ohm ） (1792–1872) goldener Schnitt

黄金分割 法

黄金分割法

华罗庚（1910－1985）

华罗庚在农村推广优选法

华罗庚在大庆油田讲优选法

华罗庚在矿山推广优选法

华罗庚在工厂、车间

Max f(x) [a, b] 上的连续函数 f(x) 是单峰的（只有 一个最大值点）, 求解 max f(x) 任取 a<c<d<b, 如果 f( c ) < f(d) , 则 我们只需在 [c, b] 上求 max f(x) 如何 选取 c , d ?

最优的 c, d 让剩下的区间尽可能短： 即： max[b-c, d-a] 达到最小  c ≈ d = (a+b)/2 !  (两点对分法） 反复利用？

重复利用对分法（4次函数计算） ① ② ③ ④

4个点的另外一种取法 ① ② ② ③ ④

反复利用对分不是最好的！ ① ② ③ ④ ① ② ③ ④

多点综合选取 1） 三个点： 先取 c=1/3 , d=2/3 去掉一截之后 [0, 1/3, 2/3] 在1/3附近再加一点可将剩下区间 去掉一截之后 [0, 1/3, 2/3] 在1/3附近再加一点可将剩下区间 [0, 1/3] 2） 四个点： 去掉一截后成三个点的情形：  c=2/5, d=3/5

菲波那契级数（兔子繁殖问题）

F0=1, F1 =1, Fk+1= Fk + Fk-1 1,1,2,3,5,8,13,21,34,55,89，… …, 一般的 c d c=Fk-1/Fk+1 d=Fk/Fk+1 Fibonacci(1170-1250)

古代运筹例子 田忌赛马 齐威王 田忌 齐威王 田忌 上 A > B A > F 中 C > D C < B 齐威王 田忌 齐威王 田忌 上 A > B A > F 中 C > D C < B 下 E > F E < D 3 : 0 1 : 2

田忌赛马的启示 决策的重要性 大多数问题可以归结于决策问题 决策者总是希望选择对自己最有利的方案 （优化 －－ optimization）

欧拉七桥问题 欧拉时代的 Königsberg Kaliningrad (today)

中国邮递员问题 邮递员送信， 要走遍他负责的所有街道，然后回到邮局。 如何走，总路程最短？ 网络优化： 连通图 G=(V,E) , w(e) 是 边 e 的长度 要求一个圈C , 使得过每条边而且极小化

最短路径问题（旅行商问题） 一个推销员要到若干城市推销产品，然后返回。已知每两个城市之间的距离，如何选择旅行路线，使得每个城市经过一次，而且总的行程最短？ 图 G=(V,E) , w(e) 是 边 e 的长度。找G的一个 Hamilton 圈C , 使得

N 个城市: 路径可能性

最短路径问题（例子）

线性规划:单纯形法 Linear Programming (LP) Problem: min cT x A x = b x ≥ 0

单纯形方法 逐步调整N  得到解 G. Dantzig(1914-2005)

线性规划的另两个奠基者 Leonid Kantorovich John von Neumann (1912-1986) (1903-1957)

小人物  大人物 Hotelling(1885-1973) ： “But we all know the world is nonlinear.” Von Neumann(1903-1957): “Mr. Chairman, Mr Chairman, if the speaker doesn’t mind, I would like to reply for him. The speaker titled his talk `linear programming’ and carefully stated his axioms. If you have an application that satisfies the axioms, well use it. If it does not, then don’t.”

线性规划：内点法 Interior Point Method (Karmarkar, 1984) xk > 0  内点

November 19, 1984

Gibert Strang (1934-） 美国科学院院士 美国工业与应用数学学会前会长 首届ICIAM 苏步青奖获得者

内点法 与 罚函数 min cTx - ∑ log (xi) s.t. A x = b KKT  Newton’s Step s.t. A x = b x >= 0 Log-barrier function: min cTx - ∑ log (xi) s.t. A x = b KKT  Newton’s Step

内点法和平面几何

优化问题 任何存在/需要决策的问题都是优化问题 力学： （最小重量，最大载重，结构最优） 材料科学； （最小能量） 金融： （最大利润，最小风险） 生命科学： （DNA 序列, 蛋白质折叠） 信息科学： （Data Mining, 图像处理） 地学： （反问题 －－ 误差最小） 交通： （最大效益，时刻表，恢复运行）

图像存储问题 尽可能少的存贮，尽可能清晰的图像  求解 A x = b ， x ∈ Rn  求解 A x = b ， x ∈ Rn A ∈ Rm×n , b ∈ Rm . m < < n . 要求： x 尽量多的分量为零! D.L. Donoho (IEE Trans IT, 2006)

简单例子 2 x + y + 2 z = 3 3 x + 3 y + 4 z = 6 无穷多个解： 三个特殊解： 无穷多个解： 三个特殊解： x = y = z = 3/5 x = 1, y = 1, z = 0 x = 0, y = 0, z = 1.5 (最稀疏的解！）

压缩感知 minimize || x || subject to Ax = b 0 范数 (稀疏） || x ||2 极小解一般不稀疏！ 0 范数 (稀疏） || x ||2 极小解一般不稀疏！ （陶哲轩） || . ||1 极小 与 || . ||0 极小 的等价 – Candes, Romberg, Tao(2006)

最小二乘

最小1-范数极小

Netflix 百万美元奖

电影评价

电影打分 观众 电影 生1 师1 生2 师2 师3 生3 小时代3 5 ? 1 疯狂动物城 3 2 荒野猎人 4 ？ 智取威虎山 飘

Netflix 问题 从1998年10月到2005年12月 搜集数据 （请客户给电影打分） 480, 189 用户 17, 770 电影 100,480,507 分数 （1到5） 问题： 如何填补没有打分的数据？

矩阵完整化(Matrix Completion) Aij ( (i, j ) in S ) 求 A 的其他元素 (例子： DVD出租） 数学问题： minimize Rank (X) s.t. Xij = Aij (i.j) in S

“十年前在我和最杰出的几何学家莱布尼茨的通信中，我表明我已经知道确定极大值和极小值的方法、… … ” “十年前在我和最杰出的几何学家莱布尼茨的通信中，我表明我已经知道确定极大值和极小值的方法、… … ” —— 牛顿 Issac Newton (1642-1727)

《一种求极大极小和切线的新方法，它也适用于分式和无理量，以及这种新方法的奇妙类型的计算》 G. Leibniz, “Nova methodus pro maximis et minimis, itemque tangentibus, quae nec fractas nec irrationales quantitates moratur, & singulare pro illi calculi genus”, Acta eruditorum (1684, Leipzig)  《一种求极大极小和切线的新方法，它也适用于分式和无理量，以及这种新方法的奇妙类型的计算》 莱布尼茨认为: “我们的世界是一切可能世界中最好的世界” “ … … , that if there were not the best (optimum) among all possible worlds, God would not have produced any. Gottfried Leibniz(1646-1716)

由于宇宙组成是最完美也是最聪明造物主之产物，宇宙间万物都遵循某种最大或最小准则 ——— 欧拉 Für, da das Gewebe des Universums am vollkommensten und die Arbeit eines klügsten ist Schöpfers, nichts an findet im Universum statt, in dem irgendeine Richtlinie des Maximums oder des Minimums nicht erscheint Leonhard Euler (1707-1783)

祝福大家 优化自己的一生 !

电影打分 学生1 老师1 学生2 老师2 老师3 学生3 星际穿越 ？ 4 2 5 ? 1 小时代3 罗马假日 王牌特工 3 智取威虎山 观众 电影 学生1 老师1 学生2 老师2 老师3 学生3 星际穿越 ？ 4 2 智取威虎山 5 ? 1 小时代3 罗马假日 王牌特工 3