《经济数学基础》课程教学资源：实验7 无约束优化

优化模型和算法的重要意义 大学数学实验 最优化:在一定条件下,寻求使目标最大(小)的决策 Experiments in Mathematics 最优化是工程技术、经济管理、科学研究、社 会生活中经常到的问题如 结构设计资源分配生产计划运输方案 实验7无约束优化 解决优化问题的手 清华大驰数科系 ·经验积腻,主观判断 作试验,比优劣 ·建立数学模型,求解最优策略 (最优化理论是运筹学的重要内容 优化问题的数学模型 适筹学(OR: Operations/Operational Resea minz=f(x),x∈∈R MS管理科学(MS: Management Science 决策变量,∫~目标函数,Ω~可行域 Ds决策科学(DS: Decision Science ==f(x) 优化( Optimization),规划( Programming) st.g1(x)≤0,i=1,2,…m(2) 无 约 多日 可行解(只满足(2)与最优解(满足(1)(2) 束规 无约束优化(只有(1))与约束优化(1)(2) 实际问题一般总有约束,何时可用无约束优化处理? 学学实 无约束优化的主要内容 实例1产销量安排 1.优化问题的最优解条件;算法模式 某厂生产两个岸号的同一种产品,如何确定产量使利润最大 2.无约束优化的基本方法: 牌号产量成本价格 假设A产销平衡 梯度法,牛顿法,拟牛顿法 3.非线性最小二乘法 假设Bp随x(两种牌号增加而减小,呈线性关系 4优化工具箱的使用 1=b-a1x1-a12x2,b2a12a12>0,a1>a12 5.实际问题中的无约束优化模型 P2=b2-a2x1-a2x2,b2a21,a2>0,a2>a21

1 大学数学实验 Experiments in Mathematics 实验7 无约束优化 清华大学数学科学系 最优化是工程技术、经济管理、科学研究、社 会生活中经常遇到的问题, 如: 优化模型和算法的重要意义 结构设计 资源分配 生产计划 运输方案 解决优化问题的手段 • 经验积累，主观判断 • 作试验，比优劣 • 建立数学模型，求解最优策略 最优化: 在一定条件下，寻求使目标最大(小)的决策 运筹学(OR: Operations/Operational Research) 管理科学(MS: Management Science) 决策科学 (DS: Decision Science) (最)优化理论是运筹学的重要内容 无 约 束 优 化 OR/ MS/ DS 优化(Optimization), 规划(Programming) 线 性 规 划 非 线 性 规 划 网 络 优 化 组 合 优 化 整 数 规 划 不 确 定 规 划 多 目 标 规 划 目 标 规 划 动 态 规 划 优化问题的数学模型 x ~ 决策变量，f ~目标函数，Ω ~ 可行域 n x min z = f (x), x∈Ω⊆ R • 可行解（只满足(2)）与最优解（满足(1),(2)） • 无约束优化（只有(1)）与约束优化（(1),(2)） . . ( ) 0, 1,2, (2) min ( ) (1) s t g x i m z f x i x ≤ = L = • 实际问题一般总有约束，何时可用无约束优化处理？ 4. 优化工具箱的使用 2. 无约束优化的基本方法： 梯度法，牛顿法，拟牛顿法 1. 优化问题的最优解条件；算法模式 无约束优化的主要内容 3. 非线性最小二乘法 5. 实际问题中的无约束优化模型 实例1 产销量安排 牌号 产量 成本 价格 甲 x1 q1 p1 乙 x2 q2 p2 假设A 产销平衡 假设B p随x (两种牌号)增加而减小，呈线性关系 1 1 11 1 12 2 1 11 12 11 12 p = b − a x − a x , b ,a ,a > 0, a > a 某厂生产两个牌号的同一种产品，如何确定产量使利润最大 2 2 21 1 22 2 2 21 22 22 21 p = b − a x − a x , b ,a ,a > 0, a > a

学学实纷 实例1产销量安排 实例2飞机精确定位问题 1612°(0.8 北 假设Cq随x(本牌号增加而减小,呈负指数关系 DME q1=re-x+c1,r,41,c1>0 864.3020) 目标利涧最大 max =(x1, x2)=(P1-q1)x1+(P2-q2)x2 飞机与监控台(图中坐标和测量距离的单位是“公里” 飞机精确定位模型 飞机精确定位模型 已知数据:设备位置坐标分别为(x,y),=1,,4 考虑误差因素 误差非均匀分布 记测量角度为O,角度误差为σ,=1,3 6-a1≤atan2(x-x,y-y)≤61+ 记测量距离为d,距离误差为G4 d.-01≤√x-x)+(-y2≤a,F,非线性规划 要求计算:飞机位置坐标(x,y Min x: Min y, Max x; Max y 不考虑误差因素 量纲不符1 atan2(x-x,y-y)=8 有人也可能会采用其他目标,如 超定方程组 以距离为约東,优化角度误差之和(或平方和); 非线性最小二乘1 或以角度为约束,优化距高误差 (x-x1)2+(y-y2)2 仅部分考虑误差 角度与距高的“地位”不应不同! (学学奖 大学学实) 飞机精确定位模型 无约束优化:最优解的分类和条件 误差一般服从什么分布?不同的量纲如何处理? 正态分布! 归一化处理! 给定一个函数f(x),寻找x*使得∫(x)最小,即 无约束非线性最小二乘模型 Mmf(x)其中x=(x1,x2,…,xn)∈9 atan2(x-x,y-y)-e,d2-Vx-x4)2+(-y4) 局部最优解|八x)^X 全局最优解 角度需要进行预处理 几 如利用atan2函数,值域(-pi,pil 必要条件V(x)=(f1…,,)=0 充分条件Vf(x')=0,V2f(x)>0V2f Hessian阵

2 1 2 1 1 1 2 2 2 , max ( , ) ( ) ( ) 1 2 z x x p q x p q x x x = − + − 目标 利润最大 , , , 0 , , , 0 2 2 2 2 2 2 1 1 1 1 1 1 2 2 1 1 = + > = + > − − q r e c r c q r e c r c x x λ λ λ λ 假设C q随x (本牌号)增加而减小，呈负指数关系 实例1 产销量安排 0 y x VOR2 x=629, y=375 309.00 (1.30) 864.3(2.0) 飞机 x=?, y=? VOR1 x=764, y=1393 161.20 (0.80) VOR3 x=1571, y=259 45.10 (0.60) 北 DME x=155, y=987 飞机与监控台（图中坐标和测量距离的单位是“公里”） 实例2 飞机精确定位问题 飞机精确定位模型 4 2 4 2 4 ( ) ( ) atan2( , ) x x y y d x x y y i i i − + − = − − = θ 不考虑误差因素 超定方程组， 非线性最小二乘！ 要求计算：飞机位置坐标（ ） 记测量距离为 ，距离误差为 记测量角度为 ，角度误差为 已知数据：设备位置坐标分别为 x y d i x y i i i i i , . , 1,...,3; ( , ), 1,...4; 4 σ 4 θ σ = = 量纲不符！ ？ 2 4 2 4 2 4 3 1 2 atan2( , ) ( ) ( ) ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − + − + ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − − ∑= d x x y y x x y y Min i i i i x,y θ 飞机精确定位模型 4 4 2 4 2 4 4 4 ( ) ( ) atan2( , ) σ σ θ σ θ σ − ≤ − + − ≤ + − ≤ − − ≤ + d x x y y d x x y y i i i i i i 考虑误差因素 Min x; Min y; Max x; Max y. 以距离为约束，优化角度误差之和（或平方和）； 或以角度为约束，优化距离误差. 非线性规划 误差非均匀分布！ ？ ？ 仅部分考虑误差! 角度与距离的“地位”不应不同！ 有人也可能会采用其他目标，如： 飞机精确定位模型 2 4 2 4 2 4 4 2 3 1 atan2( , ) ( ) ( ) ( , ) ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − − + − + ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − − − = ∑= σ σ x x y y θ d x x y y Min E x y i i i i i 误差一般服从什么分布？ 正态分布！ 不同的量纲如何处理？ 无约束非线性最小二乘模型 归一化处理！ 角度需要进行预处理， 如利用atan2函数, 值域(-pi, pi) 无约束优化:最优解的分类和条件 Min f (x) x 给定一个函数 f(x),寻找 x* 使得 f(x*)最小，即 T n n 其中 x = ( x1 , x 2 ,L , x ) ∈ ℜ 局部最优解 全局最优解 必要条件 ( ) ( , , ) 0 1 * ∇ = = T x xn f x f L f x * f(x) xl xgo 充分条件 ( ) 0, ( ) 0 * 2 * ∇f x = ∇ f x > Hessian阵 n n i j x x f f × ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ∂ ∂ ∂ ∇ = 2 2

求解无约束优化的基本思路 搜索方向的选择 1最速下降法 暂不考虑搜索步 基本思想在中某一点,确定一个搜索方向 梯度法) 长,可设a=1 及沿该方向的移动步长,得到使目标函数下降的新的点 将∫(x-)在x*点作泰勒展开,只保留一阶项, 选代 Step 1初始化:初始点,终止准则等 步辈 f(x)=f(x+d)=f(x)+Vf(r)d Step2选代改进:方向dk,步长ak 下降方向 vf(x)d<o dk f(x)<f(r) 最速下降方向 f(x2)(负梯度方向) Step3终止检验:得到近优解或k+1=k转2 选代改进格式 x-vf(x) 选择daxk使∫下降更快→不同算法 算法特点初始阶投改进较快,最优解附近改进较慢 2 Newton方法 3拟 Newton方法 将八x+)在x点作泰勒展开至二阶项,用d替代d 目的不计算 Hessian阵,克服病态、不正定、计 f(x )=f(x+d)=f(x)+Vf(x )d+od'V f(x )d 算复杂等缺陷,同时保持收做较快的优点 求d使(+)极小右端对导数为0=4)+= 思路回顾解方程组F(x)=0的拟牛顿法 牛顿方程Vf(x2)d=-Vf(x2) x+=x2F(xF(2)口x+1=x4-()-F(x 牛顿方向d=-(Vf(x2)vf(x2) 使满足4(xk-x4-)=F(xk)-F(x4- 迭代格式x=x2-(Vf(x2))Vf(x) 用迭代方法A4=Ak-1+△4-1计算A 特点局部2阶收斂;需计算 Hessian阵它可能病态或不正定 比较解F(x)=0x+=x2-{F(x)Fx 优化问题Mmf(x)v(x)相当F(x) F(x)o Vf(x) V2f(x)相当F(xV2不一定正定,构造正定阵G代替ⅴf (学学奖 3拟 Newton方法(续) 3拟 Newton方法(续) 设在第k步,G已得到,=()y1,可计算 31 Davidon- Fletcher-Powell(DFP)公式 k+lk uk HA(NH 记△xk AG=+ (Ar)GAr A"( )-(Ar)G+GAr(4") (△x2) △x2)4y Ax)'A 按照拟牛顿条件 3.2 Broyden- Fletcher- Goldfarb-Shanno(BFGS公式 构造迭代公式Gk+1=Gk+AGk或Hk+1=Hk+MH Mk(4)aAxk(△x)Gk 于是有x+2=x2-H*"vf(x+) THA Ar( M=0+ (Ar)A7△rys

3 求解无约束优化的基本思路 基本思想 在 n ℜ 中某一点，确定一个搜索方向 及沿该方向的移动步长，得到使目标函数下降的新的点 迭代 步骤 Step 1 初始化：初始点x0，终止准则等 Step 2 迭代改进：方向d k，步长α k ( ) ( ) k 1 k f x < f x k k k k + x = x + α d +1 Step 3 终止检验：得到近优解或k+1⇒k转2 选择d k ,α k 使 f 下降更快 ⇒ 不同算法 搜索方向的选择 1 最速下降法 （梯度法） 下 降方向 最速下降方向 迭代改进格式 算法特点 初始阶段改进较快，最优解附近改进较慢 k k k k T k k f (x ) f (x d ) f (x ) f (x )d 1 = + = + ∇ + ∇ ( ) < 0 T k k f x d ( ) k k d = −∇f x ( ) k 1 k k x = x − ∇f x + 将 ( ) k +1 f x 在 k x 点作泰勒展开，只保留一阶项，有 暂不考虑搜索步 长，可设αk=1 (负梯度方向) 2 Newton方法 特点 局部2阶收敛;需计算Hessian阵,它可能病态或不正定 将f(xk+1)在xk点作泰勒展开至二阶项，用d替代dk 牛顿方程 牛顿方向 迭代格式 ( ) ( ) 2 k k ∇ f x d = −∇f x f x f x d f x f x d d f x d k k k T k T k ( ) 2 1 ( ) ( ) ( ) ( ) 1 2 = + = + ∇ + ∇ + ( ( )) ( ) k 2 k 1 k d = − ∇ f x ∇f x − ( ( )) ( ) k 1 k 2 k 1 k x = x − ∇ f x ∇f x + − [ ( )] ( ) k 1 k k 1 k x x F x F x + − 比较 = − ′ 的牛顿法 解F ( x) = 0 F ( x) ⇔ ∇f ( x) 求d使f(xk+1)极小⇒右端对d导数为0 ( ) ( ) 0 2 ⇒∇f x +∇ f x d = k k 3 拟Newton方法 目的 不计算Hessian阵，克服病态、不正定、计 算复杂等缺陷，同时保持收敛较快的优点 回顾解方程组 F(x)=0的拟牛顿法 ( ) ( ) ( ) −1 −1 − = − k k k k k k 使A 满足 A x x F x F x k k k k 用迭代方法A A A 计算A −1 −1 = + ∆ 思路 [ ( )] ( ) k 1 k k 1 k x x F x F x + − = − ′ ( ) ( ) k 1 k k 1 k x x A F x + − = − Min f (x) 优化问题 x ∇f ( x)相当 F ( x) f x F x f G f 2 2 2 ∇ ( )相当 ′( ), ∇ 不一定正定，构造正定阵 代替∇ 3 拟Newton方法(续) k k k k k k G = G + ∆G H = H + ∆H 构造 迭代公式 +1 或 +1 按照拟牛顿条件： k k k k k k G ∆x = ∆f ∆x = H ∆f +1 或 +1 , ( ) ( ) k k 1 k k k 1 k ∆x = x − x ∆f = ∇f x − ∇f x 记 + + ( ) k 1 k k k x = x − H ∇f x + 设在第k步, Gk已得到, Hk=(Gk)-1,可计算 ( ) +2 +1 +1 +1 = − ∇ k k k k 于是有 x x H f x 3.1 Davidon-Fletcher-Powell(DFP)公式 k T k k k k k T k k T k k k T k f H f H f f H x f x x H ∆ ∆ ∆ ∆ − ∆ ∆ ∆ ∆ ∆ = ( ) ( ) ( ) ( ) 3 拟Newton方法(续) k T k k k T k k k k T k T k k k T k T k k T k k k x f f x G G x f x f f f x f x G x G ∆ ∆ ∆ ∆ + ∆ ∆ − ∆ ∆ ∆ ∆ ∆ ∆ ∆ ∆ ∆ = + ( ) ( ) ( ) ( ) ( ) ) ( ) ( ) (1 3.2 Broyden-Fletcher-Goldfarb-Shanno(BFGS)公式 k T k k k k k T k k T k k k T k x G x G x x G f x f f G ∆ ∆ ∆ ∆ − ∆ ∆ ∆ ∆ ∆ = ( ) ( ) ( ) ( ) k T k k k T k k k k T k T k k k T k T k k T k k k x f x f H H f x x f x x x f f H f H ∆ ∆ ∆ ∆ + ∆ ∆ − ∆ ∆ ∆ ∆ ∆ ∆ ∆ ∆ ∆ = + ( ) ( ) ( ) ( ) ( ) ) ( ) ( ) (1

搜索步长的确定 非线性最小二乘 Least square)拟合 线性索( Line search)确定步长方法 问题给定和方向d,确定步长α,使得 问题给定(py白1,n,拟合一个函敷=几(x) min f(x +ad 优化问题 其中x为待定的参数向量,∫对x非线性 dola=0 4(d")Vf(x +ad)=0 记误差r(x)=y-f(12x)r(x)=((x)…(x) 优化模型minR(x)=r(x)r(x) 优化糞金分割(0.618)法、 Fibonacci法、 Newton 算法 切线法、割线法、2次或3次插值法等 根据目标函数是rx)的二次函数的特点 构造简单算法 非线性最小二乘拟合 R(x)=r(x)r(x) 非线性最小二乘拟合 记r(x)的雅各比阵为J(x)=(r/ax)m Gauss-Newton算法:忽略矩阵S VR=2J(x)r(x)VR=2J(x)J(x)+2S 牛顿方程Vf(x2)d=-Vf(x2) S=Er(x)V; (x)Vr(x)=(@r/ax, ax) 用R代替,下降方向满足 讨论·牛顿法要计算 Hessian矩阵,其中S计算量大 J(x2)yJ(x4)d=-J/(x2)r(x2) ·若∫对x线性,则化为缄性最小二乘拟合此时S=0 GN算法收斂性依赖厂对x的线性程度 及偏差r的大小 特定算法考虑如何忽略或近似矩阵S。 (学学奖 大学费学买验 非线性最小二乘拟合 优化工具箱 Levenberg- Marquardt算法:GN算法修正 模型:Minf(x),x∈R f(x)的m文件名 x0~初始点;x-最优解 J(x2)2J(x2)d*=-J(x2)r(x) 基本用法 ~传给fun的参敷 几防止J出现病态 xfm]nnd(e,1b,u)中间输入项缺省用占位 (J(x2)yJ(x*)+a4D)d=-J(x3)r(x2) x=fminunc(@f, xo) x=fminunc(ef, xO, options, P1, P2,...) 中c少>0为修正参数 x=fminsearch(ef, xO, options, P1, P2,...) LM算法严位于牛顿方向(a很小)和负梯度 例:min(3sinx+x) 方向(很大之间 ∈l8 例ma+bE 其中a=b

4 搜索步长的确定 线性搜索(Line Search)确定步长方法 问题 给定xk和方向dk, 确定步长αk, 使得 min ( ) k k f x αd α + 优化 算法 黄金分割(0.618)法、Fibonacci法、Newton 切线法、割线法、2次或3次插值法等 ~一维优化问题 k = 0 d df α α ( ) ∇ ( + ) = 0 k T k k k d f x α d 非线性最小二乘(Least Square)拟合 问题 给定(t i , y i ), i=1,…n, 拟合一个函数y=f(t, x)， 其中x为待定的参数向量, f 对x非线性。 优化模型 min R(x) r (x)r(x) T x = r(x) y f (t , x) i = i − i T n r(x) (r(x), r (x)) 记误差 = 1 L 根据目标函数是 r(x) 的二次函数的特点 构造简单算法 非线性最小二乘拟合 R 2J (x) r(x) T ∇ = R J x J x S T 2 ( ) ( ) 2 2 ∇ = + i i k l m m r x r x x × ∇ ( ) = (∂ ∂ ∂ ) 2 2 讨论 • 牛顿法要计算Hessian矩阵，其中S计算量大 • 若 f 对x线性, 则化为线性最小二乘拟合,此时S=0 特定算法考虑如何忽略或近似矩阵S。 i j n m J x r x × 记 r(x) 的雅各比阵为 ( ) = (∂ / ∂ ) R(x) r (x)r(x) T = ( ) ( ) 2 1 S r x r x i n i =∑ i ∇ = Gauss-Newton算法：忽略矩阵S ( ) ( ) ( ) ( ) k T k k k k J x J x d = −J x r x f用R代替，下降方向dk满足 G-N算法 收敛性依赖 f 对 x 的线性程度, 及偏差r的大小 非线性最小二乘拟合 ( ) ( ) 2 k k 牛顿方程 ∇ f x d = −∇f x R 2J (x) r(x) T ∇ = 2 ( ) ( ) 2R J x J x T ∇ = Levenbery-Marquardt算法：G-N算法修正 ( ( ) ( ) ) ( ) ( ) k T k k k k k J x J x +α I d = −J x r x 其中αk>0为修正参数. dk位于牛顿方向(αk很小)和负梯度 方向(αk很大)之间 L-M算法 非线性最小二乘拟合 ( ) ( ) ( ) ( ) k T k k k k J x J x d = −J x r x 防止 JTJ 出现病态 优化工具箱 基本用法： x=fminbnd(@f,lb,ub) x=fminunc(@f,x0) x=fminunc(@f,x0,options,P1,P2,...) x=fminsearch(@f,x0,options,P1,P2,...) f.m ~ f(x)的m文件名 x0 ~初始点; x ~最优解 P1,P2, … ~ 传给fun的参数 中间输入项缺省用[ ]占位 n x 模型：Min f (x), x∈ R 2 2 min 2 2 = = + a b b y a x 其中 例 ： Exam0701.m Exam0702.m x [1,8] 1 min (3sinx x) ∈ 例 ： +

非线性最小二乘法(x)=y.-f(,x) min R(x)=r(xr(x) r(x)=(r(x),r(x)) 非线性最小二乘法minR(x)=r(x)r(x) [x, resnorm, res, exit, out, lambda, jacob] 例3用下面一组数据拟合系数rk c(t=re- [x, resnorm, res, exitf, out, lambda, jacob] P1,P2 输入的用法与 Eminunc类似,但注意 1921115314101284937415241301 f.m~f(x)的m文件名:func fun,m~x(x)的m文件名; function r=fun(x,t,y) 输出 reson=(x)T*x(x),xes=r(x)(误差向量) 控制精度,观察中间结果,控制选代次数等 主要控制参数(对大规模/中等规模算法均有效) options控制参敷设定/莪取: optinet; optimget Diagnostics'on’I('off'}//是否显示诊断信惠 //显示控制参数 off I 'iter fina1’| notify、//显示信的级 optimset optfun//显示 optfun的控制参数 Grado] on’t'off}//是否用分析度 opt=optimise //挫制参敷设为[(即缺省值 on’|【。ff pt= optinet( optfun)// optfun拉制李数设缺省值 //乘用分析Jacb阵(用子约来优化中) Opt-optimset('parl', vall,'par2, val2,.) off//是否采用大规模算法 Opt=optimset(oldopts,'parl, vall,.) axFunEva1s最大画数调用次舭 最大速代次数 约的控制精度(用于约乘优化中 val=optimget(opt, 'par1,'par2,) T。1Eun 函敷值的控制精度 val=optimget(opt,'parl,'par2 default) Tol 解的控制精度 (学学奖 (学学 更多输出:最优值等 最一般的输出形式 4 min a=10.b=1 [x, f, exitflag, out ]=fminu 目标函数值 用。 ptimset控制参教选择 exits1ag>0收做,0达到函敷成选代次敷,<0不收做 Output iterations实际选代次敷 实际函训用次敷 gorithm 实际采用的其法 cgiterations实际Pc选代次数(大规模算法用) firstorderopt一阶最优条件(梯度的范数) grad目标画数的梯度 hess标函教的 Hessian矩阵

5 非线性最小二乘法 min R(x) r (x)r(x) T lb x ub = ≤ ≤ r ( x) y f (t , x) i = i − i T n r(x) (r (x), r (x)) = 1 L [x,resnorm,res,exitf,out,lambda,jacob]= lsqnonlin(@fun,x0,lb,ub,options,P1,P2,…) 输入的用法与fminunc类似，但注意： f.m~f(x)的m文件名: function y=f(x,t) fun.m~r(x)的m文件名: function r=fun(x,t,y) 输出 resnom=r(x)T*r(x), res=r(x)(误差向量) [x,resnorm,res,exitf,out,lambda,jacob]= lsqcurvefit(@f,x0,t,y,lb,ub,options,P1,P2,…) 非线性最小二乘法 min R(x) r (x)r(x) T lb x ub = ≤ ≤ c 19.21 18.15 15.36 14.10 12.89 9.32 7.45 5.24 3.01 t 0.25 0.5 1 1.5 2 3 4 6 8 kt c t re − ( ) = 例3 用下面一组数据拟合系数r, k : exam0703fit.m exam0703lsq.m 控制精度，观察中间结果，控制迭代次数等 Optimset //显示控制参数 optimset optfun //显示optfun的控制参数 opt=optimset //控制参数设为[](即缺省值) opt=optimset(optfun)//optfun控制参数设缺省值 Opt=optimset('par1',val1,'par2',val2,...) Opt=optimset(oldopts,'par1',val1,...) opt=optimset(oldopts,newopts) val=optimget(opt,'par1','par2',…) val=optimget(opt,'par1','par2',…, default) Options 控制参数设定/获取: optimset; optimget Diagnostics ‘on’ | {‘off’} //是否显示诊断信息 Display 'off' | 'iter' | ‘final’ | ‘notify‘ //显示信息的级别 GradObj ‘on’ | {‘off’}//是否采用分析梯度 Jacobian ‘on’ | {‘off’} //采用分析Jacob阵（用于约束优化中） LargeScale ‘on’ | {‘off’}//是否采用大规模算法 MaxFunEvals 最大函数调用次数 MaxIter 最大迭代次数 TolCon 约束的控制精度（用于约束优化中） TolFun 函数值的控制精度 TolX 解的控制精度 主要控制参数(对大规模/中等规模算法均有效) 最一般的输出形式 [x,f,exitflag,out,grad,hess]=fminunc(...) 更多输出：最优值等 f 目标函数值 exitflag >0收敛,0达到函数或迭代次数, <0不收敛 Output iterations 实际迭代次数 funcCount 实际函数调用次数 algorithm 实际采用的算法 cgiterations 实际PCG迭代次数（大规模算法用） stepsize 最后迭代步长（中等规模算法用） firstorderopt 一阶最优条件（梯度的范数） grad 目标函数的梯度 hess 目标函数的Hessian矩阵 例 4 min , 10, 1 2 2 2 1 + a = b = b x a x Exam0704.m 用optimset控制参数选择

算法选择:。 ptimset中参数控制 例5minf(x,y)=100(y-x2)2+(1-x)2 on’l'off′(on为缺省) 精确解:x=y=1,∫xy)=0 系就缺省采用大规模算法(如果可能 Exam0705m 当设为'off"时缺省:BFGs、混合2,3次多项式插值 计算结果 搜索方向的算法选择 方向|步长 最优值 HessUpdate=dfp’(DF算法 次(9.997019.9900)109400 HessU pdate=‘ steepest'(最速下降算法) DFP|2,3次09.997001999400)2.11300165 sep2,3次(8.0263e00165064001)32536e+001003 索步长的算法选择 BFGS3次1000001012 Line SearchType= quadcubic''混合2,3次多项式插值 DFP3次|(9468c0018.157200198270003495 Line SearchType= cubicpoly'3次多项式播值 step3次(-1.1831e+0001.4056e+0004.7695e+0001002 无约束优化模型:Mmf(x),x∈R 计算站果 方向步 采用分析梯度 BFGS2,3次(10001e+00010002e+0008.9857-009105 Gradobj='on' DFP2.31000040199109 BFGS3次|(1.000000100.716400953 x=fminunc(efun, xo, opt,) funm中还要有Vf(x) DFP3次(747l05.5212001)67609e00214 与不用分析梯度的结采比较 般形式￡ unction【f,g]=fun(x) 方向|步长 最优解x 最优值∫ 续例5minf(x,y)=100y-x2)2+(1-x) (9.99970019999001)1.094009 DFP2,3次(9.9997-0019998001)2.1173e009165 算出vf= 400x(y-x2)-2(1-x) BFGS3次|(100e00001432-008162 00 DFP|3次(9068001857200987e03495 学学实 几个值得注意的问题 f(x,y)=1000-x2)2+(1-x)2的图形 梯度函敷:利用分析梯度可能改进算法的性能 Rosenbrock函数 精度控制:对选代次数有重大影响,应适当选择 (香蕉函数) kam0705plotm 改变初始值由一个初值出发遁常得到局部最优解, 如果函教存在多个局部最优,只有改变初值,对局 部最优进行比较,才有可能得到全局最优解 算法选择:BFGS公式,混合2,3次插值,一般校好 其他算法选择:(评细用法请查阅help文档 高度非线性、不连续时可用程序 fminsearch(afun,x0) 单变量时可用程序 fminbnd(afun,v1,v2)

6 算法选择：optimset中参数控制 LargeScale ‘on’ | ‘off’ （on为缺省） 搜索步长的算法选择 系统缺省采用大规模算法（如果可能） 当设为‘off’时缺省：BFGS、混合2, 3次多项式插值 LineSearchType='quadcubic' 混合2, 3次多项式插值 LineSearchType='cubicpoly' 3次多项式插值 HessUpdate = ‘dfp’ （DFP算法） HessUpdate = ‘steepdesc’（最速下降算法） 搜索方向的算法选择 计算结果 方向 步长 最优解x 最优值f n BFGS 2,3次 (9.9997e-001 9.9994e-001) 1.0944e-009 165 DFP 2,3次 (9.9997e-001 9.9994e-001) 2.1173e-009 165 steep 2,3次 (-8.0263e-001 6.5064e-001) 3.2536e+000 1003 BFGS 3次 (1.0001e+000 1.0003e+000) 3.1432e-008 162 DFP 3次 (9.0468e-001 8.1572e-001) 9.8270e-003 495 steep 3次 (-1.1831e+000 1.4056e+000) 4.7695e+000 1002 2 2 2 例5. min f (x, y) =100(y − x ) + (1− x) 精确解：x=y=1, f(x,y)=0 Exam0705.m 无约束优化 n x 模型：Min f (x), x∈ R 采用分析梯度： GradObj='on' x=fminunc(@fun,x0,opt,…) fun.m中还要有 一般形式 function [f,g]=fun(x) ∇f ( x) 2 2 2 续例5. min f (x, y) =100( y − x ) + (1− x) ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ − − − − − ∇ = 200( ) 400 ( ) 2(1 ) 2 2 y x x y x x 算出 f exam0705grad_run.m 方向 步长 最优解x 最优值f n BFGS 2,3次 (1.0001e+000 1.0002e+000) 8.9857-009 105 DFP 2,3次 (1.0001e+000 1.0003e+000) 2.2499e-008 109 BFGS 3次 (1.0000e+000 1.0001e+000) 2.7164e-009 53 DFP 3次 (7.4711e-001 5.5212e-001) 6.7609e-002 144 计算结果 与不用分析梯度的结果比较 方向 步长 最优解x 最优值f n BFGS 2,3次 (9.9997e-001 9.9994e-001) 1.0944e-009 165 DFP 2,3次 (9.9997e-001 9.9994e-001) 2.1173e-009 165 BFGS 3次 (1.0001e+000 1.0003e+000) 3.1432e-008 162 DFP 3次 (9.0468e-001 8.1572e-001) 9.8270e-003 495 x0 * O f (x, y) =100(y − x2 ) 2 + (1− x) 2 的图形 exam0705plot.m Rosenbrock 函数 （香蕉函数） 算法选择：BFGS公式，混合2，3次插值，一般较好。 几个值得注意的问题 精度控制：对迭代次数有重大影响，应适当选择。 梯度函数：利用分析梯度可能改进算法的性能 改变初始值 由一个初值出发通常得到局部最优解， 如果函数存在多个局部最优，只有改变初值，对局 部最优进行比较，才有可能得到全局最优解。 其他算法选择： （详细用法请查阅help文档） 高度非线性、不连续时可用程序 fminsearch(@fun,x0) 单变量时可用程序 fminbnd(@fun,v1,v2)

非线性最小二乘法(x)=y.-f(,x) 非线性最小二乘法minR(x)=r(x)r(x) min R(x)=r(x)r(x) r(x)=(r(x),r(x) xitf, out, lambda, ja 省:大桃油( LargeSca1e= Isqnonlin(G :o,1b, ub, options, Pl 缺省:工 ardt算法; 输入的用法与 Eminunc类似,但注意:fun.m~r(x) 的m文件名, Jacobian='on时含有导数敷信息vr(x evenbergMarquardt='off: Gauss-Newton%t 单搜索(线技你)步长选择与 minute中类似 function [r,J]= fun(x) exam0705sq m exam0705l5q jacob_run.m 实例1产销量安排 实例1产销量安排 初始点忽略成本及价12 原问题4=75+4,14>0=12 的选择格中的 max(x1,x2)=(P1-q)x+(P2-92)x2 问题简化为minf(x)=-(b-a11x)x-(b-a22x2)x2 其解为x=h 已知 a21a2)(022 作为原问题的初始点 r=(30100x=(001500m)c7=(20 命令和最优解x= fminunc(a,x0) shili0701m inf(x)=-(b-a11-a2-ne-4-)x x=239025624977y=64135+003 即甲产量为239025,乙产量为62497,最大利润为6435 (b2-a21x1-a22x2-P2e 学学实 实例2飞机精确定位模型 其他:非线性方程(组) Min E(x,y)= 无约束非线性最小二乘模型 单变量方程求根:f(x)=0,x∈R atan2(x-x,y-y)-e, , d.-(r-x4)+(y-V)? [x, fval, exitflag, output] fzero(fun, xo, options,P1 角度需要进行预处理, hili0702 m 多变量方程组求零点:F(x)=0,x∈R 如利用atan2函数值域(-pi,pi) [x, fval, exitflag, output, jacobian] fsolve(fun, xo, options, P1, P2 飞机坐标(97831,723.98,误差平方和0.685(<4)

7 非线性最小二乘法 min R(x) r (x)r(x) T lb x ub = ≤ ≤ r ( x) y f (t , x) i = i − i T n r(x) (r (x), r (x)) = 1 L [x,resnorm,res,exitf,out,lambda,jacob]= lsqnonlin(@fun,x0,lb,ub,options,P1,P2,…) 输入的用法与fminunc类似，但注意：fun.m ~r(x) 的m文件名，Jacobian=‘on’时含有导数信息 function [r,J] = fun(x) ∇r(x) 算法选择: 缺省：大规模算法（LargeScale = 'on' ） 当LargeScale = 'off' ： •缺省： Levenberg-Marquardt算法； •LevenbergMarquardt=‘off’:Gauss-Newton法 一维搜索（线搜索）步长选择与fminunc中类似 非线性最小二乘法 min R(x) r (x)r(x) T lb x ub = ≤ ≤ exam0705lsq.m exam0705lsq_jacob_run.m 实例1 产销量安排 ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ =⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ 280 100 0.2 2 1 0.1 21 22 11 12 b a a a a 已知 数据 = (30 100 ), = (0.015 0.02 ), = (20 30) T T T r λ c 2 21 1 22 2 2 2 2 1 11 1 12 2 1 1 1 ( ) min ( ) ( ) 2 2 1 1 b a x a x r e c x f x b a x a x r e c x x x − − − − − = − − − − − − − λ λ , , , 0, 1,2, pi =bi −ai1x1 −ai2x2 bi ai1 ai2 > i = = + , , , > 0, =1,2, − q r e c r c i i i i i x i i i i λ λ 1 2 1 1 1 2 2 2 , max ( , ) ( ) ( ) 1 2 z x x p q x p q x x x = − + − 原问题 x = 23.9025 62.4977 y = 6.4135e+003 即甲产量为23.9025，乙产量为62.4977，最大利润为6413.5 命令和最优解 x=fminunc(@f, x0) shili0701.m 其解为x1 = b1 / 2a11 = 50， x2 = b2 / 2a22 = 70 初始点 的选择 实例1 产销量安排 ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ =⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ 0.2 2 1 0.1 21 22 11 12 a a 忽略成本及价 a a 格中的 a12, a21 1 11 1 1 2 22 2 2 问题简化为 min f (x) = −(b − a x )x − (b − a x )x 作为原问题的初始点 飞机坐标(978.31，723.98), 误差平方和0.6685 (<< 4) 实例2 飞机精确定位模型 2 4 2 4 2 4 4 2 3 1 atan2( , ) ( ) ( ) ( , ) ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − − + − + ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ − − − = ∑= σ σ x x y y θ d x x y y Min E x y i i i i i 无约束非线性最小二乘模型 角度需要进行预处理， 如利用atan2函数, 值域(-pi, pi) shili0702.m 其他:非线性方程(组) 单变量方程求根： f (x) = 0, x ∈ R [x,fval,exitflag,output] = fzero(fun,x0,options,P1,P2,...) [x,fval,exitflag,output,jacobian] = fsolve(fun,x0,options,P1,P2, ... ) n 多变量方程组求零点： F(x) = 0, x ∈ R

其他:非负最小二乘mnkx-d2 其他:约束线性最小二乘 [x, resnorm, res, exit, out, lambda]= 士x-d lsqnonneg(c,d, xo, options) s1.A1x≤b,A2x≤b2,b≤x≤b 敷播拟合也可用mn|F(x,dma)-yml [x, resnorm, res, exitflag, output, lambda] lsqlin(C, d, Al, bl, A2, b2, 1b, ub, xo, options) =∑(F(x,xdan)- ydata) 其他优化程序(实验8) 其他优化程序 [x, resnorm, res, exit, out, lambda, jacob] quadprog:包舰 Minimax 小大 lsqcurvefit(fun, xo, x y, lb, ub, opt, Pl, P2,.) fmincon:来非能他肌划 Semine 元购叱化内容 实验目的 1.掌握 Matlab优化工具包的基本用法,对不同 算法进行初步分析、比较 2.练习建立和求解实际问题的无约束优化模型和 非线性最小二乘拟合模型 内 容课上布置,或参见网络学堂 还 8

8 2 2 2 1 0 min Cx d x − ≥ [x,resnorm,res,exitf,out,lambda]= lsqnonneg(C,d,x0,options) 数据拟合也可用 lsqcurvefit [x,resnorm,res,exitf,out,lambda,jacob] = lsqcurvefit(fun,x0,x,y,lb,ub,opt,P1,P2,…) = ∑( ) − − ≥ i i i x F x xdata ydata F x xdata ydata 2 2 1 2 2 2 1 0 ( , ) min ( , ) 其他:非负最小二乘 s t A x b A x b lb x ub Cx d x ≤ ≤ ≤ ≤ − ≥ . . , , min 1 1 2 2 2 2 2 1 0 [x,resnorm,res,exitflag,output,lambda] = lsqlin(C,d,A1,b1,A2,b2,lb,ub,x0,options) 其他优化程序 Fgoalattain：多目标规划 fminimax ：极小极大 fseminf ：半无穷规划 其他优化程序(实验8) linprog ：线性规划 quadprog：线性规划 fmincon ：约束非线性规划 其他:约束线性最小二乘 无约束优化实验内容 实验目的 1．掌握 Matlab 优化工具包的基本用法，对不同 算法进行初步分析、比较。 2．练习建立和求解实际问题的无约束优化模型和 非线性最小二乘拟合模型。 内容 课上布置，或参见网络学堂