杭州紫金港培训学校(紫金港专升本)杭州紫金港培训学校(紫金港专升本)
同等学力申硕机械工程学科综合考前辅导第三章 现代设计方法第 16 节 / 共 32 节约 30 分钟报名学员看全文

现代设计方法(三):无约束方法、线性规划与约束方法

对应第三章第二节二至四:一维搜索(区间确定、黄金分割法、二次插值法)、梯度法、牛顿法、变尺度法、共轭梯度法;线性规划的一般形式、基本可行解与单纯形法;约束一维搜索、可行方向法与内点、外点、混合罚函数法。

本节考点:一维搜索法梯度法与牛顿法共轭方向与变尺度法线性规划方法约束最优化方法

本节导读

这一节对应大纲第三章第二节的后三条:无约束最优化方法、线性规划方法、约束最优化方法。第 15 节讲了「下降迭代」的框架,这一节讲具体怎样定方向、定步长。

学完要做到:会用黄金分割法缩小区间;会算梯度法、牛顿法的一步迭代,说出两者的优缺点;会判断两个方向是否共轭;会列单纯形表、确定换入换出变量;说出内点法和外点法的区别,会求简单罚函数的极小点。

本节记号沿用第 15 节:迭代序号上标 (k)(k)(k),步长因子 α\alphaα,搜索方向 SSS,梯度 g=∇fg=\nabla fg=∇f,海塞矩阵 HHH;罚因子 rrr。

无约束最优化方法

一维搜索法

确定了方向 S(k)S^{(k)}S(k) 后,求最优步长就是一元函数 φ(α)=f(X(k)+αS(k))\varphi(\alpha)=f(X^{(k)}+\alpha S^{(k)})φ(α)=f(X(k)+αS(k)) 的极小化问题。

初始区间的确定和缩小:先用进退法找出「高—低—高」的三个点,确定包含极小点的初始区间 [a,b][a,b][a,b];再在区间内取两点比较函数值,舍去不含极小点的一段,逐步缩小区间(单峰函数)。

黄金分割法:在 [a,b][a,b][a,b] 内按对称位置取两点

α1=a+0.382(b−a)α2=a+0.618(b−a)\begin{aligned} \alpha_1&=a+0.382(b-a) \\ \alpha_2&=a+0.618(b-a) \end{aligned}α1​α2​​=a+0.382(b−a)=a+0.618(b−a)​

比较函数值,若 φ(α1)<φ(α2)\varphi(\alpha_1)\lt\varphi(\alpha_2)φ(α1​)<φ(α2​) 就舍去 [α2,b][\alpha_2,b][α2​,b],否则舍去 [a,α1][a,\alpha_1][a,α1​]。每次区间缩为原来的 0.618 倍,且保留的那个点正好是下一轮的一个分点,每轮只需新算一个函数值。

二次插值法:用区间内三点 (α1,φ1)(\alpha_1,\varphi_1)(α1​,φ1​)、(α2,φ2)(\alpha_2,\varphi_2)(α2​,φ2​)、(α3,φ3)(\alpha_3,\varphi_3)(α3​,φ3​) 作抛物线,取其极小点作为新的近似点:

αp=12⋅(α22−α32)φ1+(α32−α12)φ2+(α12−α22)φ3(α2−α3)φ1+(α3−α1)φ2+(α1−α2)φ3\begin{aligned} &\alpha_p=\frac12\cdot \\ &\frac{(\alpha_2^{2}-\alpha_3^{2})\varphi_1+(\alpha_3^{2}-\alpha_1^{2})\varphi_2+(\alpha_1^{2}-\alpha_2^{2})\varphi_3}{(\alpha_2-\alpha_3)\varphi_1+(\alpha_3-\alpha_1)\varphi_2+(\alpha_1-\alpha_2)\varphi_3} \end{aligned}​αp​=21​⋅(α2​−α3​)φ1​+(α3​−α1​)φ2​+(α1​−α2​)φ3​(α22​−α32​)φ1​+(α32​−α12​)φ2​+(α12​−α22​)φ3​​​

函数接近二次时收敛很快。

梯度法

取负梯度为搜索方向,S(k)=−g(k)S^{(k)}=-g^{(k)}S(k)=−g(k),又叫最速下降法。对二次函数 f=12XTHX+⋯f=\frac12X^{\mathrm T}HX+\cdotsf=21​XTHX+⋯,沿负梯度的最优步长为

α(k)=g(k)Tg(k)g(k)THg(k)\alpha^{(k)}=\frac{g^{(k)\mathrm T}g^{(k)}}{g^{(k)\mathrm T}Hg^{(k)}}α(k)=g(k)THg(k)g(k)Tg(k)​

特点:开始几步下降快、程序简单;相邻两步的搜索方向互相垂直,在极小点附近走「之」字形,收敛慢。

牛顿法

基本牛顿法:用二阶泰勒展开近似目标函数,令其梯度为零,

X(k+1)=X(k)−H−1(X(k)) g(k)X^{(k+1)}=X^{(k)}-H^{-1}(X^{(k)})\,g^{(k)}X(k+1)=X(k)−H−1(X(k))g(k)

对正定二次函数一步就到极小点,在极小点附近收敛很快(二阶收敛);缺点是要算海塞矩阵及其逆,初始点离极小点远时可能不下降甚至发散。阻尼牛顿法:取牛顿方向 S=−H−1gS=-H^{-1}gS=−H−1g,但步长由一维搜索确定,保证每步都下降。

变尺度法

用一个逐步修正的正定矩阵 A(k)A^{(k)}A(k) 近似 H−1H^{-1}H−1,搜索方向 S(k)=−A(k)g(k)S^{(k)}=-A^{(k)}g^{(k)}S(k)=−A(k)g(k);A(0)A^{(0)}A(0) 取单位阵(第一步就是梯度法),以后按相邻两点的梯度差、位置差修正(DFP、BFGS 两种修正公式),逐渐逼近牛顿方向。它不用算二阶导数,又有接近牛顿法的收敛速度,是常用的无约束方法。

共轭梯度法

共轭方向:对正定矩阵 HHH,若 S1THS2=0S_1^{\mathrm T}HS_2=0S1T​HS2​=0,称 S1S_1S1​、S2S_2S2​ 关于 HHH 共轭;HHH 为单位阵时就是普通的正交。沿 nnn 个互相共轭的方向依次做一维搜索,nnn 元正定二次函数最多 nnn 步到达极小点。

共轭方向的形成:可以从任意方向出发,用 HHH 构造与之共轭的方向;也可以不用 HHH,靠两次平行搜索的极小点连线得到(鲍威尔法的思路)。

共轭梯度法:用梯度构造共轭方向,S(0)=−g(0)S^{(0)}=-g^{(0)}S(0)=−g(0),以后

S(k+1)=−g(k+1)+β(k)S(k)β(k)=∥g(k+1)∥2∥g(k)∥2\begin{aligned} S^{(k+1)}&=-g^{(k+1)}+\beta^{(k)}S^{(k)} \\ \beta^{(k)}&=\frac{\lVert g^{(k+1)}\rVert^{2}}{\lVert g^{(k)}\rVert^{2}} \end{aligned}S(k+1)β(k)​=−g(k+1)+β(k)S(k)=∥g(k)∥2∥g(k+1)∥2​​

只用一阶导数,存储量小,适合变量较多的问题。

线性规划方法

线性规划问题的一般形式

目标函数和约束都是线性的:max⁡z=∑cjxj\max z=\sum c_jx_jmaxz=∑cj​xj​,约束 ∑aijxj≤bi\sum a_{ij}x_j\le b_i∑aij​xj​≤bi​,xj≥0x_j\ge 0xj​≥0。标准形把不等式约束加松弛变量化成等式、右端项非负。

解的产生与转换

  • 解的产生:mmm 个等式约束、nnn 个变量时,令 n−mn-mn−m 个非基变量为零,解出 mmm 个基变量,得到基本解;各变量都非负的基本解叫基本可行解,对应可行域的顶点。最优解(若存在)一定能在某个顶点上找到。
  • 解的转换:从一个基本可行解换到相邻的另一个:选一个非基变量换入基,按最小比值规则选一个基变量换出,保证新解仍可行。
  • 初始基本可行解:约束都是「≤\le≤」且右端非负时,直接取松弛变量为基变量;否则要引入人工变量(大 M 法或两阶段法)。

本节后面还有约 2223 字:报名学员看全文

每门课前 10 节免费看全文;从第 11 节起,完整教程要报名后由顾问在后台为你的账号开通才能看。

题库账号可以直接登录,但第 11 节起的完整教程要报名后由后台开通才能看。

学完练一练

按本节考点从本课的课后练习里抽题(每次 10 道以内),做完看解析、错题自动进错题本。第 11 节起的课后练习报名学员才能练。

本节内容由 AI 辅助编写,配图由 AI 生成,仅供备考参考;考试要求以《全国各类成人高等学校招生考试大纲(2024 年版)》及浙江省教育考试院当年公布为准。

我要提问免费报名咨询