第一讲 最优化基础.ppt

最优化理论与方法 张平健 华南理工大学计算机学院 Email: pjzhang@126.com Tel:最优化历史 Fermat, 1638; Newton, 1670 min f(x) Euler, 1775 min f(x, y, …) Lagrange, 1797 min f(x, y, …) s.t. g(x, y, …) = 0 Euler, Langrange-calculus of variations 最优化历史-近现代 1930’s~1940’s：生产运输问题、资源规划问题、Kuhn-Tucker定理 1940’s：线性规划单纯型法 1950’s：动态规划 1950’s：凸分析 1980’s：非光滑分析 1980’s：椭圆算法 最优化的例子 参数优化的例子 运筹学 － 线性规划问题、动态规划问题 数据分析 － 最小二乘方法、参数估计 极值问题 － 湖泊深度、蜂房结构、效用函数 约束优化 － 库存问题、能耗、功耗问题 泛函最优化的方法 等周线问题 － 变分问题 摆线问题 － 最小时间 最少燃料 － 最优控制问题 最优化问题的模型 f(x), gi(x) , hj(x) : Rn?R min f(x) s.t. gi(x) ≤ 0, i = 1,2,…,m hj(x) = 0, j = 1,2,…,l 更一般地，可写为 min f(x), D－可行域（约束域） x∈D 最优化问题的分类 按目标函数与约束函数的性质 线性规划 二次规划 凸规划 非线性规划 按约束形式 无约束问题 等式约束问题 不等式约束问题 混合约束问题 最优化应用 管理 经济 工程技术 人工智能 预备知识 二次型与正定矩阵 多元函数的梯度 多元函数的Hessian矩阵 多元函数的Taylor展开 凸函数及其性质 二次型 f(x1,x2,…xn)= a11x12+a12x1x2+…+a1nx1 xn + a21x1x2+a22x22+…+a2nx2 xn + … an1x1 xn +an2xnx2+…+annxn2 = XTAX,其中X是向量(x1,x2,…xn)T,T代表转置，A是n阶（对称）方阵 （半）正定矩阵 （半）正定矩阵是对称的 （半）正定矩阵的所有特征值都(=)0 （半）正定矩阵可用正交矩阵对角化 梯度 ?f (x)＝(? f /? x1 , ? f /? x2 , … , ? f /? xn )T?Rn 线性函数：f (x) = cTx + b , ?f (x) = c 二次函数：f (x) = (1/2) xTQx + cTx + b, ? f (x) = Qx + c 例：f(x1,x2)= 4x1 - 3x2, ?f (x)＝(4, 3 )T= 梯度计算模块 用外推法计算梯度 Hessian矩阵（二阶偏导数矩阵） ? 2f /?x1 2 ? 2f /?x2 ?x1 … ? 2f /?xn ?x1 ?2f (x)= ? 2f /?x1 ?x2 ? 2f /?x22 … ? 2f /?xn ?x2 … … … … ? 2f /?x1 ?xn ? 2f /?x2 ?xn … ? 2f /?xn2 线性函数：f (x) = cTx + b , ?2f (x) = 0 二次函数：f (x) = 1/2xTQx + cTx + b, ?2f(x)=Q 例： Hessian矩阵计算模块 用外推法计算Hessian矩阵 对角线元素 非对角线元素 多元函数的Taylor展开 设f (x): Rn ? R ，二阶可导。在x* 的邻域内 一阶Taylor展开式： f (x) = f (x*)+ ?f T(x*)(x-x*) + o(‖x-x*‖) 二阶Taylor展开式： f (x) = f (x*)+ ?f T(x*)(x-x*) + (1/2)(x-x*)T ?2f (x*)(x-x*) + o(‖x-x*‖2) 例：求 在x*＝（1,1)T处的二阶Taylor展开式 凸集 设集合 S ? Rn，若?x(1),