现代设计方法(三):无约束方法、线性规划与约束方法
对应第三章第二节二至四:一维搜索(区间确定、黄金分割法、二次插值法)、梯度法、牛顿法、变尺度法、共轭梯度法;线性规划的一般形式、基本可行解与单纯形法;约束一维搜索、可行方向法与内点、外点、混合罚函数法。
本节导读
这一节对应大纲第三章第二节的后三条:无约束最优化方法、线性规划方法、约束最优化方法。第 15 节讲了「下降迭代」的框架,这一节讲具体怎样定方向、定步长。
学完要做到:会用黄金分割法缩小区间;会算梯度法、牛顿法的一步迭代,说出两者的优缺点;会判断两个方向是否共轭;会列单纯形表、确定换入换出变量;说出内点法和外点法的区别,会求简单罚函数的极小点。
本节记号沿用第 15 节:迭代序号上标 (k),步长因子 α,搜索方向 S,梯度 g=∇f,海塞矩阵 H;罚因子 r。
无约束最优化方法
一维搜索法
确定了方向 S(k) 后,求最优步长就是一元函数 φ(α)=f(X(k)+αS(k)) 的极小化问题。
初始区间的确定和缩小:先用进退法找出「高—低—高」的三个点,确定包含极小点的初始区间 [a,b];再在区间内取两点比较函数值,舍去不含极小点的一段,逐步缩小区间(单峰函数)。
黄金分割法:在 [a,b] 内按对称位置取两点
α1α2=a+0.382(b−a)=a+0.618(b−a)比较函数值,若 φ(α1)<φ(α2) 就舍去 [α2,b],否则舍去 [a,α1]。每次区间缩为原来的 0.618 倍,且保留的那个点正好是下一轮的一个分点,每轮只需新算一个函数值。
二次插值法:用区间内三点 (α1,φ1)、(α2,φ2)、(α3,φ3) 作抛物线,取其极小点作为新的近似点:
αp=21⋅(α2−α3)φ1+(α3−α1)φ2+(α1−α2)φ3(α22−α32)φ1+(α32−α12)φ2+(α12−α22)φ3函数接近二次时收敛很快。
梯度法
取负梯度为搜索方向,S(k)=−g(k),又叫最速下降法。对二次函数 f=21XTHX+⋯,沿负梯度的最优步长为
α(k)=g(k)THg(k)g(k)Tg(k)特点:开始几步下降快、程序简单;相邻两步的搜索方向互相垂直,在极小点附近走「之」字形,收敛慢。
牛顿法
基本牛顿法:用二阶泰勒展开近似目标函数,令其梯度为零,
X(k+1)=X(k)−H−1(X(k))g(k)对正定二次函数一步就到极小点,在极小点附近收敛很快(二阶收敛);缺点是要算海塞矩阵及其逆,初始点离极小点远时可能不下降甚至发散。阻尼牛顿法:取牛顿方向 S=−H−1g,但步长由一维搜索确定,保证每步都下降。
变尺度法
用一个逐步修正的正定矩阵 A(k) 近似 H−1,搜索方向 S(k)=−A(k)g(k);A(0) 取单位阵(第一步就是梯度法),以后按相邻两点的梯度差、位置差修正(DFP、BFGS 两种修正公式),逐渐逼近牛顿方向。它不用算二阶导数,又有接近牛顿法的收敛速度,是常用的无约束方法。
共轭梯度法
共轭方向:对正定矩阵 H,若 S1THS2=0,称 S1、S2 关于 H 共轭;H 为单位阵时就是普通的正交。沿 n 个互相共轭的方向依次做一维搜索,n 元正定二次函数最多 n 步到达极小点。
共轭方向的形成:可以从任意方向出发,用 H 构造与之共轭的方向;也可以不用 H,靠两次平行搜索的极小点连线得到(鲍威尔法的思路)。
共轭梯度法:用梯度构造共轭方向,S(0)=−g(0),以后
S(k+1)β(k)=−g(k+1)+β(k)S(k)=∥g(k)∥2∥g(k+1)∥2只用一阶导数,存储量小,适合变量较多的问题。
线性规划方法
线性规划问题的一般形式
目标函数和约束都是线性的:maxz=∑cjxj,约束 ∑aijxj≤bi,xj≥0。标准形把不等式约束加松弛变量化成等式、右端项非负。
解的产生与转换
- 解的产生:m 个等式约束、n 个变量时,令 n−m 个非基变量为零,解出 m 个基变量,得到基本解;各变量都非负的基本解叫基本可行解,对应可行域的顶点。最优解(若存在)一定能在某个顶点上找到。
- 解的转换:从一个基本可行解换到相邻的另一个:选一个非基变量换入基,按最小比值规则选一个基变量换出,保证新解仍可行。
- 初始基本可行解:约束都是「≤」且右端非负时,直接取松弛变量为基变量;否则要引入人工变量(大 M 法或两阶段法)。
本节后面还有约 2223 字:报名学员看全文
每门课前 10 节免费看全文;从第 11 节起,完整教程要报名后由顾问在后台为你的账号开通才能看。
题库账号可以直接登录,但第 11 节起的完整教程要报名后由后台开通才能看。
学完练一练
按本节考点从本课的课后练习里抽题(每次 10 道以内),做完看解析、错题自动进错题本。第 11 节起的课后练习报名学员才能练。
本节内容由 AI 辅助编写,配图由 AI 生成,仅供备考参考;考试要求以《全国各类成人高等学校招生考试大纲(2024 年版)》及浙江省教育考试院当年公布为准。