机械优化设计 · 对话式复习卷
一章一页,知识点 → 例题 → 真题习题;所有例题与真题的答案都折叠在三角标后面,先自己想,再点开对答案。
开卷考试 · 90 分钟笔试 + 云班课客观题 · 依据本校 2016 与 2020 两套真题整理
建模 + 程序化
变化率/迭代/等式约束/无约束方法
画图 + K-T 判定
必须会画
一、这门课考什么:先看分值再决定背什么
根据 2020-06-16 真题,笔试 100 分、限时 90 分钟,结构非常稳定:
| 题号 | 题型 | 分值 | 考什么 | 本卷对应 |
|---|---|---|---|---|
| 一 | 简答 4 题 | 4×5=20 | 函数变化率的意义、数值迭代法、等式约束处理、无约束方法列举 | 第2章 + 第4章 |
| 二 | 计算 | 4+8+2+6=20 | 画设计空间/可行域/等值线;K-T 判定;局部/全局;自选点 | 第2章 §6 |
| 三 | 简述 + 框图 | 5+10=15 | 产生可行初始点的算法步骤 + 框图 | 第5-6章 §6 |
| 四 | 绘图 + 文字 | 15 | 复合形法“反射-收缩”迭代过程 | 第5-6章 §4 |
| 五 | 应用题 2 题 | 2×15=30 | 圆木锯梁建模 + 程序化;型材下料建模 | 第1章 §5 |
二、六条主线
三、5 天节奏(按你自己时间压缩也行)
| 天 | 主线 | 过关标准 |
|---|---|---|
| D1 | 第1章 + 第2章 | 会建三要素模型并按课本格式写子程序;能不看书写出 K-T 方程组并判 μ 符号 |
| D2 | 第3章 | 15 分钟内完成 0.618 两轮;能写出二次插值 αp 公式与四种缩小区间 |
| D3 | 第4章 | 默画七方法对比表;独立完成 DFP 一轮 |
| D4 | 第5-6章 | 5 分钟画出复合形“反射-收缩”图;写出内点/外点惩罚函数式与初始点框图 |
| D5 | 真题限时 | 90 分钟做完 2020 卷 80% 以上;错题回到本页对应小节 |
建议:每章先读“知识点”不点开例题,自己动手写一遍,再点三角对答案;例题后面紧跟的真题折叠块一定要遮住答案做。
四、这个页面的用法
三角形 = 折叠
点标题右侧的三角展开答案;再点一次收起。顶部“展开本题 / 收起”可一次全开或全关。默认全部收起,方便先自测。
搜索
右上角搜索框输入“复合形”“K-T”“0.618”,会自动展开命中的折叠块并高亮,用来考前定位最快。
进度会记住
当前页签、深浅色、滚动位置都存在本机浏览器里,关掉再打开还在原处。
第 1 章 优化设计概述与建模
对应讲义《绪论 + 优化设计概述》。真题落点:应用题 2×15 分——建立数学模型(不求解)+ 按课本格式程序化。
§1.1 什么是优化设计(一句话 + 三个特点)
定义:根据给定的设计要求和现有的设计条件,应用专业理论和优化方法,在计算机上从满足要求的许多可行方案中,按给定目标自动选出最优的设计方案。
机械优化设计 = 机械设计理论 + 优化方法 + 计算机,自动寻找最优设计方案与最佳设计参数。
§1.2 数学模型三要素与标准形式(必背)
| 要素 | 含义 | 考试注意 |
|---|---|---|
| 设计变量 $\mathbf{x}=[x_1,\dots,x_n]^T$ | 设计过程中需要不断修改调整、最终确定的独立参数 | 与目标直接相关、可独立调整、越少越好;注明单位;分连续/离散 |
| 目标函数 $f(\mathbf{x})$ | 把设计目标写成设计变量的函数 | 一律写成求最小;求最大加负号 $f=-w$ |
| 约束条件 | 对设计变量的限制:性能、几何、边界 | 统一写成 $g\le 0$;$\ge$ 要乘 $-1$;等式写 $h=0$ |
等值线(面):令 $f(\mathbf{x})=C$(一系列常数),变量取得的点的集合。它能反映函数的变化情况——等值线越密,函数变化越快;等值线的法线方向就是梯度方向。
§1.3 建模五步(应用题按这个顺序写,15 分按块给分)
- 明确问题:要优化什么、已知什么、允许改什么。
- 选设计变量:$\mathbf{x}=[x_1,\dots,x_n]^T$,逐个说明符号含义与单位。
- 建目标函数:写出物理公式 → 明确最大/最小 → 统一成 $\min f(\mathbf{x})$。
- 列约束条件:性能约束(强度、刚度、稳定性)→ 几何约束(尺寸关系、装配、空间)→ 边界约束(加工、标准、正的尺寸);全部整理成 $g_u\le 0$、$h_v=0$。
- 规范化检查:量纲一致、约束不矛盾、可行域非空、说明连续还是整数/离散。
选择约束时特别注意:避免出现相互矛盾的约束,尽量减少不必要的约束。
§1.4 三种解法与图解法要点
| 方法 | 做法 | 适用 |
|---|---|---|
| 解析法 | 用微分、变分等数学工具直接求最优解 | 小型、简单、有解析式的问题 |
| 图解法 | 画目标函数等值线与约束曲线,找最后接触点 | 仅 $n\le 2$ 的低维问题,简单直观 |
| 数值迭代法 | 按一定格式反复迭代,逐步逼近最优解 | 复杂函数、无解析表达式的问题 |
图解法四步
- 建坐标,画每条约束边界(直线取两端点;圆/抛物线标圆心、顶点)。
- 代入试验点判断保留哪一侧,可行域用斜线阴影,写“可行域 $D$”。
- 令 $f=C$ 画 2–3 条等值线,用箭头标出函数值增大方向。
- 等值线与可行域最后接触的点就是约束最优点 $\mathbf{x}^*$,用 ★ 标出。
数值迭代法的核心(也是 2020 简答第 2 题)
基本思想:步步逼近、步步下降。迭代格式
三个核心:① 建立搜索方向 $\mathbf{d}^k$;② 计算最佳步长 $\alpha_k$;③ 判断是否已找到最优点(收敛准则)。
三条终止准则($\varepsilon>0$ 充分小):点距准则 $\|\mathbf{x}^{k+1}-\mathbf{x}^k\|\le\varepsilon$;函数值下降量准则 $|f(\mathbf{x}^{k+1})-f(\mathbf{x}^k)|\le\varepsilon$;梯度准则 $\|\nabla f(\mathbf{x}^k)\|\le\varepsilon$。
§1.5 例题(先遮住答案自己写,再点三角)
例1生产规划模型纠错:这个模型有几处错误?
题:某厂生产甲、乙两种产品,单件利润 200 元、300 元;三种资源消耗与限额如下。有人建了模型:
问:该模型有几处错误?请改正。
答案与采分点
三处错误:①目标函数写成 $\max$,不满足标准形式;②约束方向虽为 $\le$ 但右边是限额,写成 $g_u(\mathbf{x})\le 0$ 时须把常数移到左边;③漏了非负(边界)约束 $x_1,x_2\ge 0$。
规范模型:
考场写法:直接把“max 改 min 加负号、常数左移、补 $x_i\ge 0$”三条各写一行,再用方框给出标准形。
例2无盖长方体水箱:容积给定,求用料最省(建立模型)
题:设计一个无盖长方体水箱,容积 $V$ 给定,要求用料(表面积)最省。建立优化设计数学模型。
答案
设计变量:$\mathbf{x}=[x_1,x_2,x_3]^T=[长,宽,高]^T$(mm)。
目标函数:表面积 = 底 + 四个侧面
约束:容积等式约束 + 尺寸为正
校验(了解最优形状):由拉格朗日乘子法可得 $x_1=x_2=2x_3$,即底面为正方形、高为底边一半时表面积最小;$S_{\min}=3\sqrt[3]{2V^2}$。
例3悬臂圆截面梁:重量最轻(建立模型)
题:图示悬臂梁,长 $l$,自由端受集中力 $F$,材料许用弯曲应力 $[\sigma]$、密度 $\rho$、弹性模量 $E$,允许最大挠度 $[f]$。圆截面直径 $d$ 为设计变量,使梁的重量最轻。建立数学模型(不求解)。
答案
设计变量:$x=d$(mm)。
目标函数:重量 $W=\rho g\cdot \dfrac{\pi d^2}{4}l$,即
性能约束:①弯曲强度 $\sigma_{\max}=\dfrac{M}{W_z}=\dfrac{32Fl}{\pi d^{3}}\le[\sigma]$;②刚度 $\delta_{\max}=\dfrac{Fl^{3}}{3EI}=\dfrac{64Fl^{3}}{3\pi Ed^{4}}\le[f]$。
完整模型:
采分:两个性能约束是主体(各 4–5 分),$g_3$ 是边界约束(2 分),目标函数必须含 $\rho g$ 且写成 min(3–4 分)。
真题 2020五-1:圆木锯矩形截面梁(建模 + 程序化,15 分)
题:从直径 $D=100\text{ mm}$ 的圆木中锯出矩形截面梁,选择矩形的长 $b$ 和高 $h$,使其抗弯强度(截面系数 $W=bh^2/6$)最大。试:(1) 建立该问题优化设计的数学模型;(2) 按照课本要求的格式将其程序化。
标准答案(含程序)
(1) 数学模型
设计变量:$\mathbf{x}=[x_1,x_2]^T=[b,h]^T$(mm)。
目标函数:$W=bh^2/6$ 要求最大,故
约束:矩形必须内接于圆(对角线 ≤ $D$),尺寸为正:
★ 本题最容易丢分的是 $g_1$:矩形对角线 $=\sqrt{b^2+h^2}\le D$,即 $b^2+h^2\le D^2$(4 分)。
(2) 按课本格式程序化(FORTRAN 问题函数子程序段)
C ===== 目标函数子程序 =====
SUBROUTINE FUN(N, X, F)
DIMENSION X(N)
F = -X(1)*X(2)**2/6.0
RETURN
END
C ===== 约束函数子程序(统一 G(I) <= 0)=====
SUBROUTINE CONS(N, X, G, NC)
DIMENSION X(N), G(NC)
D = 100.0
G(1) = X(1)**2 + X(2)**2 - D**2
G(2) = -X(1)
G(3) = -X(2)
RETURN
END
若允许用 MATLAB,等价写法:
function f = objfun(x) % 目标函数
f = -x(1)*x(2)^2/6;
end
function [c, ceq] = confun(x) % 约束:c <= 0, ceq = 0
c = [x(1)^2 + x(2)^2 - 100^2; -x(1); -x(2)];
ceq = [];
end
顺带记住最优解(可用于验算):$h=\sqrt{2}\,b$,$b=D/\sqrt{3}=57.74$ mm,$h=\sqrt{2/3}\,D=81.65$ mm,$W_{\max}=D^3/(9\sqrt{3})=64150$ mm³。
真题 2020五-2:型材下料问题(建模,15 分)
题:有棒类型材长 $L=181$,所需零件长度、件数如下表,设锯缝为 1。问怎样下料料头最少。试建立优化设计数学模型(不用求解)。
| 零件1 | 零件2 | 零件3 | 零件4 | |
|---|---|---|---|---|
| 长度 | 90 | 70 | 52 | 35 |
| 件数 | 400 | 300 | 200 | 100 |
标准答案(含可行方案表与最优解)
第一步:枚举可行下料方案(每根棒料上各零件的件数 $a_{ij}$,须满足 $\sum_i a_{ij}l_i+\text{锯缝}\le 181$)
| 方案 $j$ | 零件1(90) | 零件2(70) | 零件3(52) | 零件4(35) | 用料(含锯缝) | 料头 |
|---|---|---|---|---|---|---|
| 1 | 2 | 0 | 0 | 0 | 181 | 0 |
| 2 | 1 | 0 | 1 | 1 | 178 | 3 |
| 3 | 1 | 1 | 0 | 0 | 161 | 20 |
| 4 | 0 | 2 | 0 | 1 | 176 | 5 |
| 5 | 0 | 1 | 2 | 0 | 175 | 6 |
| 6 | 0 | 0 | 3 | 0 | 157 | 24 |
| 7 | 0 | 2 | 0 | 0 | 141 | 40 |
| 8 | 1 | 0 | 0 | 2 | 161 | 20 |
说明:表中“用料”已含锯缝;方案 1 恰好零料头(2×90+1=181),是本题的“甜头”。
第二步:数学模型
设计变量:$x_j$ = 采用第 $j$ 种方案的棒料根数($j=1,\dots,p$),非负整数。
目标函数(两种等价写法,任选):
约束:零件数量必须满足
完整模型(按“根数最少”写):
第三步:最优下料方案(供理解,考场不必求)
用方案 1 切 225 根 → 得零件1 共 450 件(超产 50 件);方案 4 切 100 根 → 零件2 200 件、零件4 100 件;方案 5 切 100 根 → 零件2 100 件、零件3 200 件。合计 425 根,料头 $225\times0+100\times5+100\times6=1100$。
真题 2016六:两根钢丝绳悬吊重物(建模,15 分)
题:设一重量为 $P$ 的物体,悬挂在两根钢丝绳上,两绳悬点等高、相距 $a$,与水平线夹角分别为 $\alpha_1$、$\alpha_2$,绳长 $l_1$、$l_2$,截面积 $A_1$、$A_2$,许用应力 $[\sigma]$,弹性模量 $E$,材料比重 $\gamma$。为保证正常工作,除工作应力不大于许用应力外,还规定悬点(挂点)的铅垂位移 $\Delta f$ 不超过 $[f]$,且 $A_1$、$A_2$ 应在 $A_{\min}$ 与 $A_{\max}$ 之间。以结构总重量最轻为目标,求 $A_1$、$A_2$。建立优化设计数学模型。
标准答案(建模思路 + 完整模型)
① 设计变量:$\mathbf{x}=[A_1,A_2]^T$(两绳截面积)。
② 几何关系:两绳长 $l_1=\dfrac{a}{\cos\alpha_1}$,$l_2=\dfrac{a}{\cos\alpha_2}$。
③ 目标函数(结构总重):绳重 = 比重 × 体积
④ 受力:节点平衡(水平、竖直两方向)
⑤ 强度约束:$\sigma_i=\dfrac{T_i}{A_i}\le[\sigma]$
⑥ 刚度(位移)约束:伸长 $\Delta l_i=\dfrac{T_il_i}{EA_i}$,挂点铅垂位移 $\Delta f=\dfrac{\Delta l_i}{\sin\alpha_i}$(两式相等是其几何协调条件),故
⑦ 边界约束:$g_5=A_{\min}-A_1\le0$,$g_6=A_1-A_{\max}\le0$,$g_7=A_{\min}-A_2\le0$,$g_8=A_2-A_{\max}\le0$。
⑧ 完整模型:$\min W(\mathbf{x})$,s.t. $g_1\sim g_8\le0$。
§1.6 习题(做完再展开)
习题1斜弯曲梁:矩形截面 $b\times h$,重量最轻(建立模型)
矩形截面简支梁,跨度 $l$,跨中受铅垂力 $F_y$ 与水平力 $F_x$,材料许用应力 $[\sigma]$。以梁的重量最轻为目标建立模型。
答案
设计变量 $\mathbf{x}=[b,h]^T$;目标 $\min f=\rho g\,bhl$;强度约束为斜弯曲的组合应力
再加边界约束 $g_2=-b\le0$、$g_3=-h\le0$。若还要求挠度,则补 $g_4=f_{\max}-[f]\le0$。
习题2六角形盒:给定容积,用料最省(建立模型)
设计一个正六棱柱形无盖盒,容积 $V$ 给定,底面正六边形边长 $a$、高 $h$,使表面积(用料)最小。
答案
设计变量 $\mathbf{x}=[a,h]^T$;底面积 $S_{\text{底}}=\dfrac{3\sqrt3}{2}a^{2}$,侧面积 $S_{\text{侧}}=6ah$:
要点:等式约束用体积公式;无盖所以侧面积是 6 个侧面,别写成 12 个。
习题3圆管悬臂梁:$1/4$ 圆管,$G$ 点应力约束(建立模型)
悬臂梁长 $l$,自由端受集中力 $F$,截面为平均直径 $d$、壁厚 $t$ 的圆管,材料许用应力 $[\sigma]$、密度 $\rho$。要求 $G$ 点(危险点)应力不超过许用值,且 $d$ 在 $[d_{\min},d_{\max}]$ 内,使质量最轻。
答案
取 $x=d$(壁厚 $t$ 给定)。目标:
弯矩 $M_G=Fl$,抗弯截面系数 $W=\dfrac{\pi d^{2}t}{4}$(薄壁圆管近似),故
这题的关键是写出 $W$ 与 $M$ 的正确组合;若题目给了具体截面尺寸,直接代 $W=\pi d^2t/4$。
习题4概念快问快答(6 小问)
答案
- 优化设计三要素?设计变量、目标函数、约束条件。
- 什么叫设计变量?设计过程中需要不断修改调整、最终确定的独立参数;可用向量 $\mathbf{x}=[x_1,\dots,x_n]^T$ 表示。
- 目标函数为什么一律写成 min?为了统一算法与判别式;求最大时取 $f=-w$。
- 约束为什么统一写成 $g\le0$?统一“可行”判据 $g_u(\mathbf{x})\le0$,便于程序判断与 K-T 条件书写;$\ge$ 形式乘 $-1$。
- 什么叫设计空间、可行域?$n$ 个设计变量为坐标组成的实空间;满足全部约束的点在设计空间中的活动范围。
- 传统设计与优化设计的区别?传统设计被动地“分析—校核—改参数”,得到的是可行解;优化设计主动地按算法沿改进方向自动搜索,得到最优解。
第 2 章 优化设计的数学基础
对应讲义《第二章 优化设计的数学基础》与第二次作业。真题落点:简答(变化率/等式约束)+ 计算题(K-T 判定 20 分)。
§2.1 方向导数与梯度
设 $l$ 为过 $\mathbf{x}_0$ 的单位方向向量 $\mathbf{l}=[\cos\theta_1,\dots,\cos\theta_n]^T$,则
其中 $\nabla f(\mathbf{x})=\left[\dfrac{\partial f}{\partial x_1},\dots,\dfrac{\partial f}{\partial x_n}\right]^T$ 为梯度,$\varphi$ 是 $\mathbf{l}$ 与梯度的夹角。
| 方向 | 方向导数 | 含义 |
|---|---|---|
| 与梯度同向 $\varphi=0$ | $\|\nabla f\|$(最大) | 函数增长最快的方向 |
| 与梯度反向 $\varphi=\pi$ | $-\|\nabla f\|$(最小) | 最速下降方向(负梯度方向) |
| 与梯度垂直 $\varphi=\pi/2$ | $0$ | 沿等值线切线方向 |
研究变化率的工具:一阶偏导与梯度(方向导数)、二阶偏导与海赛矩阵(曲率、凸性)、泰勒展开(局部近似)。
§2.2 泰勒展开与二次函数矩阵形式(第二次作业 3 的模板)
二次函数(考试最常见):
化矩阵形式的固定做法:对 $f=ax_1^2+bx_1x_2+cx_2^2+dx_1+ex_2+f_0$
§2.3 无约束极值条件(必背)
| $\mathbf{H}$ 的性质 | 结论 |
|---|---|
| 正定 | 极小点 |
| 负定 | 极大点 |
| 不定 | 鞍点(不是极值点) |
| 半正定 / 半负定 | 需进一步判断(可能为弱极值) |
正定判定(答题必须写主子式):各阶顺序主子式 $\Delta_1,\Delta_2,\dots,\Delta_n$ 全部 $>0$。二元时 $\Delta_1=H_{11}>0$ 且 $\Delta_2=H_{11}H_{22}-H_{12}^{2}>0$。
§2.4 凸集、凸函数、凸规划
答题套路:先说明可行域 $D$ 是凸集(如全平面 $\mathbb{R}^n$、线性约束围成),再求 $\mathbf{H}$ 并证明半正定/正定。
§2.5 等式约束:拉格朗日乘子法(2020 简答第 3 题)
问题 $\min f(\mathbf{x})$,s.t. $h_v(\mathbf{x})=0\ (v=1,\dots,l)$,构造
$n+l$ 个方程解 $n+l$ 个未知量($\mathbf{x}$ 与 $\boldsymbol\lambda$)。充分性可回代消元后用二阶导判断,或用加边海赛矩阵。
§2.6 不等式约束:K-T 条件(全卷最值钱的 20 分)
问题
设 $\mathbf{x}^*$ 为约束最优点,$J=\{j\mid g_j(\mathbf{x}^*)=0\}$ 为起作用约束集合,则存在乘子 $\mu_j$ 使
等价的全约束写法(含互补松弛):
几何意义:在约束极小点处,目标函数的负梯度可表示为所有起作用约束梯度的非负线性组合——即 $-\nabla f$ 落在起作用约束梯度张成的锥内。
K-T 判定六步法(真题标准写法,一步 1–2 分)
- 可行性检验:代入全部 $g_j(\bar{\mathbf{x}})$;有 $g_j>0$ → 不可行,直接结论“不是最优解”。
- 找起作用约束:$J=\{j\mid g_j=0\}$;不起作用约束的 $\mu_j=0$。
- 算梯度:$\nabla f(\bar{\mathbf{x}})$、$\nabla g_j(\bar{\mathbf{x}})\ (j\in J)$。
- 列 K-T 方程:$\nabla f+\sum_{j\in J}\mu_j\nabla g_j=\mathbf{0}$,写成分量方程组。
- 解乘子并检验符号:是否全部 $\mu_j\ge0$。
- 结论:可行 + 方程有解 + $\mu\ge0$ → 是 K-T 点(约束极值点);否则说明原因(不可行 / $\mu$ 为负 / 方程无解)。
§2.7 例题(第二次作业标准答案改写,务必自己算一遍)
例1方向导数:$f=x_1^2-x_1x_2+x_2^2+5$ 在 $[1,1]^T$ 沿与 $x_1$ 轴成 $\alpha$ 的方向
题:求上述方向导数,并问 $\alpha$ 为何值时取最大、最小、为零。
答案
偏导:$\dfrac{\partial f}{\partial x_1}=2x_1-x_2$,$\dfrac{\partial f}{\partial x_2}=-x_1+2x_2$。在 $[1,1]^T$ 处 $\nabla f=[1,1]^T$,$\|\nabla f\|=\sqrt2$。
取单位方向 $\mathbf{d}=[\cos\alpha,\sin\alpha]^T$,则
- 最大 $\sqrt2$:$\alpha=\pi/4+2k\pi$($\mathbf{d}$ 与梯度同向);
- 最小 $-\sqrt2$:$\alpha=5\pi/4+2k\pi$(与梯度反向,即最速下降方向);
- 为 0:$\alpha=3\pi/4+k\pi$(与梯度垂直,沿等值线切线)。
易错:忘记把 $\mathbf{d}$ 单位化,直接用 $[1,\tan\alpha]$ 去点乘。
例2无约束极值 + 海赛主子式:$f=2x_1^2+5x_2^2+x_3^2+2x_2x_3+2x_1x_3-6x_2+3$
题:用极值条件求极小点和极值,海赛矩阵判定要有过程。
答案
$\mathbf{H}$ 正定 → 极小点;$f(\mathbf{x}^*)=2+5+4-4-4-6+3=0$。
$\Delta_3$ 用第一行展开:$4(20-4)+2(0-20)=64-40=24$。符号错一处全题白算,务必重算一遍。
例3二次函数矩阵化 + 凸性证明:$f=x_1^2+x_2^2-10x_1-4x_2+60$
题:写成 $f=\frac12\mathbf{X}^T\mathbf{A}\mathbf{X}+\mathbf{B}^T\mathbf{X}+C$,并证明在 $\mathbb{R}^2$ 上是凸函数。
答案
$\nabla f=\mathbf{A}\mathbf{X}+\mathbf{B}$,$\mathbf{H}=\mathbf{A}$ 处处正定($\Delta_1=2>0,\Delta_2=4>0$),故半正定;$\mathbb{R}^2$ 是凸集,由“$\mathbf{H}$ 处处半正定 ⇔ 凸函数”得证(实为严格凸)。
例4拉格朗日乘子法:$f=x_1^2+x_2^2-3x_1x_2$,$h=3x_1+2x_2-62=0$
题:求极值点坐标与极值(第二次作业 4)。
答案
$f(12,13)=144+169-468=-155$。充分性:沿约束消元 $x_2=(62-3x_1)/2$,得 $\dfrac{d^2f}{dx_1^2}=\dfrac{31}{2}>0$ → 极小。
也可以直接说:$\mathbf{H}=\begin{bmatrix}2&-3\\-3&2\end{bmatrix}$ 不定,但沿约束方向二阶导为正,所以是极小。
真题 2020二、计算题:画设计空间 + K-T 判定(20 分)
题:约束优化问题
1. 绘制设计空间、可行域和目标函数等值线图,并标出 $x_A$、$x_B$、$x_C$、$x_D$;
2. 判断这些点中哪些是约束极值点,若不是说明理由,若是用 K-T 条件计算判断;
3. 回答这些点中哪些是局部最优点、哪些是全局最优点;
4. 自己另外指定 4 点,说明其可行性与适用性。
其中 $x_A=\begin{bmatrix}3\\0\end{bmatrix}$,$x_B=\begin{bmatrix}0\\-3\end{bmatrix}$,$x_C=\begin{bmatrix}0\\0\end{bmatrix}$,$x_D=\begin{bmatrix}0\\3\end{bmatrix}$。
① 绘图答案(含示意图)
注意:$f=x_1^2+x_2$ 的等值线是 $x_2=c-x_1^2$——开口向下的抛物线,$c$ 越大抛物线越高;沿 $x_2$ 减小方向函数值减小。
② 逐点 K-T 判定(8 分核心,按六步写)
$\nabla f=\begin{bmatrix}2x_1\\1\end{bmatrix}$,$\nabla g_1=\begin{bmatrix}2x_1\\2x_2\end{bmatrix}$,$\nabla g_2=\begin{bmatrix}1\\1\end{bmatrix}$。
A(3,0)
可行性:$g_1=9+0-9=0$,$g_2=3+0-1=2>0$ → 不可行(在圆上但在直线上方)。结论:不是最优解。
B(0,−3)
可行性:$g_1=0+9-9=0$,$g_2=0-3-1=-4<0$ → 可行。起作用约束 $J=\{1\}$,$\mu_2=0$。
$\nabla f(0,-3)=\begin{bmatrix}0\\1\end{bmatrix}$,$\nabla g_1(0,-3)=\begin{bmatrix}0\\-6\end{bmatrix}$。
可行 + 方程有解 + $\mu_1\ge0$ → 满足 K-T 条件,是 K-T 点。但注意它在圆的最低点,函数值 $f=-3$。
C(0,0)
可行性:$g_1=-9<0$,$g_2=-1<0$ → 可行,无起作用约束。K-T 条件退化为 $\nabla f(0,0)=\mathbf{0}$,而 $\nabla f(0,0)=[0,1]^T\neq\mathbf{0}$ → 不满足 K-T,不是约束极值点。
几何理由:$C$ 是无约束驻点的“候选”但实际上 $\nabla f\ne0$;沿 $-x_2$ 方向还能下降(如 $(-0.3,-0.4)$ 处 $f=-0.31<0$)。
D(0,3)
可行性:$g_1=0$,$g_2=3-1=2>0$ → 不可行。结论:不是最优解。
③ 局部最优 / 全局最优(2 分,用一句话就能证完)
可行域是圆盘被直线切掉一块后的弓形,边界由圆弧($g_1=0$,从 $(0,3)$ 逆时针到 $(2.12,-2.12)$)和直线段($g_2=0$,从 $(-1,2)$ 到 $(2,-1)$)两部分组成;可行域有界闭,最优解一定存在。
关键观察(一行证明):在可行域内 $x_2\ge-3$(圆盘的最低点),于是
等号要同时成立必须 $x_1=0$ 且 $x_2=-3$,即点 $B(0,-3)$,而它恰好可行。所以
结论(按题目三问逐条写):
- 局部最优点:$B(0,-3)$(它同时是全局最优,所以当然是局部最优)。
- 全局最优点:$B(0,-3)$,$f_{\min}=-3$。
- $A(3,0)$、$D(0,3)$ 不可行($g_2=2>0$),$C(0,0)$ 可行但不满足 K-T,均不是最优点。
两个交点为什么不是最优点:$(-1,2)$ 与 $(2,-1)$ 处两约束都起作用,K-T 方程解出 $\mu_1=-\tfrac13<0$,违反乘子非负,故不是 K-T 点;从图上也能看出等值线在这两点还能往 $x_2$ 减小的方向“切进去”。
顺带说明(老师常追问):直线段上 $f=x_1^2+1-x_1$ 的最小值在 $(0.5,0.5)$,$f=0.75$,但它不满足 K-T($\nabla f=(1,1)\ne0$)——因为它还能沿垂直方向往圆内 $x_2$ 更小处走,这也说明K-T 只是必要条件。
④ 自选 4 点,说明可行性与适用性(4 分)
任选 4 点,每点两句:“可行/不可行 + 是否 K-T 点/是否极值点”。例如:
| 自选点 | $g_1$ | $g_2$ | 可行性 | K-T / 结论 |
|---|---|---|---|---|
| $P_1(1,1)$ | $-7$ | $1$ | 不可行 | 直线外,直接排除 |
| $P_2(0.5,0.5)$ | $-8.5$ | $0$ | 可行 | 起作用 $g_2$;$\nabla f=(1,1)=\mu_2(1,1)$ 得 $\mu_2=1\ge0$,但沿法向仍可下降,是 K-T 点却不是极小(说明 K-T 只是必要条件) |
| $P_3(-1,2)$ | $0$ | $0$ | 可行 | 两约束起作用,$\mu_1=-\tfrac13<0$ → 不是 K-T 点 |
| $P_4(-2,-2)$ | $-1$ | $-5$ | 可行 | 无起作用约束、$\nabla f=(-4,1)\ne0$ → 非极值点 |
| $P_5(2,-1)$ | $0$ | $0$ | 可行 | 两约束起作用,$\mu_1=-\tfrac13<0$ → 不是 K-T 点 |
“适用性”就是回答:该点是否满足 K-T 条件、是否为约束极值点、在图上处于什么位置(可行域内部 / 边界上 / 边界外)。
真题 2016四-2:$f=(x_1-10)^2+(x_2-2)^2$ 的 K-T 判定(15 分)
题:约束优化问题的数学模型为
该问题的几何图形如图所示。计算判断 $x_A=\begin{bmatrix}2\\0\end{bmatrix},\ x_B=\begin{bmatrix}0\\4\end{bmatrix},\ x_C=\begin{bmatrix}6\\4\end{bmatrix},\ x_D=\begin{bmatrix}-4\\0\end{bmatrix}$ 是否满足 K-T 条件,并由图形判断这些点中哪些是局部最优点、哪些是全局最优点。
答案(逐点 + 全局最优)
$\nabla f=\begin{bmatrix}2(x_1-10)\\2(x_2-2)\end{bmatrix}$,$\nabla g_1=\begin{bmatrix}4\\-2x_2\end{bmatrix}$,$\nabla g_2=\begin{bmatrix}1\\0\end{bmatrix}$,$\nabla g_3=\begin{bmatrix}0\\-1\end{bmatrix}$。
| 点 | 可行性 | 起作用约束与 K-T 方程 | 结论 |
|---|---|---|---|
| $x_A(2,0)$ | $g_1=-12<0,\ g_2=-4<0,\ g_3=0$:可行 | $J=\{3\}$,$\nabla f=(-16,-4)^T$;$(-16,-4)+\mu_3(0,-1)=0$ 无解(第一分量 $-16\ne0$) | 不是 K-T 点 |
| $x_B(0,4)$ | $g_2=8>0$:不可行 | — | 不是最优解 |
| $x_C(6,4)$ | $g_1=-28<0,\ g_2=0,\ g_3=-4<0$:可行 | $J=\{2\}$,$\nabla f=(-8,4)^T$;$(-8,4)+\mu_2(1,0)=0$ → $\mu_2=8\ge0$,第二分量 $4\ne0$ | 第一分量可配平但第二分量 $4\ne0$ → 不满足 K-T($x_2$ 方向仍需下降) |
| $x_D(-4,0)$ | $g_1=-24<0,\ g_2=-10<0,\ g_3=0$:可行 | $J=\{3\}$,$\nabla f=(-28,-4)^T$;第一分量 $-28\ne0$ 无解 | 不是 K-T 点 |
全局最优点:约束 $g_1\le0$ 即 $x_1\ge\dfrac{x_2^{2}+8}{4}$(抛物线右侧),加上 $x_1\le6,\ x_2\ge0$,可行域是抛物线、直线 $x_1=6$、$x_2=0$ 围成的曲边三角形。目标函数等值线是以 $(10,2)$ 为圆心的圆。$(10,2)$ 不可行($x_1>6$),圆心“投影”到可行域上最近的点是直线 $x_1=6$ 上的 $(6,2)$:
该点 $g_1=-20<0$、$g_2=0$、$g_3=-2<0$,可行;沿可行域内任何方向移动都会使 $(x_1-10)^2$ 增大($x_1$ 只能减小或保持 6),故 全局最优点 $\mathbf{x}^*=(6,2)^T$,$F_{\min}=16$。
四个给定点的函数值:$F(A)=68$、$F(B)=104$、$F(C)=20$、$F(D)=200$,均大于 16,与“都不是全局最优点”一致。
“由图形判断”的答法:等值线是圆,越小越靠近 $(10,2)$;可行域在 $x_1\le6$ 一侧,所以最靠近圆心的可行点就是 $(6,2)$。
§2.8 习题
习题1判断 $f=x_1^2+x_2^2-4x_1+4$ 在约束 $g_1=x_2-x_1-2\le0$、$g_2=x_1^2-x_2+1\le0$、$g_3=-x_1\le0$、$g_4=-x_2\le0$ 下的最优点
提示与答案
无约束极小点 $(2,0)$:$g_2=4-0+1=5>0$ 不可行;$g_1=-4<0$ 可行。故约束最优在 $g_2=0$ 上。代 $x_2=x_1^2+1$,得 $f=x_1^2+(x_1^2+1)^2-4x_1+4$,求导解三次方程取可行根,再比较边界点。
这题是 2016 卷一-2 的变体,练“先判无约束点是否可行,再沿起作用约束找”。
习题2K-T 条件默写 + 几何意义(5 分钟自测)
答案
见 §2.6。默写要点:①梯度条件 $\nabla f+\sum_{j\in J}\mu_j\nabla g_j=0$;②起作用约束 $g_j=0$、其余 $g_j<0$;③$\mu_j\ge0$;④互补松弛 $\mu_jg_j=0$。几何意义:负梯度落在起作用约束梯度张成的凸锥内。
习题3为什么凸规划的 K-T 点就是全局最优点?
答案
凸规划的目标函数与可行域都是凸的,任何局部最优都是全局最优;而 K-T 条件是凸规划的充分必要条件,所以满足 K-T 的点就是全局最优点。反之,非凸问题中 K-T 点只是“候选”,可能不是极值点(本页 2020 真题的 $P_2(0.5,0.5)$ 就是反例:满足 K-T 但沿法向还能下降)。
第 3 章 一维搜索方法
对应讲义《第三章 一维搜索方法》。真题落点:计算题小问(0.618 一至两轮)、算法步骤简答;0.618 法是必保内容。
§3.1 一维搜索在干什么
方向 $\mathbf{d}^k$ 由算法给定,步长 $\alpha_k$ 由一维搜索确定——即求一元函数 $\varphi(\alpha)$ 的极小点。前提:$\varphi(\alpha)$ 在搜索区间内是单峰函数(先降后升,只有一个极小点)。
“最优步长”的理解(2016 简答 1):沿给定方向使目标函数取极小值的步长,满足 $\varphi'(\alpha)=0$;一维搜索的实质就是一元函数求极值。
§3.2 搜索区间的确定:进退法(外推法)
目标:找到“高—低—高”三点 $a<b<c$,使 $\varphi(b)<\varphi(a)$、$\varphi(b)<\varphi(c)$。
- 给定初始点 $\alpha_0$、初始步长 $h$,计算 $\varphi(\alpha_0)$,令 $\alpha_1=\alpha_0+h$。
- 若 $\varphi(\alpha_1)<\varphi(\alpha_0)$:前进,步长加倍 $h\leftarrow2h$,继续向前,直到函数值开始上升。
- 若 $\varphi(\alpha_1)\ge\varphi(\alpha_0)$:反向,$h\leftarrow-h$,再按上一步搜索。
- 取 $[\alpha_{\text{前}},\alpha_{\text{低}},\alpha_{\text{高}}]$ 作为初始区间。
§3.3 区间消去法原理
在 $[a,b]$ 内取两点 $\alpha_1<\alpha_2$,比较 $\varphi(\alpha_1)$、$\varphi(\alpha_2)$:
| 情形 | 保留区间 | 理由 |
|---|---|---|
| $\varphi(\alpha_1)<\varphi(\alpha_2)$ | $[a,\alpha_2]$ | 极小点在 $\alpha_2$ 左侧 |
| $\varphi(\alpha_1)\ge\varphi(\alpha_2)$ | $[\alpha_1,b]$ | 极小点在 $\alpha_1$ 右侧 |
记忆口诀:“留低点所在的一侧”——函数值小的那个试点一定留在新区间里。
§3.4 黄金分割法(0.618 法)★
$y_1=\varphi(\alpha_1)$,$y_2=\varphi(\alpha_2)$:
| 比较 | 新区间 | 复用点 |
|---|---|---|
| $y_1<y_2$ | $[a,\alpha_2]$ | $\alpha_2$ 成为新的 $\alpha_1$(只再算 1 个新点) |
| $y_1\ge y_2$ | $[\alpha_1,b]$ | $\alpha_1$ 成为新的 $\alpha_2$ |
终止条件:$|b-a|\le\varepsilon$(题目通常给 $\varepsilon$)。迭代次数估算 $n\ge\dfrac{\ln[\varepsilon/(b-a)]}{\ln0.618}$(向上取整)。
§3.5 斐波那契法(分数法)
由精度确定试验次数:$\dfrac{b-a}{F_n}\le\varepsilon$;试点
比较规则与 0.618 法相同;$n$ 次试验后区间长度 $\le(b-a)/F_n$,理论收敛比 0.618 法略快。
§3.6 二次插值法(抛物线法)★
前提:$\alpha_1<\alpha_2<\alpha_3$ 且 $y_1>y_2<y_3$(中间低)。用三点拟合抛物线:
区间缩短四种情况:
| 条件 | 新区间取法 |
|---|---|
| $\alpha_p>\alpha_2$ 且 $y_p<y_2$ | $\alpha_1\leftarrow\alpha_2,\ \alpha_2\leftarrow\alpha_p$(舍左端) |
| $\alpha_p>\alpha_2$ 且 $y_p\ge y_2$ | $\alpha_3\leftarrow\alpha_p$(舍右端) |
| $\alpha_p\le\alpha_2$ 且 $y_p<y_2$ | $\alpha_3\leftarrow\alpha_2,\ \alpha_2\leftarrow\alpha_p$(舍右端) |
| $\alpha_p\le\alpha_2$ 且 $y_p\ge y_2$ | $\alpha_1\leftarrow\alpha_p$(舍左端) |
终止:$|\alpha_p-\alpha_2|\le\varepsilon$ 或 $|y_p-y_2|\le\varepsilon$;输出 $\alpha^*=\alpha_p$(若 $y_p<y_2$)否则 $\alpha_2$。
§3.7 一维牛顿法
二阶收敛、快;但要算二阶导、对初值敏感、可能发散。
§3.8 四种方法对比
| 方法 | 用导数 | 每轮计算量 | 收敛速度 | 适用 |
|---|---|---|---|---|
| 0.618 法 | 否 | 1 个新点 | 线性(0.618) | 通用、最稳 |
| 斐波那契法 | 否 | 1 个新点 | 线性(略快) | 已知精度、次数固定 |
| 二次插值法 | 否(用函数值) | 1 个新点 | 较快 | 函数光滑、单峰 |
| 一维牛顿法 | 一、二阶导 | 1 个点 | 二阶 | 光滑、初值好 |
§3.9 例题与真题
例10.618 法两轮:$\varphi(\alpha)=\alpha^2-4\alpha+5$,$[0,3]$
题:用 0.618 法求极小点,迭代两轮($\varepsilon=0.5$)。
答案(表格)
| $k$ | $a$ | $b$ | $\alpha_1$ | $\alpha_2$ | $y_1$ | $y_2$ | 比较 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 3 | 1.146 | 1.854 | 1.729 | 1.021 | $y_1>y_2$ |
| 1 | 1.146 | 3 | 1.854 | 2.292 | 1.021 | 1.085 | $y_1<y_2$ |
| 2 | 1.146 | 2.292 | 1.584 | 1.854 | 1.173 | 1.021 | $y_1>y_2$ |
第 2 轮后区间 $[1.584,2.292]$,$|b-a|=0.708>0.5$;继续第 3 轮得区间 $[1.854,2.292]$,长度 $0.438\le0.5$,取 $\alpha^*\approx2.02$(精确值 2,$\varphi_{\min}=1$)。
注意:第 1 轮 $\alpha_1=1.146$ 被舍掉、$\alpha_2=1.854$ 复用为新 $\alpha_1$;每轮只算一个新点。
例2二次插值一轮:$\varphi(\alpha)=(a-2)^2+1$,三点 $\alpha=0,1,3$
答案
$y_1=5,\ y_2=2,\ y_3=2$。
$\alpha_p=2>\alpha_2=1$,$y_p=\varphi(2)=1<y_2=2$ → 舍左端:$\alpha_1\leftarrow1,\ \alpha_2\leftarrow2$,新区间 $[1,3]$,$\alpha_p=2$ 恰为精确极小点。
真题 2016三-2:黄金分割法求 $\varphi(\alpha)=\alpha+20/\alpha$ 的极小点(一次迭代)
题:试用黄金分割法求函数 $\varphi(\alpha)=\alpha+\dfrac{20}{\alpha}$ 的极小点和极小值,设搜索区间 $[a,b]=[0.2,1]$(迭代一次即可)。
答案(原卷表格版)
因 $\varphi(\alpha_1)>\varphi(\alpha_2)$,故舍去 $[a,\alpha_1]$,新区间为 $[\alpha_1,b]=[0.5056,1]$。
| 迭代序号 | $a$ | $\alpha_1$ | $\alpha_2$ | $b$ | $y_1$ | 比较 | $y_2$ |
|---|---|---|---|---|---|---|---|
| 0 | 0.2 | 0.5056 | 0.6944 | 1 | 40.0626 | > | 29.4962 |
| 1 | 0.5056 | 0.6944 | 0.8111 | 1 | 29.4962 | > | 25.4890 |
第二轮:$\alpha_2=0.5056+0.618\times0.4944=0.8111$,$\varphi=25.4890<29.4962$,舍 $[0.5056,0.6944]$,新区间 $[0.6944,1]$。
理论最优(供验算):$\varphi'=1-\dfrac{20}{\alpha^2}=0\Rightarrow\alpha^*=\sqrt{20}=4.4721\notin[0.2,1]$——注意该函数在 $[0.2,1]$ 上单调递减,区间内无驻点,所以迭代只会把区间往右端缩。考场若被问“极小点”,应指出精确极小点在 $\alpha=\sqrt{20}$,一次迭代只是缩小了区间。
真题 2016三-3:牛顿法求 $f=16x_1^2+25x_2^2+5$ 的极小点
题:用牛顿法求目标函数 $f(\mathbf{X})=16x_1^2+25x_2^2+5$ 的极小点,设 $\mathbf{X}^{(0)}=[2,2]^T$。
答案
$f(\mathbf{X}^{(1)})=5$,一次迭代即达极小点 $\mathbf{X}^*=[0,0]^T$,$f_{\min}=5$。
二次函数 + 正定常海赛 → 基本牛顿法一步到位;这就是“牛顿法二次收敛”的最直观例子。
§3.10 习题
习题10.618 法一轮:$\varphi(\alpha)=\alpha^2-6\alpha+10$,$[0,4]$
答案
$\alpha_1=0+0.382\times4=1.528$,$\alpha_2=0+0.618\times4=2.472$;$\varphi(1.528)=3.171$,$\varphi(2.472)=1.271$。$y_1>y_2$ → 舍 $[0,1.528]$,新区间 $[1.528,4]$,复用 $\alpha_1\leftarrow2.472$,新 $\alpha_2=1.528+0.618\times2.472=3.055$。
精确极小点 $\alpha=3$,$\varphi_{\min}=1$。
习题2二次插值:三点 $(0,1),(1,6),(3,26)$
答案
$c_1=\dfrac{26-1}{3}=8.333$,$c_2=\dfrac{\frac{6-1}{1}-8.333}{1-3}=1.667$,$\alpha_p=\dfrac12\left[0+3-\dfrac{8.333}{1.667}\right]=-1$。
$\alpha_p<\alpha_2$ 且 $y_p=\varphi(-1)=1-\dfrac{10}{3}+1=-1.333<y_2=6$ → 舍右端:$\alpha_3\leftarrow\alpha_2=1,\ \alpha_2\leftarrow\alpha_p=-1$,新区间 $[-1,1]$。
这三点恰好落在 $\varphi=\alpha^2+\frac{10}{3}\alpha+1$ 上,其顶点 $\alpha=-5/3=-1.667$;用三点拟合的抛物线顶点是 $-1$,下一轮会继续逼近。
习题3进退法:$\varphi(\alpha)=(\alpha-3)^2$,$\alpha_0=0$,$h=1$
答案
$\varphi(0)=9$,$\varphi(1)=4<9$ → 前进,$h=2$,$\alpha=2$:$\varphi(2)=1<4$ → 继续,$h=4$,$\alpha=6$:$\varphi(6)=9>1$ → 停止。得到“高—低—高”三点 $0,2,6$,初始区间 $[0,6]$。
若第一步 $\varphi(\alpha_1)\ge\varphi(\alpha_0)$,则反向 $h\leftarrow-h$ 再搜。
第 4 章 无约束优化方法
对应讲义《第四章 无约束优化方法》与第三次作业。真题落点:简答必考"列举无约束优化方法并说明搜索方向思想";计算题考牛顿/共轭梯度/DFP 的一轮或两步。本章按"为什么这么定方向 → 算法步骤 → 算例 → 优缺点"展开,每个方法都能独立读懂。
§4.1 统一迭代格式、终止准则与收敛速度
① 所有方法都是同一个迭代公式
区别只在两件事:方向 $\vec d^k$ 怎么取(这是"方法的灵魂")、步长 $\alpha_k$ 怎么定(精确一维搜索 / 固定步长 / 经验公式)。所以"介绍一种新方法"永远只说清这两件事。
② 算法必备三要素 + 一个终止准则
| 要素 | 作用 | 怎么取 |
|---|---|---|
| 初始点 $\vec x^0$ | 迭代起点 | 凭经验或粗略设计值;凸问题不影响结果,非凸时影响收敛到哪个局部极小 |
| 搜索方向 $\vec d^k$ | 决定往哪走 | 各方法的核心差别(负梯度 / 牛顿 / 共轭 / 坐标轴 / 连线) |
| 步长 $\alpha_k$ | 决定走多远 | 精确一维搜索(最常用)、加速步长、固定步长 |
| 终止准则 | 什么时候停 | 三选一,见下 |
③ 三个终止准则(考试常问"用什么判断收敛")
实际程序常两个条件同时满足才停,防止"函数值变化小而点还在跑"。作业 3-1 用梯度准则($\varepsilon=0.1$),作业 4-1 用相对区间/相对函数差。
④ 收敛速度(填空、简答都可能考)
设迭代收敛到 $\vec x^*$,记误差 $\vec e^k=\vec x^k-\vec x^*$:
| 阶 | 定义 | 含义 | 哪些方法 |
|---|---|---|---|
| 线性收敛 | $\dfrac{\|\vec e^{k+1}\|}{\|\vec e^{k}\|}\le c,\ 0<c<1$ | 误差按固定比例缩小(每步"打个折") | 最速下降、坐标轮换 |
| 超线性收敛 | $\dfrac{\|\vec e^{k+1}\|}{\|\vec e^{k}\|}\to0$ | 比线性快、比二次慢 | 变尺度法(DFP) |
| 二次收敛 | $\|\vec e^{k+1}\|\le c\|\vec e^{k}\|^2$ | 误差平方级缩小(有效数字翻倍) | 牛顿法、阻尼牛顿 |
⑤ 分类
| 大类 | 方法 | 搜索方向 | 所用信息 |
|---|---|---|---|
| 用导数 | 最速下降法 | $\vec d=-\nabla f$ | 一阶 |
| 牛顿型法(基本 / 阻尼) | $\vec d=-\mathbf H^{-1}\nabla f$ | 二阶 | |
| 共轭梯度法 | $\vec d=-\vec g+\beta\vec d^{k-1}$ | 一阶 | |
| 变尺度法 DFP | $\vec d=-\mathbf H_k\vec g$($\mathbf H_k\approx\mathbf H^{-1}$) | 一阶 | |
| 不用导数 | 坐标轮换法 | $\vec e_1,\vec e_2,\dots,\vec e_n$ | 只算函数值 |
| Powell 法 | 逐轮连线,构造共轭方向 | 只算函数值 | |
| 单形替换法(单纯形法) | 按比较结果反射 / 收缩 | 只算函数值 |
⑥ 一个全章通用的工具:二次函数的精确步长
本章例题几乎都是二次函数,沿 $\vec d$ 作精确一维搜索时不必展开 $\varphi(\alpha)$,直接用公式:
来源:令 $\varphi(\alpha)=f(\vec x^k+\alpha\vec d^k)$,对二次函数 $\varphi'(\alpha)=(\vec d^k)^T\nabla f(\vec x^k+\alpha\vec d^k)=(\vec d^k)^T(\vec g^k+\alpha\mathbf H\vec d^k)=0$,解出 $\alpha$。
若 $\vec d^k$ 取负梯度,上式化为 $\alpha=\dfrac{(\vec g^k)^T\vec g^k}{(\vec g^k)^T\mathbf H\vec g^k}$——最速下降法的标准步长。
§4.2 最速下降法(梯度法)
① 为什么取负梯度方向——用第 2 章的结论一句话说清
第 2 章推出方向导数 $\dfrac{\partial f}{\partial d}=\|\nabla f\|\cos\varphi$($\varphi$ 是方向与梯度的夹角)。要"下降最快"就是让这个值最小:$\cos\varphi=-1$,即 $\varphi=\pi$,方向与梯度反向。
② 算法步骤
- 给定 $\vec x^0$、$\varepsilon$,令 $k=0$;
- 算 $\vec g^k=\nabla f(\vec x^k)$,若 $\|\vec g^k\|<\varepsilon$ 停;
- 取 $\vec d^k=-\vec g^k$;
- 沿 $\vec d^k$ 作一维搜索求 $\alpha_k$;
- $\vec x^{k+1}=\vec x^k+\alpha_k\vec d^k$,$k\leftarrow k+1$,回 2。
③ 算例:$f=x_1^2+4x_2^2$,$\vec x^0=[1,1]^T$(看"锯齿"和"慢")
$\nabla f=[2x_1,\ 8x_2]^T$,$\mathbf H=\begin{bmatrix}2&0\\0&8\end{bmatrix}$,$\vec g^0=[2,8]^T$,$\vec d^0=[-2,-8]^T$。
继续迭代(每轮都用精确步长):
| $k$ | $x_1$ | $x_2$ | $f$ | $\|\vec g\|$ |
|---|---|---|---|---|
| 0 | 1.0000 | 1.0000 | 5.0000 | 8.246 |
| 1 | 0.7385 | −0.0462 | 0.5538 | 1.522 |
| 2 | 0.1108 | 0.1108 | 0.0613 | 0.913 |
| 3 | 0.0818 | −0.0051 | 0.0068 | 0.169 |
| 4 | 0.0123 | 0.0123 | 0.00075 | 0.101 |
| 6 | 0.0014 | 0.0014 | $9\times10^{-6}$ | 0.019 |
看 $x_2$ 的符号:$+1\to-0.046\to+0.111\to-0.005\to+0.012\dots$ 来回穿越,这就是锯齿;而且越靠近最优点步子越小,收敛明显变慢。
④ 为什么会锯齿——相邻两步方向必然正交
$\alpha_k$ 由精确一维搜索确定,意味着 $\varphi'(\alpha_k)=0$,而
又因为 $\vec d^k=-\vec g^k$、$\vec d^{k+1}=-\vec g^{k+1}$,所以 $\vec d^{k+1}\perp\vec d^k$。每两步就走成一个直角,在狭长的椭球等值线里只能沿"峡谷"两侧来回撞,这就是收敛慢的根本原因。
数值验证:上例 $\vec d^0=[-2,-8]$、$\vec d^1=[-1.4769,0.3692]$,点乘 $2.9538-2.9538=0$ ✓。
⑤ 优缺点(简答标准句)
缺点:①靠近极小点呈锯齿形振荡,只有线性收敛,越接近越慢;②等值线为狭长椭球(变量量级相差大 / 病态 $\mathbf H$)时尤其慢;③不能利用二阶信息,无法一步到位。
改进思路(后面三个方法都是这么来的):把 $\vec d=-\vec g$ 换成 $\vec d=-\mathbf A\vec g$,$\mathbf A$ 取 $\mathbf H^{-1}$ 就是牛顿法,取 $\mathbf H_k\approx\mathbf H^{-1}$ 就是变尺度法,取"共轭组合"就是共轭梯度法。
§4.3 牛顿型法
① 方向是怎么推出来的——对二次近似求驻点
在 $\vec x^k$ 处作二阶泰勒展开(第 2 章 §2.2):
把右边这个二次近似当成真函数,求它的极小点(对 $\vec x$ 求导令为零):
所以牛顿方向就是"直接跳到二次模型的极小点"的方向:
对比最速下降:最速下降只用"坡度",牛顿法还用了"曲率"($\mathbf H$)。等值线是狭长椭球时,$\mathbf H^{-1}$ 会把负梯度方向"拉正",一步指向椭圆中心。
② 为什么二次函数一步到位
二次函数的二阶泰勒展开就是它本身(三阶及以上导数为零),所以近似没有误差,牛顿方向直指真极小点,取 $\alpha=1$ 恰好落到点上。"二次函数一步到位"是牛顿法的标志性结论,简答常考。
③ 基本牛顿法算法
- 给 $\vec x^0$、$\varepsilon$,$k=0$;
- 算 $\vec g^k$,若 $\|\vec g^k\|<\varepsilon$ 停;
- 算 $\mathbf H(\vec x^k)$ 并求逆(或解线性方程组 $\mathbf H\vec d=-\vec g$,省去求逆);
- $\vec x^{k+1}=\vec x^k+\vec d^k$(步长固定为 1);
- $k\leftarrow k+1$,回 2。
④ 算例:$f=x_1^2+2x_2^2-2x_1x_2-4x_1$,$\vec x^0=[1,1]^T$
$f(4,2)=16+8-16-16=-8$。一步收敛(因为函数是二次的)。
求逆的小技巧:$2\times2$ 矩阵 $\begin{bmatrix}a&b\\b&d\end{bmatrix}^{-1}=\dfrac{1}{ad-b^2}\begin{bmatrix}d&-b\\-b&a\end{bmatrix}$,考试最常用,务必记牢。
⑤ 基本牛顿法 vs 阻尼牛顿法
| 基本牛顿法 | 阻尼牛顿法 | |
|---|---|---|
| 方向 | $-\mathbf H^{-1}\vec g$ | 同左 |
| 步长 | 固定 $\alpha=1$ | 沿方向作一维搜索求 $\alpha_k$ |
| 是否保证下降 | 不保证($\mathbf H$ 非正定时可能上升) | 保证(一维搜索取最优步长) |
| 二次函数 | 一步到极小 | 一步到极小(搜索得 $\alpha=1$) |
| 每步代价 | 算 $\mathbf H$ + 求逆 | 再加一次一维搜索 |
阻尼牛顿为什么能保证下降:牛顿方向满足 $(\vec d^k)^T\vec g^k=-(\vec g^k)^T\mathbf H^{-1}\vec g^k<0$(只要 $\mathbf H$ 正定,$\mathbf H^{-1}$ 也正定),所以它是下降方向;再沿线作一维搜索取最优点,函数值必减。
⑥ $\mathbf H$ 不正定 / 奇异怎么办(简答"牛顿法的缺点及改进"必答)
- 加阻尼(一维搜索):即使方向不下降也能靠步长救回来;
- 修正 $\mathbf H$:$\mathbf H+\mu\mathbf I$($\mu$ 足够大使它正定),工程上常用;
- 改用伪逆 $\mathbf H^{+}$($\mathbf H$ 奇异时,如作业 4-3 那道四次函数在极小点处 $\det\mathbf H=0$);
- 换方法:改用变尺度法($\mathbf H_k$ 始终保持正定)。
⑦ 优缺点
缺点:①要算二阶导($n^2$ 个元素)并求 $n\times n$ 矩阵逆,计算量与存储量大;②$\mathbf H$ 必须正定,否则方向可能不是下降方向;③$\mathbf H$ 奇异时无法求逆;④对非二次函数只在极小点附近才好用(所以才要阻尼)。
一句话对比:最速下降"只看坡度",牛顿"坡度 + 曲率",所以牛顿快;但牛顿"每次都要重新量一遍曲率",代价高。变尺度法就是在两者之间折中。
§4.4 共轭方向与共轭方向法
① 定义(务必写全三个条件:$\mathbf H$ 对称正定、两个非零方向、内积为零)
$n$ 个方向两两共轭:$(\vec d^{i})^T\mathbf H\vec d^{j}=0$,$i\ne j$,称为一组 $\mathbf H$-共轭方向。
② 几何意义:正交的"推广"
- $\mathbf H=\mathbf I$ 时,共轭条件退化成 $(\vec d^0)^T\vec d^1=0$,就是普通正交;
- 一般 $\mathbf H$ 时,先在坐标系里做变换 $\vec y=\mathbf H^{1/2}\vec x$,把等值椭球变成圆,共轭方向在新坐标里就是正交方向;
- 直观说法:沿共轭方向搜索,一个方向上的最优性不会被后一个方向破坏——所以 $n$ 个方向走完就到极小点,不返工。
③ 核心性质(简答必写)
证明思路(考场上写三句就够):设 $\vec x^*=\vec x^0+\sum_{i=0}^{n-1}\alpha_i\vec d^i$($\vec d^i$ 构成 $\mathbb R^n$ 的基),两边左乘 $(\vec d^j)^T\mathbf H$:
而第 $j$ 步的一维搜索恰好保证 $(\vec d^j)^T\mathbf H(\vec x^*-\vec x^0)=\alpha_j(\vec d^j)^T\mathbf H\vec d^j$,所以每个 $\alpha_j$ 都取到了最优值,第 $n$ 步必然等于 $\vec x^*$。
④ 三种产生方法(简答"如何产生"要全部答出)
| 方法 | 做法 | 公式 |
|---|---|---|
| ① 两点连线法 | 从 $\vec x^0$ 沿 $\vec d^0$ 搜到 $\vec x^1$,再沿 $\vec d^1$ 搜到 $\vec x^2$,则连线方向与前两方向共轭 | $\vec d^2=\vec x^2-\vec x^1$ |
| ② 共轭梯度递推 | 用梯度的模方比作为组合系数,把负梯度"偏转"成共轭方向 | $\vec d^k=-\vec g^k+\beta_{k-1}\vec d^{k-1}$,$\beta=\dfrac{\|\vec g^k\|^2}{\|\vec g^{k-1}\|^2}$ |
| ③ Gram-Schmidt 共轭化 | 从任意线性无关组(如坐标轴 $\vec e_i$)出发,逐个"减去它在已有共轭方向上的分量" | $\vec d^k=\vec e_k+\sum_{i<k}\beta_{ki}\vec d^i$,$\beta_{ki}=-\dfrac{(\vec d^i)^T\mathbf H\vec e_k}{(\vec d^i)^T\mathbf H\vec d^i}$ |
Powell 法不用导数,靠"逐轮连线"实现第 ① 种,是同一思想的无导数版本。
§4.5 共轭梯度法(F-R 法)
① 公式与"偏转"的含义
怎么理解:第一步和最速下降一样(负梯度);从第二步起,把新的负梯度往旧方向上偏一点(加 $\beta\vec d^{k-1}$),偏到"与旧方向关于 $\mathbf H$ 共轭"为止。$\beta$ 就是"偏多少"的系数。
$\beta$ 的另一种写法(Dixon 形式,两者对二次函数等价):$\beta_{k-1}=\dfrac{(\vec g^{k})^{T}\mathbf H\vec d^{k-1}}{(\vec d^{k-1})^{T}\mathbf H\vec d^{k-1}}$。
② 算法步骤
- 给 $\vec x^0$、$\varepsilon$;算 $\vec g^0$,$\vec d^0=-\vec g^0$,$k=0$;
- 一维搜索求 $\alpha_k$,$\vec x^{k+1}=\vec x^k+\alpha_k\vec d^k$;
- 算 $\vec g^{k+1}$,若 $\|\vec g^{k+1}\|<\varepsilon$ 停;
- 算 $\beta_k=\|\vec g^{k+1}\|^2/\|\vec g^k\|^2$;
- $\vec d^{k+1}=-\vec g^{k+1}+\beta_k\vec d^{k}$;$k\leftarrow k+1$,回 2。
重置策略:非二次函数时理论上 $\beta$ 公式不再保证共轭,实践中每 $n$ 步(或每 $n+1$ 步)把方向重置为 $-\vec g$,防止"方向退化"。
③ 为什么它比最速下降好
| 最速下降 | 共轭梯度 | |
|---|---|---|
| 方向 | $-\vec g^k$ | $-\vec g^k+\beta\vec d^{k-1}$ |
| 相邻方向关系 | 必然正交 ⇒ 锯齿 | 关于 $\mathbf H$ 共轭 ⇒ 不返工 |
| 二次函数 | 无穷多步(理论极限才到) | $n$ 步到极小 |
| 所需信息 | 一阶导 | 一阶导(不需要 $\mathbf H$,$\alpha$ 可用一维搜索) |
严格说公式里写到了 $\mathbf H$,但实际计算用一维搜索求 $\alpha$,不需要真的知道 $\mathbf H$——这正是它的价值。
④ 优缺点
缺点:①对非二次函数要重置,且 $\beta$ 公式在非二次时只是近似;②一维搜索精度要求高(搜索不准会破坏共轭性);③数值稳定性不如变尺度法。
§4.6 变尺度法(DFP)★
① 要解决什么问题
| 方法 | 方向 | 问题 |
|---|---|---|
| 最速下降 | $-\mathbf I\,\vec g$ | $\mathbf I$ 太"粗糙",锯齿、慢 |
| 牛顿法 | $-\mathbf H^{-1}\vec g$ | $\mathbf H^{-1}$ 很"准",但要算二阶导 + 求逆,代价高 |
| 变尺度 | $-\mathbf H_k\vec g$ | 让 $\mathbf H_k$ 逐步逼近 $\mathbf H^{-1}$:起点用 $\mathbf I$(便宜),终点用 $\mathbf H^{-1}$(准确),中间自动过渡 |
所以变尺度法又叫拟牛顿法:不去算真正的 $\mathbf H^{-1}$,而是用一个"越用越像"的 $\mathbf H_k$ 代替。
② 拟牛顿条件($\mathbf H_k$ 该满足什么)
对二次函数,梯度差与点位差满足严格关系 $\vec g^{k+1}-\vec g^k=\mathbf H(\vec x^{k+1}-\vec x^k)$,即 $\mathbf H\vec s_k=\vec y_k$。既然希望 $\mathbf H_k$ 近似 $\mathbf H^{-1}$,就要求
③ 校正公式(DFP)与记忆法
符号含义:$s$=step(点位差),$y$=梯度差。写反是本章最常见的错。
④ 算法步骤
- 给 $\vec x^0$、$\varepsilon$,$\mathbf H_0=\mathbf I$,$k=0$;
- 算 $\vec g^k$,若 $\|\vec g^k\|<\varepsilon$ 停;
- $\vec d^k=-\mathbf H_k\vec g^k$;
- 一维搜索求 $\alpha_k$,$\vec x^{k+1}=\vec x^k+\alpha_k\vec d^k$;
- 算 $\vec s_k=\vec x^{k+1}-\vec x^k$、$\vec y_k=\vec g^{k+1}-\vec g^k$;
- 按公式更新 $\mathbf H_{k+1}$;$k\leftarrow k+1$,回 2。
第 4 步对二次函数也可用 $\alpha_k=-\dfrac{(\vec d^k)^T\vec g^k}{(\vec d^k)^T\mathbf H\vec d^k}$;不知道 $\mathbf H$ 时用一维搜索。
⑤ 三条重要性质
- 保持对称正定:只要 $\mathbf H_k$ 对称正定且 $\vec s^T\vec y>0$,$\mathbf H_{k+1}$ 仍对称正定,因此 $\vec d^k$ 恒为下降方向;
- $n$ 步收敛:对 $n$ 维二次函数,$\mathbf H_n=\mathbf H^{-1}$,$n$ 步(有时 $n+1$ 步)到极小;
- 超线性收敛:非二次函数时比共轭梯度稳定、比牛顿省。
补充:BFGS 是 DFP 的对偶形式(对 $\mathbf H_k$ 与 $\mathbf B_k\approx\mathbf H$ 互为对偶),实际更常用;考试写 DFP 即可,提到 BFGS 是加分项。
§4.7 坐标轮换法与 Powell 法
一、坐标轮换法
思想:不动导数,把 $n$ 元问题化成 $n$ 个一元问题——依次沿 $\vec e_1,\vec e_2,\dots,\vec e_n$ 作一维搜索,一轮走 $n$ 步,反复直到收敛。
算例:$f=x_1^2+x_2^2-x_1x_2-2x_1$,$\vec x^0=[0,0]^T$
第 1 轮:沿 $\vec e_1$(固定 $x_2=0$):$f=x_1^2-2x_1$,$\dfrac{df}{dx_1}=2x_1-2=0\Rightarrow x_1=1$ → $\vec x=[1,0]^T$。
沿 $\vec e_2$(固定 $x_1=1$):$f=1+x_2^2-x_2-2=x_2^2-x_2-1$,$\dfrac{df}{dx_2}=2x_2-1=0\Rightarrow x_2=0.5$ → $\vec x=[1,0.5]^T$。
第 2 轮:沿 $\vec e_1$:$f=x_1^2+0.25-0.5x_1-2x_1=x_1^2-2.5x_1+0.25\Rightarrow x_1=1.25$ → $[1.25,0.5]$。
沿 $\vec e_2$:固定 $x_1=1.25$,$f=1.5625+x_2^2-1.25x_2-2.5=x_2^2-1.25x_2-0.9375\Rightarrow x_2=0.625$ → $[1.25,0.625]$。
精确最优:$\nabla f=[2x_1-x_2-2,\ 2x_2-x_1]=\vec 0\Rightarrow x_1=\frac43,x_2=\frac23$,$f^*=-\frac43\approx-1.3333$。
| 轮 | 点 | $f$ | $\|\vec x^k-\vec x^*\|$ |
|---|---|---|---|
| 0 | $(0,\ 0)$ | $0$ | $1.491$ |
| 1 | $(1,\ 0.5)$ | $-1.250$ | $0.373$ |
| 2 | $(1.25,\ 0.625)$ | $-1.328$ | $0.0932$ |
| 3 | $(1.3125,\ 0.65625)$ | $-1.3330$ | $0.0233$ |
| 5 | $(1.33203,\ 0.66602)$ | $-1.33333$ | $0.00146$ |
| 最优 | $(1.3333,\ 0.6667)$ | $-1.33333$ | $0$ |
每轮误差大致按 1/4 缩小($0.373\to0.0932\to0.0233\to\dots$),是典型的线性收敛:虽然单调下降、不会跑偏,但越走越慢。原因是沿坐标轴交替搜索时,两步之后才"折"向最优点,变量相关越强(交叉项越大)越慢。
加速步长法(改进)
一轮结束后,沿"起点 → 终点"连线再搜一次(这个方向自动带上了变量间的相关性):
二、Powell 法(不用导数的共轭方向法)
核心:用"逐轮搜索的连线"自动构造共轭方向,并把贡献最小的旧方向换掉。
二维步骤:
- 从 $\vec x^0_0$ 出发,沿 $\vec e_1$ 搜到 $\vec x^0_1$,再沿 $\vec e_2$ 搜到 $\vec x^0_2$;
- 令新方向 $\vec d=\vec x^0_2-\vec x^0_0$,沿 $\vec d$ 搜索得 $\vec x^0_3$;
- 用 $\vec d$ 替换函数值下降最少的那个旧方向,开始下一轮;
- 重复,直到 $\|\vec x^{k+1}-\vec x^k\|<\varepsilon$。
算例(同上函数,$\vec x^0=[0,0]^T$)
第 1 轮:沿 $\vec e_1$ 得 $[1,0]$,沿 $\vec e_2$ 得 $[1,0.5]$,连线方向 $\vec d=[1,0.5]$。
沿 $\vec d$ 搜索:$\vec x=[1+\alpha,\ 0.5+0.5\alpha]^T$,代入得
为什么一轮就到:二维二次函数只需 2 个共轭方向,而 $\vec e_1$ 与"连线方向"正好构成一组共轭方向。
方向替换规则(考试细节)
每轮比较各方向上的函数值下降量 $\Delta_i=f(\vec x_{i-1})-f(\vec x_i)$,把$\Delta$ 最小的那个方向删掉,用新连线方向补上。改进 Powell 法另外设了判据(避免"方向线性相关"导致退化),简答提到即可。
优缺点
缺点:每轮 $n+1$ 次一维搜索,计算量大;可能出现方向退化(改进 Powell 法处理);不如用导数的方法快。
§4.8 七方法对比(背这张表)
| 方法 | 搜索方向 $\vec d^k$ | 需几阶导 | 收敛性 | 每步代价 | 特点/适用 |
|---|---|---|---|---|---|
| 最速下降 | $-\vec g^k$ | 一阶 | 线性,慢 | 1 次一维搜索 | 简单、必下降;锯齿,只宜前期 |
| 基本牛顿 | $-\mathbf H^{-1}\vec g^k$ | 二阶 | 二阶 | 算 $\mathbf H$ + 求逆 | 二次函数一步到位;$\mathbf H$ 须正定 |
| 阻尼牛顿 | $-\mathbf H^{-1}\vec g^k$ | 二阶 | 二阶 | 求逆 + 一维搜索 | 保证下降,最稳的牛顿型 |
| 共轭方向法 | $\mathbf H$-共轭方向 | 二阶(用 $\mathbf H$) | $n$ 步二次 | 1 次一维搜索 | 理论方法,用于导出其它算法 |
| 共轭梯度 | $-\vec g^k+\beta\vec d^{k-1}$ | 一阶 | $n$ 步二次 | 1 次一维搜索 | 存储最省,适合大规模 |
| 变尺度 DFP | $-\mathbf H_k\vec g^k$ | 一阶 | 超线性 + $n$ 步二次 | 存 $n\times n$ 矩阵 + 一维搜索 | 综合最好,工程最常用 |
| 坐标轮换 | $\vec e_1,\dots,\vec e_n$ | 无 | 线性,可能很慢 | 每轮 $n$ 次一维搜索 | 最简单;变量相关时差 |
| Powell | 逐轮连线(共轭化) | 无 | $n$ 轮二次 | 每轮 $n+1$ 次一维搜索 | 不用导数中最好的 |
§4.9 简答标准答案(直接背)
Q1:列举无约束优化方法,并简述其搜索方向产生的思想(2020 简答 4)★
答:可分为用导数与不用导数两类。
(一)用导数:① 最速下降法——取负梯度方向,因为该方向函数值下降最快(方向导数为最小值);② 牛顿法——用海赛矩阵的逆修正负梯度,$\vec d=-\mathbf H^{-1}\vec g$,利用了二阶曲率信息;③ 共轭梯度法——在负梯度方向上叠加前一搜索方向,构造与 $\mathbf H$ 共轭的方向,$\vec d^k=-\vec g^k+\beta\vec d^{k-1}$;④ 变尺度法(DFP)——用对称正定矩阵 $\mathbf H_k$ 逐步逼近 $\mathbf H^{-1}$,$\vec d=-\mathbf H_k\vec g$,兼具梯度法的低代价与牛顿法的快收敛。
(二)不用导数:⑤ 坐标轮换法——依次沿各坐标轴方向搜索,把多变量问题化为一系列单变量问题;⑥ Powell 法——通过逐轮搜索的连线构造共轭方向,并替换"贡献最小"的旧方向。
答题格式建议:先写"分两类",再每条一句"方向怎么来",最后补一句各自适用场合。
Q2:什么是共轭方向?如何产生?
定义:设 $\mathbf H$ 对称正定,若非零方向 $\vec d^0,\vec d^1$ 满足 $(\vec d^0)^T\mathbf H\vec d^1=0$,称二者关于 $\mathbf H$ 共轭。
为什么要它:沿 $n$ 个共轭方向依次作精确一维搜索,$n$ 维二次函数至多 $n$ 步到达极小点,且不会破坏前面已取得的最优性。
产生方法:①两点连线法:$\vec d^2=\vec x^2-\vec x^1$;②共轭梯度递推:$\beta=\|\vec g^k\|^2/\|\vec g^{k-1}\|^2$;③Gram-Schmidt 共轭化:从任意线性无关组出发逐个扣除已有共轭分量;④Powell 法用逐轮连线实现无导数版本。
Q3:最速下降法与牛顿法各有何优缺点?
最速下降:每次沿负梯度,程序简单、只算一阶导、每步必下降、全局收敛;但相邻方向正交,靠近极小点呈锯齿形,仅线性收敛,等值线狭长时极慢。
牛顿法:用 $\mathbf H^{-1}$ 修正方向,二阶收敛,二次函数一步到位;但需计算二阶导与 $n\times n$ 矩阵逆,$\mathbf H$ 非正定时方向可能不是下降方向,$\mathbf H$ 奇异时无法求逆,故实际多用阻尼牛顿(加一维搜索保证下降)。
结论句:牛顿法"快但贵且挑条件",最速下降"稳但慢";实际算法(变尺度、共轭梯度)都是在两者之间取折中。
Q4:为什么说共轭梯度法是最速下降法的一种改进?
共轭梯度法第一步就取负梯度方向,与最速下降法完全相同;从第二步起,它在负梯度方向基础上叠加前一搜索方向(系数 $\beta$),把新方向"偏转"成与前面方向关于 $\mathbf H$ 共轭的方向。这样避免了相邻方向正交造成的锯齿,使 $n$ 维二次函数 $n$ 步即可收敛,而计算量仍只是一阶导。所以它保留了最速下降法"便宜"的优点,克服了"慢"的缺点。
Q5:什么叫线性收敛、二次收敛、超线性收敛?各方法属于哪类?
以误差 $\vec e^k=\vec x^k-\vec x^*$ 衡量:线性收敛指 $\|\vec e^{k+1}\|\le c\|\vec e^k\|$($0<c<1$),误差按固定比例缩小;超线性收敛指比值 $\to0$;二次收敛指 $\|\vec e^{k+1}\|\le c\|\vec e^k\|^2$,有效数字每步翻倍。
最速下降、坐标轮换为线性收敛;变尺度法为超线性收敛;牛顿法、阻尼牛顿为二次收敛;共轭梯度对二次函数为 $n$ 步(有限步)收敛。
Q6:为什么要求 $\mathbf H_k$(或 $\mathbf H$)对称正定?
因为 $\vec d=-\mathbf A\vec g$ 要是下降方向,必须 $(\vec d)^T\vec g=-(\vec g)^T\mathbf A\vec g<0$,这等价于 $\mathbf A$ 正定(对任意非零 $\vec g$)。所以牛顿法要求 $\mathbf H$ 正定、DFP 要保证 $\mathbf H_k$ 正定,否则方向可能使函数值上升。
Q7:Powell 法与坐标轮换法有什么区别?
两者都不用导数。坐标轮换法只沿固定的坐标轴 $\vec e_i$ 搜索,变量相关时会在"脊线"上来回蹭,收敛很慢;Powell 法在每轮 $n$ 次坐标搜索后,再沿起点到终点的连线作一次搜索,并把这个连线方向留作下一轮的搜索方向(替换掉贡献最小的旧方向),从而逐步构造出共轭方向,对二次函数 $n$ 轮内收敛,明显快于坐标轮换。
§4.10 例题与真题
例1阻尼牛顿法:$f=4(x_1+1)^2+2x_2^2+x_3^2+x_1+x_2+10$,$\mathbf{x}^0=\mathbf{0}$,$\varepsilon=0.1$
题:第三次作业 1。要求写出完整迭代过程。
答案(一步收敛)
$\nabla f(\mathbf{0})=[9,1,0]^T$,$\|\nabla f\|=\sqrt{82}=9.055>0.1$;$\mathbf{d}^0=-\mathbf{H}^{-1}\nabla f(\mathbf{0})=[-9/8,-1/4,0]^T$。
沿 $\mathbf{d}^0$ 一维搜索:$\varphi(\alpha)=\frac{83}{16}\alpha^2-\frac{83}{8}\alpha+14$,$\varphi'(\alpha)=0\Rightarrow\alpha_0=1$。
本题是二次函数、$\mathbf{H}$ 正定,最佳步长恰为 1,所以阻尼牛顿与基本牛顿一步结果相同。答题时把 $\varphi(\alpha)$ 的化简写出来(这是采分点)。
例2共轭梯度法:$f=\frac12x_1^2+x_2^2$,$\mathbf{x}^0=[2,1]^T$(第三次作业 2)
答案(两步到极小)
$\nabla f=[x_1,2x_2]^T$。第一步:$\mathbf{g}^0=[2,2]^T$,$\mathbf{d}^0=[-2,-2]^T$,$\varphi(\alpha)=6\alpha^2-8\alpha+3\Rightarrow\alpha_0=\frac23$,$\mathbf{x}^1=[\frac23,-\frac13]^T$。
$\mathbf{g}^1=[\frac23,-\frac23]^T$,$\beta_0=\dfrac{\|\mathbf{g}^1\|^2}{\|\mathbf{g}^0\|^2}=\dfrac{8/9}{8}=\dfrac19$,$\mathbf{d}^1=[-\frac89,\frac49]^T$。
第二步一维搜索得 $\alpha_1=\frac34$,$\mathbf{x}^2=[0,0]^T$,$\mathbf{g}^2=\mathbf{0}$,$f_{\min}=0$。
校核共轭性:$(\mathbf{d}^0)^T\mathbf{H}\mathbf{d}^1=[-2,-2]\begin{bmatrix}1&0\\0&2\end{bmatrix}[-\frac89,\frac49]^T=0$。
例3DFP 法:$f=4x_1^2+x_2^2-40x_1-12x_2+136$,$\mathbf{x}^0=[8,9]^T$(第三次作业 3)
答案(一轮更新 + 第二次搜索)
$\nabla f=[8x_1-40,\,2x_2-12]^T$,$\mathbf{H}=\operatorname{diag}(8,2)$。
$k=0$:$\mathbf{g}^0=[24,6]^T$,$\mathbf{d}^0=[-24,-6]^T$;$\varphi(\alpha)=2340\alpha^2-612\alpha+45\Rightarrow\alpha_0=0.131$,$\mathbf{x}^1=[4.862,8.215]^T$。
$\mathbf{d}^1=-\mathbf{H}_1\mathbf{g}^1=[0.280,-4.482]^T$,$\alpha_1=0.494$,$\mathbf{x}^2=[5.000,6.000]^T$,$\mathbf{g}^2=\mathbf{0}$,$f_{\min}=0$。
若继续迭代可得 $\mathbf{H}_2=\operatorname{diag}(0.125,0.5)=\mathbf{H}^{-1}$,验证“$n$ 步后尺度矩阵收敛到海赛逆”。
真题 2016三-1:最速下降法(负梯度方向 + 一维搜索)求 $f=8x_1^2+4x_1x_2+5x_2^2$,$\mathbf{x}^0=[10,10]^T$
题:试用最速下降法(沿负梯度方向作一维搜索)求 $f(\mathbf{X})=8x_1^2+4x_1x_2+5x_2^2$ 的最优解,$\mathbf{X}^{(0)}=[10,10]^T$。
答案(原卷数据完整复原)
① 初始点函数值与梯度:
② 沿负梯度方向作一维搜索:
$f(\mathbf{X}^1)=\min_\alpha f[\mathbf{X}^0-\alpha\nabla f(\mathbf{X}^0)]=\min_\alpha\varphi(\alpha)$,令 $\varphi'(\alpha_0)=0$。展开得
③ 第一次迭代结果:
此后按同样过程继续迭代($\mathbf{X}^{1}$ 处再求梯度、再作一维搜索),直到 $\|\nabla f\|\le\varepsilon$。本题精确最优解在 $\mathbf{X}^*=[0,0]^T$,$f_{\min}=0$。
方法要点:①$\mathbf{d}^0=-\nabla f(\mathbf{X}^0)$;②$\alpha_0$ 由 $\varphi'(\alpha)=0$ 解出,不能直接取 1;③$\mathbf{X}^1=\mathbf{X}^0+\alpha_0\mathbf{d}^0$;④用 $\|\nabla f\|$ 判收敛。
§4.11 习题
习题1基本牛顿法:$f=x_1^2+2x_2^2-2x_1x_2-4x_1$,$\mathbf{x}^0=[1,1]^T$
答案
$\nabla f=[2x_1-2x_2-4,\ 4x_2-2x_1]^T$,$\mathbf{H}=\begin{bmatrix}2&-2\\-2&4\end{bmatrix}$,$\mathbf{H}^{-1}=\frac14\begin{bmatrix}4&2\\2&2\end{bmatrix}=\begin{bmatrix}1&0.5\\0.5&0.5\end{bmatrix}$。
$\mathbf{g}^0=[-4,2]^T$,$\mathbf{d}^0=-\mathbf{H}^{-1}\mathbf{g}^0=[3,1]^T$,$\mathbf{x}^1=[4,2]^T$,$\mathbf{g}^1=\mathbf{0}$,一步到极小点;$f_{\min}=-8$。
习题2坐标轮换法一轮:$f=x_1^2+x_2^2-x_1x_2-2x_1$,$\mathbf{x}^0=[0,0]^T$
答案
沿 $\mathbf{e}_1$:$f=x_1^2-2x_1\Rightarrow x_1=1$,得 $[1,0]^T$;沿 $\mathbf{e}_2$:$f=1+x_2^2-x_2\Rightarrow x_2=0.5$,得 $[1,0.5]^T$。一轮结束。
精确极小点 $[4/3,2/3]^T$,说明坐标轮换需要多轮(变量相关时收敛慢)。
习题3Powell 法思想口述(30 秒版)
答案
先给 $n$ 个线性无关初始方向(常取坐标轴),每轮依次沿它们作一维搜索;一轮结束后用起点到终点的连线作为新方向替换“贡献最小”的旧方向,再沿新方向搜索一次。这样逐步构造出共轭方向系,对二次函数 $n$ 轮内到极小点。
第 5-6 章 约束优化方法
对应讲义《第六章 约束优化方法》与第四次作业。真题落点:复合形法“反射-收缩”画图 15 分;可行初始点算法 + 框图 15 分;随机方向法简答。
§5.1 方法分类(答题先写这一层)
约束优化方法
├─ 直接法:在可行域内直接搜索(需可行初始点)
│ ├─ 随机方向法
│ ├─ 复合形法
│ ├─ 可行方向法
│ └─ 网格法
└─ 间接法:把约束并入目标函数,化为无约束问题
├─ 惩罚函数法(内点 / 外点 / 混合)
└─ 增广乘子法
直接法只需函数值、适合不等式约束、要求初始点可行;间接法可复用成熟的无约束算法,惩罚函数法最常用。
§5.2 随机方向法
思路:在可行域内,从当前点出发随机产生若干方向,找到可行且下降的方向前进一步,否则缩小步长。
随机方向的产生
共产生 $N$ 个随机单位方向($N$ 常取 50~200)。
可行搜索方向的产生(简答标准答案)
对每个随机方向 $\mathbf{d}_j$ 检验两个条件:①可行性 $\mathbf{x}+\alpha\mathbf{d}_j$ 满足全部 $g_u\le0$;②下降性 $f(\mathbf{x}+\alpha\mathbf{d}_j)<f(\mathbf{x})$。同时满足的方向即为可行搜索方向;若所有方向都不满足,则步长减半 $\alpha\leftarrow0.5\alpha$ 重新搜索,直到 $\alpha$ 小于给定精度。
迭代步骤
- 给定可行初始点 $\mathbf{x}^0$、初始步长 $\alpha$、精度 $\varepsilon$;
- 产生 $N$ 个随机单位方向;
- 逐个检验可行性与下降性,找到则前进;
- 找不到则 $\alpha\leftarrow0.5\alpha$;
- 满足收敛条件(步长足够小或函数值不再下降)停止。
§5.3 复合形法 ★(15 分画图题)
在可行域内构造 $k$ 个顶点的多面体(复合形),不断用新点替换最坏点,使复合形向最优点收缩、收缩到最优点附近。
初始复合形
方法:①人为给定 $k$ 个可行顶点;②给定 1 个可行点,其余用 $\mathbf{x}_j=\mathbf{a}+\mathbf{r}_j(\mathbf{b}-\mathbf{a})$ 随机产生,不可行点向已可行点中心移动 $\mathbf{x}=\mathbf{x}_C+0.5(\mathbf{x}-\mathbf{x}_C)$ 直到可行;③全部由计算机随机生成。
四个基本操作(画图题按这个顺序讲)
- 反射:找最好点 $\mathbf{x}_L$、最坏点 $\mathbf{x}_H$、次坏点 $\mathbf{x}_G$;形心(去掉 $\mathbf{x}_H$ 后其余 $k-1$ 个顶点的中心)
成功条件:$\mathbf{x}_R$ 可行且 $f(\mathbf{x}_R)<f(\mathbf{x}_H)$;否则 $\alpha\leftarrow0.5\alpha$ 重算。
- 扩张(延伸):若 $f(\mathbf{x}_R)<f(\mathbf{x}_C)$,$\mathbf{x}_E=\mathbf{x}_R+\gamma(\mathbf{x}_R-\mathbf{x}_C)$($\gamma=1$);$\mathbf{x}_E$ 可行且更优则用 $\mathbf{x}_E$ 替换 $\mathbf{x}_H$,否则用 $\mathbf{x}_R$。
- 收缩:若反射方向找不到比 $\mathbf{x}_H$ 更好的点,$\mathbf{x}_k=\mathbf{x}_H+\beta(\mathbf{x}_C-\mathbf{x}_H)$($\beta=0.5$);若 $f(\mathbf{x}_k)<f(\mathbf{x}_H)$ 则替换。
- 压缩:若收缩仍失败,全部顶点向最好点靠拢 $\mathbf{x}_j=0.5(\mathbf{x}_L+\mathbf{x}_j),\ j\ne L$。
计算步骤(答题编号)
- 选 $k$($n+1\le k\le2n$),构造初始复合形;
- 计算各顶点函数值,找 $\mathbf{x}_L,\mathbf{x}_H,\mathbf{x}_G$;
- 求形心 $\mathbf{x}_C$ 并检查可行性;不可行则重新界定上下限 $\mathbf{a}=\mathbf{x}_L,\mathbf{b}=\mathbf{x}_C$ 重建;
- 反射,必要时缩小 $\alpha$,直到反射成功构成新复合形;
- 判断收敛(顶点函数值之差或复合形尺寸小于精度),否则回到 2。
§5.4 惩罚函数法 ★
内点法(障碍函数法)
适用:只有不等式约束,迭代点必须在可行域内部。
惩罚因子序列 $r^0>r^1>\dots\to0$;初始点必须严格可行($g_j<0$);最优解从可行域内部逼近边界;不能处理等式约束。
外点法(惩罚函数法)
适用:不等式 + 等式约束,迭代点可在可行域外。
惩罚因子序列 $M^0<M^1<\dots\to\infty$;初始点任意;迭代点从外部逼近边界;收敛慢、$M$ 过大易病态。
混合法
内点处理不等式、外点处理等式;$r\downarrow0$、$M\uparrow\infty$。
计算步骤(三种通用)
- 选初始点、初始惩罚因子、缩小/放大系数 $c$;
- 构造 $\Phi$;
- 用无约束方法求 $\Phi$ 的极小点 $\mathbf{x}^*(r)$;
- 检查收敛(相邻两次 $\mathbf{x}^*$ 之差或惩罚项足够小),否则 $r\leftarrow cr$(或 $M\leftarrow cM$),以当前 $\mathbf{x}^*$ 为初值重复 3。
§5.5 可行初始点的产生(15 分,含框图)
网格法
- 估计各变量上下限 $[a_i,b_i]$;
- 每个区间均分若干等份形成网格点;
- 逐点代入全部约束检验;
- 第一个满足全部约束的点即为可行初始点;
- 若无可行点,加密网格或调整上下限。
随机抽样法(Monte Carlo)
- 给定区间 $[a_i,b_i]$ 与最大抽样次数 $N$;
- $\mathbf{x}_i=a_i+r_i(b_i-a_i)$,$r_i$ 为 $(0,1)$ 均匀随机数;
- 检验约束,可行则输出,否则重复;
- 超过 $N$ 次仍不可行 → 扩大区间或放宽约束。
画图要点:菱形判断框、是/否两条分支、循环箭头回到“产生候选点”、必须有次数判断(否则死循环)。
§5.6 方法对比
| 方法 | 类型 | 初始点 | 适用约束 | 特点 |
|---|---|---|---|---|
| 随机方向法 | 直接 | 必须可行 | 不等式 | 简单,效率一般 |
| 复合形法 | 直接 | 必须可行 | 不等式 | 不用导数,稳健 |
| 内点法 | 间接 | 严格可行 | 仅不等式 | 解在可行域内 |
| 外点法 | 间接 | 任意 | 不等式 + 等式 | 从外部逼近 |
| 混合法 | 间接 | 不等式需内点 | 全部 | 综合两者 |
§5.7 例题与真题
例1复合形法一轮:$f=(x_1-4)^2+(x_2-4)^2$,$0\le x_1,x_2\le3$
题:三顶点 $\mathbf{x}_1=(0,0),\mathbf{x}_2=(3,0),\mathbf{x}_3=(0,3)$,$\alpha=1.3$,做一轮反射。
答案
$f=(32,17,17)$ → $\mathbf{x}_L=(3,0)$,$\mathbf{x}_H=(0,0)$,$\mathbf{x}_G=(0,3)$。
形心 $\mathbf{x}_C=\frac12[(3,0)+(0,3)]=(1.5,1.5)$;反射点
$3.45>3$ 越界不可行 → $\alpha\leftarrow0.65$,$\mathbf{x}_R=(1.5,1.5)+0.65(1.5,1.5)=(2.475,2.475)$,可行且 $f=2\times(-1.525)^2=4.65<f(\mathbf{x}_H)=32$ → 用 $\mathbf{x}_R$ 替换 $\mathbf{x}_H$。
新复合形 $\{(2.475,2.475),(3,0),(0,3)\}$。
真题 2020四、绘图并说明复合形法“反射-收缩”迭代过程(15 分)
题:绘图并辅以文字,简要说明复合形法的含有“反射-收缩”策略的迭代过程。
标准答案(两幅图 + 文字判据)
文字说明(按这个顺序写,15 分约 6 个采分点):
- 在可行域内构造 $k$ 个顶点的初始复合形($n+1\le k\le2n$),计算各顶点函数值,找出最好点 $\mathbf{x}_L$、最坏点 $\mathbf{x}_H$、次坏点 $\mathbf{x}_G$。
- 求形心:去掉最坏点,其余 $k-1$ 个顶点的中心 $\mathbf{x}_C=\frac{1}{k-1}\sum_{j\ne H}\mathbf{x}_j$。
- 反射:$\mathbf{x}_R=\mathbf{x}_C+\alpha(\mathbf{x}_C-\mathbf{x}_H)$,$\alpha$ 初值 1.3,$\mathbf{x}_H,\mathbf{x}_C,\mathbf{x}_R$ 三点共线且 $\mathbf{x}_C$ 在中间。
- 判据:若 $\mathbf{x}_R$ 可行且 $f(\mathbf{x}_R)<f(\mathbf{x}_H)$,用 $\mathbf{x}_R$ 替换 $\mathbf{x}_H$,构成新复合形;否则缩小 $\alpha$($\alpha\leftarrow0.5\alpha$)重算。
- 扩张:若 $f(\mathbf{x}_R)<f(\mathbf{x}_C)$,还可沿 $\mathbf{x}_C\to\mathbf{x}_R$ 延伸 $\mathbf{x}_E=\mathbf{x}_R+\gamma(\mathbf{x}_R-\mathbf{x}_C)$。
- 收缩:若反射始终失败(越界或函数值不下降),在 $\mathbf{x}_H$ 与 $\mathbf{x}_C$ 之间取 $\mathbf{x}_k=\mathbf{x}_H+\beta(\mathbf{x}_C-\mathbf{x}_H)$,$\beta=0.5$;成功则替换 $\mathbf{x}_H$,仍失败则压缩:全部顶点向 $\mathbf{x}_L$ 靠拢。
- 重复上述过程,直到各顶点函数值之差或复合形尺寸小于给定精度,取 $\mathbf{x}_L$ 为最优解。
例2内点法:$\min f=x_1^2+x_2^2$,s.t. $g=1-x_1\le0$
答案(对数障碍)
令 $r\to0$($r^0>r^1>\dots\to0$):$x_1\to1$,$x_2\to0$,即 $\mathbf{x}^*=[1,0]^T$,$f^*=1$。
要点:内点法只能处理不等式;初始点必须严格可行($x_1>1$,取在边界 $x_1=1$ 时 $\ln0$ 无定义);$r$ 递减。
例3外点法:同一问题 $\min f=x_1^2+x_2^2$,s.t. $g=1-x_1\le0$
答案
当 $x_1<1$(违反约束)时 $\Phi=x_1^2+x_2^2+M(1-x_1)^2$,令偏导为零:
令 $M\to\infty$($M^0<M^1<\dots$):$x_1\to1$,$\mathbf{x}^*=[1,0]^T$,$f^*=1$。
外点法可同时处理等式与不等式;初始点任意;从可行域外部逼近;$M$ 递增。
真题 2016三:试按混合罚函数法构造罚函数(不用求解),简述基本原理及内点项、外点项的意义
题:$\min F(\mathbf{x})=4x_1-x_2^2-12$,s.t. $g_1=-x_1\le0$,$g_2=-x_2\le0$,$h_1=x_1^2+x_2^2-25=0$。按混合罚函数法构造罚函数(不用求解),并简述罚函数法的基本原理及内点项(障碍项)和外点项(惩罚项)的意义。
答案
构造(内点处理不等式 + 外点处理等式):
注意符号:$g_1=-x_1$、$g_2=-x_2$,故 $-\frac{r}{g_1}=+\frac{r}{x_1}$。要求 $x_1>0,x_2>0$(严格内点)。$r\downarrow0$、$M\uparrow\infty$。
基本原理:把约束优化问题转化为一系列无约束问题——在目标函数上叠加由约束构造的“惩罚/障碍”项,使无约束极小点随参数变化逐步逼近原约束问题的最优点。
内点项(障碍项)的意义:$-r\sum1/g_j$ 在可行域内部取有限值,越靠近约束边界 $g_j\to0^-$ 其值 $\to+\infty$,形成“障碍”,把迭代点挡在可行域内部;$r$ 递减使障碍逐渐减弱,最优点从内部逼近边界。只适用于不等式约束,要求严格可行初始点。
外点项(惩罚项)的意义:$M\sum\{\max[0,g_j]\}^2+M\sum h_v^2$ 在可行域内为零、在违反约束时为正,且违反越多惩罚越大;$M$ 递增使惩罚加重,迫使迭代点从外部逼近可行域边界。可处理等式与不等式,初始点任意。
真题 2016一-8:随机方向法中的可行搜索方向是怎样产生的?
答案
在当前点 $\mathbf{x}$ 处,用均匀随机数产生 $N$ 个分量在 $[-1,1]$ 内的方向向量并单位化;对每个方向 $\mathbf{d}$ 检验:①$\mathbf{x}+\alpha\mathbf{d}$ 满足全部约束(可行性);②$f(\mathbf{x}+\alpha\mathbf{d})<f(\mathbf{x})$(下降性)。同时满足者为可行搜索方向;若 $N$ 个方向均不满足,则步长减半 $\alpha\leftarrow0.5\alpha$ 重新搜索,直到 $\alpha$ 小于给定精度。
真题 2020三、简述产生可行初始点的算法步骤并画出框图(15 分)
答案(网格法/随机抽样法 + 框图)
随机抽样法步骤:①给定各变量区间 $[a_i,b_i]$ 与最大抽样次数 $N$;②产生随机点 $x_i=a_i+r_i(b_i-a_i)$;③检验是否满足全部 $g_u\le0$;④可行则作为初始点输出;⑤否则重复,超过 $N$ 次则扩大区间或放宽约束。
框图:见 §5.5 的流程图(“给定区间 → 产生候选点 → 检验约束 → 可行?→ 是:输出;否:未超次数则回到产生候选点 / 超次数则扩大区间”)。
网格法步骤:①估计上下限;②各区间均分 $m$ 等份形成网格;③逐点检验全部约束;④第一个满足全部约束的点即输出;⑤无可行点则加密网格或调整上下限。
采分:步骤 5 分(每步 1 分)+ 框图 10 分(框、菱形判断、是/否分支、循环、次数判断、输出)。
§5.8 习题
习题1复合形法:$f=x_1^2+x_2^2$,可行域 $0\le x_1,x_2\le2$,三顶点 $(0,0),(2,0),(1,2)$
答案
$f=(0,4,5)$ → $\mathbf{x}_L=(0,0)$,$\mathbf{x}_H=(1,2)$,$\mathbf{x}_G=(2,0)$;形心 $\mathbf{x}_C=\frac12[(0,0)+(2,0)]=(1,0)$;$\mathbf{x}_R=(1,0)+1.3[(1,0)-(1,2)]=(1,-2.6)$ 越界不可行 → $\alpha=0.65$:$\mathbf{x}_R=(1,-1.3)$ 仍不可行 → $\alpha=0.325$:$\mathbf{x}_R=(1,-0.65)$ 仍不可行 → $\alpha=0.1625$:$\mathbf{x}_R=(1,-0.325)$ 仍不可行……
说明本例反射方向恰指向边界外,会一直缩小 $\alpha$;此时按策略转收缩:$\mathbf{x}_k=\mathbf{x}_H+0.5(\mathbf{x}_C-\mathbf{x}_H)=(1,1)$,$f=2<5$,收缩成功。这正是“反射失败 → 收缩”的典型例子。
习题2内点法一轮:$\min f=(x_1-2)^2+x_2^2$,s.t. $x_1-1\ge0$(即 $g=1-x_1\le0$)
答案
$\Phi=(x_1-2)^2+x_2^2-r\ln(x_1-1)$,$\partial\Phi/\partial x_1=2(x_1-2)-r/(x_1-1)=0$,$\partial\Phi/\partial x_2=2x_2=0$。
$r=1$ 时解 $2(x_1-2)(x_1-1)=1$,即 $2x_1^2-6x_1+3=0$,取 $x_1=\frac{3+\sqrt3}{2}=2.366$(>1 可行),$x_2=0$。$r\to0$ 时 $x_1\to2$,即约束最优点 $(2,0)$。
习题3混合法:构造 $\min f=x_1^2+x_2^2$,s.t. $x_1+x_2-2\le0$,$x_1-x_2-1=0$ 的罚函数
答案
要求 $x_1+x_2<2$(严格内点),$r\downarrow0$、$M\uparrow\infty$。
四次作业 · 计算题归纳
计算题基本是四次作业的变形。优先级:老师黑板例题 > 作业题 > PPT 例题——所以第一小节先讲黑板例题与作业的一一对应,第二小节起按最新 Word 原件逐题给完整推导:不只答案,还写清每一步"为什么这么做、数怎么来"。
零、黑板例题(最高优先级)——与作业、真题一一对应
老师黑板上讲过的例题就是命题的直接来源。这 21 张照片归纳成 12 个例题,下表给出它们与作业题、真题的对应关系;后面把网页里原来没有或讲得太简的几道(练习 1、泰勒展开、进退法、共轭梯度、牛顿法两例)补成完整解法。
| # | 黑板例题 | 讲了什么 | 对应作业 | 对应真题 |
|---|---|---|---|---|
| 1 | 第一章 练习 1:$f=(x_1-2)^2+(x_2-5)^2$,圆 $r=4$ | 图解法三问:可行域、无约束/约束最优、加等式约束 | 作业 1-2(同结构换数) | 2020 计算二 |
| 2 | 进退法:$f=x^2-7x+10$,$\alpha_1=0$,$h_0=1$ | 确定初始搜索区间,得 $[2,8]$ | 作业 4-1 的前置步骤 | 一维搜索小题 |
| 3 | 0.618 法:$f=\alpha^2+2\alpha$,$[-3,5]$ | 两轮迭代 + 求 $x^*=-1.472$、$f^*=-0.777$ | 作业 4-1 | 2016 计算 3-4 |
| 4 | 泰勒展开:$f=x_1^3-x_2^3+3x_1^2+3x_2^2-9x_1$ 在 $(1,1)$ | 二次近似化简为 $6x_1^2-12x_1+3x_2$ | 作业 2-2、2-3(求导/矩阵化) | 填空、计算都可能 |
| 5 | 共轭方向:给定 $\mathbf G$,从 $\vec e_0,\vec e_1,\vec e_2$ 作 Gram-Schmidt 共轭化 | $\beta$ 公式、$\vec d^k=\vec e_k+\sum\beta\vec d$ | 作业 3-2、3-3 的理论依据 | 简答"共轭方向如何产生" |
| 6 | 共轭梯度:$f=x_1^2+2x_2^2-4x_1-2x_1x_2$,$\vec x^0=[1,1]^T$ | 两步到 $[4,2]$,$f^*=-8$ | 作业 3-2(同结构换数) | 计算、简答 |
| 7 | 复合形法:$f=x_1^2+x_2^2$,四顶点 $(3,0),(3,1),(2,1),(4,1)$ | 反射失败→缩 $\alpha$→得新复合形 | (作业无,但必考) | 2020 真题四(15 分) |
| 8 | K-T 举例:$f=(x_1-2)^2+x_2^2$,判 $\vec x^*=[1,0]^T$ | 起作用约束 $g_1,g_2$,$\mu_1=\mu_2=1$ | 作业 2-5(三元版) | 2016 四-2、2020 计算二 |
| 9 | 无约束方法分类树 + 基本 Powell(二维/三维) | 用导数/不用导数两大类;Powell 方向替换 | 作业 3-1~3-3 的定位 | 2020 简答第 4 题 |
| 10 | 一维搜索/约束优化方法树(试探法/插值法;直接法/间接法) | 0.618、牛顿、二次插值;随机方向、复合形、惩罚函数 | 作业 4 全章 | 简答、选择 |
| 11 | 牛顿型法:基本/阻尼牛顿公式 + 阻尼牛顿算例 $f=x_1^2+2x_2^2-2x_1x_2-4x_1$,$\vec x^0=[1,1]^T$ | 牛顿方向 + 一维搜索定 $\alpha_0=1$,一步到 $[4,2]$ | 作业 3-1(三元版) | 简答"牛顿法优缺点"、计算一轮 |
| 12 | 基本牛顿算例:$f=x_1^2+x_2^2-x_1x_2-10x_1-4x_2+60$,$\vec x^0=[0,0]^T$ | $\mathbf G^{-1}$ 用 $2\times2$ 公式,一步到 $[8,6]$,$f^*=8$ | 作业 3-1、作业 2-3(同族函数) | 2016 计算 3-3(牛顿法一步) |
黑板例1第一章 练习 1:图解法三问($f=(x_1-2)^2+(x_2-5)^2$,圆半径 4)
题目三问:(1) 画出可行域(阴影);(2) 标出无约束最优 $X^{*(1)}$ 与约束最优 $X^{*(2)}$;(3) 加入等式约束 $h=x_1-x_2=0$ 后,标出 $X^{*(3)}$。
① 无约束最优解——先求、再判是否可行
代约束:$g_1=4+25-16=13>0$ → 不可行(在圆外),图上只能当参照点标出。
② 可行域怎么画
| 约束 | 边界 | 可行侧(代点判断) |
|---|---|---|
| $g_1\le0$ | 圆心原点、半径 4 的圆 | 圆内(代原点 $-16\le0$) |
| $g_2\le0$ | 直线 $x_2=x_1-2$,过 $(2,0)$、$(0,-2)$ | 直线上方(代原点 $-2\le0$) |
| $g_3\le0,\ g_4\le0$ | 两条坐标轴 | 第一象限 |
交集 = 第一象限内、圆内、且在直线 $x_2=x_1-2$ 上方的那块区域。
③ 约束最优解——在圆弧上,令两梯度平行
圆心 $(2,5)$ 在圆外($g_1=13>0$),等值线从圆心向外扩,最先碰到圆弧,故最优在 $g_1=0$ 上且与圆弧相切:
代回圆方程:
校核:$g_2=1.4856-3.7139-2=-4.2283<0$ ✓(不起作用)。
④ 加等式约束 $h=x_1-x_2=0$
$h=0$ 即 $x_1=x_2$(过原点、斜率 1)。与圆联立:
⑤ 三问对比
| 情形 | 最优点 | $F$ | 起作用约束 |
|---|---|---|---|
| 无约束 | $(2,\ 5)$(不可行) | $0$ | 无 |
| 不等式约束 | $(1.4856,\ 3.7139)$ | $1.9187$ | $g_1$ |
| 再加 $h=0$ | $(2.8284,\ 2.8284)$ | $5.4020$ | $g_1,\ h$ |
黑板例2进退法:$f=x^2-7x+10$,$\alpha_1=0$,$h_0=1$,求初始搜索区间
目标:找到"高—低—高"三点 $a<b<c$($\varphi(b)<\varphi(a)$ 且 $\varphi(b)<\varphi(c)$),才能开始 0.618 或二次插值。
进退法到底在干什么(先看这段,再看数)
目标是找到"高—低—高"三点 $a<b<c$(满足 $\varphi(b)<\varphi(a)$ 且 $\varphi(b)<\varphi(c)$),才能开始 0.618 或二次插值。它不是在区间里布三个点,而是"一步一步往前走":
- 先给起点 $\alpha_1$ 和初始步长 $h_0$;
- 往前走一步得 $\alpha_2$,比较 $y_2$ 与 $y_1$:$y_2<y_1$ 说明方向对(函数下降),继续;否则反方向走(这就是"进、退"两个字的来源);
- 再往前走一步得 $\alpha_3$,比较 $y_3$ 与 $y_2$:还在降就把步长加倍(离极小点还远,步子要大),一旦升了就停——此时手上正好是"高—低—高"三点。
第 1 轮:步长 $h=h_0=1$
$y_1>y_2$($10>4$)⇒ 正向搜索(方向对了);$y_3=0<y_2=4$ ⇒ 还在下降 ⇒ 加速推进,步长加倍 $h\leftarrow2$。
第 2 轮:步长 $h=2$
把上一轮的 $\alpha_2=1$、$\alpha_3=2$ 挪过来当本轮的 $\alpha_1$、$\alpha_2$,只新算 $\alpha_3$:
仍 $y_3<y_2$ ⇒ 再加速,$h\leftarrow4$。
注意 $\alpha_2=2$(继承),不是 $\alpha_1+h=1+2=3$。
第 3 轮:步长 $h=4$
这次 $y_2=-2<y_3=18$,出现"上升"⇒ 停止。
汇成一张表(板书就是这个结构)
| 轮 | $\alpha_1\ (y_1)$ 继承 | $\alpha_2\ (y_2)$ 继承/首轮新算 | $\alpha_3\ (y_3)$ 本轮唯一新算的点 | 本轮 $h$ | 判断 |
|---|---|---|---|---|---|
| 1 | $0\ (10)$ | $1\ (4)$ | $1+1=2\ \ (0)$ | $1$ | $y_3<y_2$ → 加倍 $h=2$ |
| 2 | $1\ (4)$ | $2\ (0)$ | $2+2=4\ \ (-2)$ | $2$ | $y_3<y_2$ → 加倍 $h=4$ |
| 3 | $2\ (0)$ | $4\ (-2)$ | $4+4=8\ \ (18)$ | $4$ | $y_2<y_3$ → 停 |
累计走过的增量是 $1,1,2,4$:初始步长 $h_0=1$ 连用两次(第 1 轮要走两步才凑齐三点),之后每确认一次下降就加倍。
取区间
“高—低—高”三点是 $\alpha_1=2$、$\alpha_2=4$、$\alpha_3=8$,故初始搜索区间
校验:真极小点 $x=3.5$($f'=2x-7=0$)确实落在 $[2,8]$ 内 ✓。
黑板例30.618 法:$f(\alpha)=\alpha^2+2\alpha$,$[-3,5]$(黑板上完整两轮)
第 1 轮
$y_1<y_2$ ⇒ 舍右段,新区间 $[-3,\ 1.944]$,复用 $\alpha_1=0.056$ 作新 $\alpha_2$。
第 2 轮
$y_1<y_2$ ⇒ 舍右段,新区间 $[-3,\ 0.056]$。
结果(黑板)
精确解:$\varphi'=2\alpha+2=0\Rightarrow\alpha^*=-1$,$\varphi(-1)=-1$。两轮后近似 $-1.472$,还需继续迭代才逼近 $-1$。
黑板例4泰勒展开:把 $f=x_1^3-x_2^3+3x_1^2+3x_2^2-9x_1$ 在 $(1,1)$ 处简化为二次函数
公式(三项):
第 1 步:算 $f(\vec x_0)$
第 2 步:算梯度并代点
第 3 步:算海赛并代点
第 4 步:代进公式,展开合并
第一项线性项:$0\cdot(x_1-1)+3(x_2-1)=3x_2-3$;第二项二次项:$\frac12\cdot12(x_1-1)^2=6(x_1-1)^2$。合起来
注意常数:$-3-3+6=0$,正好抵消——这是本题的一个巧合,别以为算错。
第 5 步:验算(只在 $\vec x_0$ 附近有效)
| 点 | 原函数 $f$ | 二次近似 $6x_1^2-12x_1+3x_2$ |
|---|---|---|
| $(1,1)$ | $-3$ | $-3$ ✓ |
| $(1.2,1.1)$ | $-2.453$ | $-2.460$ |
| $(0.9,1.1)$ | $-2.642$ | $-2.640$ |
离 $(1,1)$ 越远误差越大(因为丢掉了 $x_1^3,x_2^3$ 项)。这就是"泰勒展开只是局部近似"的含义,也是牛顿法要加一维搜索(阻尼)的原因。
黑板例5共轭方向的产生:Gram-Schmidt 共轭化($\mathbf G$ 给定,从 $\vec e_0,\vec e_1,\vec e_2$ 出发)
问题:给定 $3\times3$ 矩阵 $\mathbf G$(板书写的就是一个具体数值矩阵,字迹部分被擦,不必纠结具体数,方法才是考点),从三个坐标轴方向的单位向量 $\vec e_0=[1,0,0]^T,\ \vec e_1=[0,1,0]^T,\ \vec e_2=[0,0,1]^T$ 出发,构造一组关于 $\mathbf G$ 共轭的方向 $\vec d^0,\vec d^1,\vec d^2$。
递推公式(照抄即可)
为什么这样取 $\beta$
要求 $\vec d^0$ 与 $\vec d^1$ 共轭,即 $(\vec d^0)^T\mathbf G\vec d^1=0$。把 $\vec d^1=\vec e_1+\beta_{10}\vec d^0$ 代进去:
$\beta_{20}$ 同理(让 $\vec d^2$ 与 $\vec d^0$ 共轭);$\beta_{21}$ 让 $\vec d^2$ 与 $\vec d^1$ 共轭。这就是黑板右上角那两行推导的意思。
算完要验
最终应满足 $(\vec d^0)^T\mathbf G\vec d^1=0$、$(\vec d^0)^T\mathbf G\vec d^2=0$、$(\vec d^1)^T\mathbf G\vec d^2=0$——三个内积全为零。
作业 3-2 用的是②,作业 3-3 的 DFP 用的是"用 $\mathbf H_k$ 近似 $\mathbf G^{-1}$"的另一条路。
黑板例6共轭梯度法:$f=x_1^2+2x_2^2-4x_1-2x_1x_2$,$\vec x^0=[1,1]^T$
第 1 步:梯度与初始方向
第 2 步:沿 $\vec d^0$ 一维搜索
第 3 步:共轭系数与第二个方向
第 4 步:再搜索一次,到极小点
二维二次函数,两步到极小——共轭梯度的"$n$ 步二次收敛"。
黑板例7复合形法一轮:$f=x_1^2+x_2^2$,$x_1\ge1,\ x_2\ge0$,四顶点 $(3,0),(3,1),(2,1),(4,1)$
即要求 $x_1\ge1$、$x_2\ge0$。二维取 $k=2n=4$ 个可行顶点。
第 1 步:算各顶点函数值,定 $H$、$G$、$L$
| 顶点 | 坐标 | $f=x_1^2+x_2^2$ | 身份 |
|---|---|---|---|
| $\vec x_1$ | $(3,\ 0)$ | $9$ | — |
| $\vec x_2$ | $(3,\ 1)$ | $10$ | $G$(次坏点) |
| $\vec x_3$ | $(2,\ 1)$ | $5$ | $L$(最好点) |
| $\vec x_4$ | $(4,\ 1)$ | $17$ | $H$(最坏点) |
第 2 步:求形心(去掉 $H$ 后三点平均)
第 3 步:反射($\alpha=1.3$)
板书这一行写的是 $[0.934,\ 0.234]^T$——那是中间值先取三位小数再算的结果,精确值是 $[0.9333,\ 0.2333]^T$,两者等价。
第 4 步:可行性检验——反射失败
把系数缩小(本题取 $\alpha=0.7$;教材一般取 $0.5$),向形心方向收缩重算:
检验:$x_1=1.7333\ge1$ ✓、$x_2=0.4333\ge0$ ✓,可行。
第 5 步:替换最坏点,得新复合形
$f(\vec X^C)=3.19<f(H)=17$ ⇒ 用 $X^C$ 替换 $\vec x_4$,新复合形为
下一轮重新找 $H,G,L$(此时 $H=(3,1)$、$f=10$,形心也会变),继续迭代直到
一轮就把最坏点函数值从 17 压到 3.19,说明"反射—收缩"的威力;真正最优点在 $(1,0)$,$f^*=1$。
判据速查(画图题要写)
| 反射后情形 | 动作 |
|---|---|
| $X^R$ 不可行 | 缩小 $\alpha$(取 $0.5\alpha$ 或经验值)向形心收缩,直到可行 → 得 $X^C$ |
| $f(X^R)<f(L)$ | 反射很成功,可再沿同方向扩张 $X^E=\vec F+2(\vec X^R-\vec F)$ |
| $f(X^R)<f(G)$ | 反射成功,用 $X^R$ 替换 $H$ |
| $f(X^R)\ge f(G)$ | 反射失败,向形心收缩得 $X^C$,可行则替换 $H$ |
| 收缩后仍不可行 | 所有顶点向 $L$ 压缩一半:$\vec x_i\leftarrow\vec L+0.5(\vec x_i-\vec L)$ |
黑板例8K-T 举例:判 $\vec x^*=[1,0]^T$ 是否为 $f=(x_1-2)^2+x_2^2$ 的约束极值点
第 1 步:验可行
全部 $\le0$ ⇒ 可行。
第 2 步:找起作用约束
$g_1=0$、$g_2=0$ 取等号 ⇒ 起作用,$J=\{1,2\}$;$g_3<0$ ⇒ 不起作用,$\mu_3=0$。
第 3 步:算梯度
第 4 步:列 K-T 方程
第 5 步:解乘子并判符号
$\mu_1=1\ge0$、$\mu_2=1\ge0$,全部非负 ✓
第 6 步:结论
$\vec x^*=[1,0]^T$ 满足 K-T 条件,是约束极值点。又因为 $F$ 凸、$g_1$ 凸、$g_2,g_3$ 线性 ⇒ 凸规划 ⇒ 局部最优即全局最优,$F^*=(1-2)^2+0=1$。
易错:①忘了 $\mu_3=0$;②把 $\nabla F$ 的符号与 $-\nabla F$ 搞混导致 $\mu$ 变负;③解出 $\mu$ 后不写"$\ge0$,满足"就下结论。
黑板例9无约束优化方法分类树(2020 简答第 4 题的答案骨架)
黑板上画的树:
- 用导数
- 最速下降法(负梯度方向)
- 牛顿型法:基本牛顿($\vec d=-\mathbf G^{-1}\nabla f$,$\alpha=1$)、阻尼牛顿(牛顿方向 + 一维搜索)
- 共轭梯度法($-\vec g+\beta\vec d$,$\beta=\|\vec g\|^2/\|\vec g^0\|^2$)
- 变尺度法(DFP:$\vec d=-\mathbf H_k\vec g$)
- 不用导数
- 坐标轮换法($\vec e_1,\vec e_2,\dots,\vec e_n$)
- 鲍威尔法 Powell(逐轮连线构造共轭方向)
每种方法的"方向怎么来"(一句话)
| 方法 | 方向 | 一句话思想 |
|---|---|---|
| 最速下降 | $-\nabla f$ | 负梯度是函数下降最快的方向 |
| 基本牛顿 | $-\mathbf G^{-1}\nabla f$ | 用二次模型的极小点作下一个点,$\alpha=1$ |
| 阻尼牛顿 | 同上 + 一维搜索 | 模型只局部可信,步长要搜索 |
| 共轭梯度 | $-\vec g^k+\beta\vec d^{k-1}$ | 在负梯度上叠加前一方向,构造 $\mathbf G$-共轭方向 |
| 变尺度 DFP | $-\mathbf H_k\vec g^k$ | 用 $\mathbf H_k$ 逐步逼近 $\mathbf G^{-1}$,不用求逆 |
| 坐标轮换 | $\vec e_1,\dots,\vec e_n$ | 多变量化成一系列单变量 |
| Powell | 逐轮连线构造 | 不用导数也构造共轭方向 |
基本 Powell(二维):从 $\vec x_0^0$ 出发,沿 $\vec e_1$ 得 $\vec x_1^0$,沿 $\vec e_2$ 得 $\vec x_2^0$;令 $\vec d=\vec x_2^0-\vec x_0^0$,沿 $\vec d$ 再搜索一次得 $\vec x_3^0$;下一轮用 $\vec d$ 替换掉贡献最小的旧方向。
黑板例10一维搜索 / 约束优化 方法树(简答、选择的答案骨架)
① 一维搜索(第三章)
| 大类 | 方法 | 核心思想 | 适用 |
|---|---|---|---|
| 试探法 (只比较函数值) | 0.618 法(黄金分割) | 按黄金比取两点,每轮只算 1 个新点,区间按 0.618 缩 | 单峰函数,最常用 |
| 分数法(Fibonacci)(教材补充,板书未讲) | 按斐波那契数分配试点,给定次数时最优 | 已知最多算几次 | |
| 二分法(教材补充) | 用一阶导数的符号折半 | 导数已知 | |
| 插值法 (用函数值拟合) | 牛顿切线法 | 用抛物线(二次)拟合,取顶点 | 函数光滑 |
| 二次插值法 | 三点定抛物线,取 $x_p$,按四种情况缩区间 | 函数光滑、收敛快 | |
| 三次插值法(教材补充) | 四点定三次曲线求极小 | 精度要求高 |
前置步骤:进退法确定初始搜索区间(见黑板例 2)。
② 约束优化(第五、六章)
| 大类 | 方法 | 核心思想 | 要点 |
|---|---|---|---|
| 直接法 (只算函数值,在可行域内搜索) | 随机方向法 | 随机产生若干方向,取可行且下降的方向走 | 需"可行搜索方向"的判别 |
| 复合形法 | $2n$ 个可行顶点围成复合形,用反射—收缩逼近最优点 | 必须先有可行初始复合形 | |
| 间接法 (把约束并入目标) | 外点法 | $\Phi=f+M\sum[\max(0,g)]^2$,$M\to\infty$ | 点可从外部逼近 |
| 内点法 | $\Phi=f-r\sum\frac{1}{g}$,$r\to0$ | 只用于不等式;需严格内点 | |
| 混合法 | $\Phi=f-r\sum\frac{1}{g}+\frac{1}{\sqrt r}\sum h^2$,$r\to0$ | 不等式+等式都有时用 |
③ 两句话总结(简答结尾用)
考场上若问"约束优化方法有哪些",先答"分直接法与间接法两类",再各举两例,最后补一句"直接法不需要导数但需可行初始点;间接法要把约束并入目标函数"。
黑板例11阻尼牛顿法:$f=x_1^2+2x_2^2-2x_1x_2-4x_1$,$\vec x^0=[1,1]^T$(板书完整过程)
黑板上先写的两个公式(牛顿型法)
板书把海赛矩阵记作 $\mathbf G(\vec x^k)$(很多教材记 $\mathbf H$),两者是同一个东西。牛顿方向统一是
差别只在步长:基本牛顿直接取 $\alpha=1$;阻尼牛顿要沿 $\vec d^k$ 作一维搜索。
第 1 步:求梯度并代点
第 2 步:求海赛矩阵及其逆($2\times2$ 公式)
第 3 步:算牛顿方向
第 4 步:沿 $\vec d^0$ 作一维搜索(这是"阻尼"的关键)
代入目标函数得一元函数:
逐项求导(注意乘积项用链式法则):
为什么恰为 1:函数是二次的,牛顿方向直指极小点,精确一维搜索的最优步长自然等于 1。这正是"二次函数一步到位"。
第 5 步:更新点并判收敛
第 6 步:极值
答:极小点 $\vec x^{*}=[4,2]^T$,极小值 $f^{*}=-8$。
板书要点(考试照写就能拿分)
- 先写清用的是基本还是阻尼牛顿;
- $\mathbf G^{-1}$ 用 $2\times2$ 公式,一行出结果;
- 阻尼牛顿必须写"沿 $\vec d^0$ 作一维搜索",并解出 $\alpha_0$;
- 最后用"$\mathbf G$ 正定"说明是极小(不是极大);
- 代回求 $f^*$。
黑板例12基本牛顿法:$f=x_1^2+x_2^2-x_1x_2-10x_1-4x_2+60$,$\vec x^0=[0,0]^T$
题:试用基本牛顿法求其极小点和极值($\alpha$ 固定为 1,不作一维搜索)。
第 1 步:梯度并代点
第 2 步:海赛矩阵及其逆
$\det\mathbf G=3\ne0$,且 $\Delta_1=2>0$、$\Delta_2=3>0$ ⇒ 正定。
第 3 步:牛顿方向
第 4 步:直接取 $\alpha=1$ 更新
第 5 步:验证梯度为零
第 6 步:极值
答:极小点 $\vec x^{*}=[8,6]^T$,极小值 $f^{*}=8$。
① 基本牛顿(例12):$\alpha$ 固定 1,只算 $\mathbf G^{-1}$ 和一次矩阵乘,步数最少、但有前提——$\mathbf G$ 正定且初始点已在"二次模型可信"的范围内,否则 $\alpha=1$ 可能冲过头甚至上升;
② 阻尼牛顿(例11):多一步一维搜索,保证每步下降,代价是多一次单变量优化。
③ 两题都是一步到最优,因为函数都是二次的——这正是"牛顿法对二次函数一步到位"的两个标准例证。简答里举这两个例子,比空谈优缺点有说服力得多。
一、四次作业 = 十三类题型,一张对照表
| 题型 | 作业原题(分值) | 例题原型(PPT / OCR) | 解法核心 |
|---|---|---|---|
| ① 建模(只写模型) | 作业 1-1(12 分) | 第一章建模五步、梯形槽例题 | 选变量 → 目标函数 → 约束 → 标准形 |
| ② 图解法(三问) | 作业 1-2(14 分) | 第一章图解法、§2.6 几何意义 | 画边界 → 阴影可行域 → 等值线 → 最后接触点 |
| ③ 方向导数 | 作业 2-1 | §2.1 例:$f=x_1^2+x_2^2-4x_1-2x_2+5$ 在 $(0,0)$ | 偏导 → 代点 → 单位化 → 点乘 |
| ④ 无约束极值 | 作业 2-2(10 分) | §2.3 极值条件($\nabla f=0$ + $\mathbf H$ 正定) | 驻点 → $\mathbf H$ 全部顺序主子式 |
| ⑤ 二次型 + 凸性 | 作业 2-3 | §2.2 矩阵形式、§2.4 凸性判定 | $\mathbf A=[2a,b;b,2c]$ → $\mathbf H=\mathbf A$ 正定 → 凸 |
| ⑥ 等式约束 | 作业 2-4 | §2.5 例 2-4:$f=4x_1^2+5x_2^2$,$2x_1+3x_2-6=0$ | 构造 $L$ → $n+l$ 个方程 → 解 $x,\lambda$ |
| ⑦ K-T 判定 | 作业 2-5 | §2.6 举例:$\vec x^*=[1,0]^T$;例 2:$(x_1-2)^2+(x_2-2)^2$ | 可行 → 起作用约束 → 列方程 → 解 $\mu$ → 判 $\mu\ge0$ |
| ⑧ 0.618 法 | 作业 4-1(15 分) | §3.3 例:$\alpha^2+2\alpha$,$[-3,5]$ + 表 3-1 | $\alpha_1=b-0.618(b-a)$,每轮只算 1 个新点 |
| ⑨ 二次插值 | 作业 4-2(20 分) | §3.4 二次插值法步骤 | 三点 → $c_1,c_2$ → $\alpha_p$ → 四种缩短 |
| ⑩ 阻尼牛顿 | 作业 3-1(15 分) | §4.3 例:$f=x_1^2+2x_2^2-2x_1x_2-4x_1$ | $\vec d=-\mathbf H^{-1}\vec g$ → 一维搜索 → $\|\vec g\|<\varepsilon$ |
| ⑪ 共轭梯度 | 作业 3-2(15 分) | §4.5 例:$x_1^2+2x_2^2-4x_1-2x_1x_2$ | $\vec d^0=-\vec g^0$ → $\beta=\|\vec g^k\|^2/\|\vec g^{k-1}\|^2$ |
| ⑫ DFP | 作业 3-3(20 分) | §4.6 DFP 校正公式 + 例题 | $\vec d=-\mathbf H_k\vec g$ → $\vec s,\vec y$ → 校正 $\mathbf H_{k+1}$ |
| ⑬ 混合惩罚 | 作业 4-4(25 分) | §6.5 内点/外点/混合公式 | $-r\sum1/g_j$ + $h^2/\sqrt r$,$r\downarrow0$ |
二、作业 1:建模与图解法(12+14+12+12 分)
作业1-1梯形槽最大容积:只要求写出数学模型(12 分)
题:一块薄板宽 $W=24$ cm、长 100 cm,折成梯形槽(两侧斜边各长 $l$,与水平面夹角 $\theta$),问 $l$、$\theta$ 多大时容积最大。写出优化数学模型即可。
第 1 步:把几何量都用 $l,\theta$ 表示
薄板总宽 24,两侧各斜出一段 $l$,所以底宽是
斜边倾角 $\theta$,则槽深(斜边的竖直投影)和单侧水平投影分别是
于是顶宽 = 底宽 + 两侧水平投影
第 2 步:写截面积(梯形面积 = 上底加下底乘高除 2)
容积 = 截面积 × 槽长 100,所以目标函数是
第 3 步:写约束(为什么是这四条)
$l$ 是"每侧斜边长度",两侧共用薄板 24,所以 $2l<24$,即 $l<12$;$l$ 还要为正。$\theta$ 要在 $0^\circ$ 到 $90^\circ$ 之间(否则不成槽)。
题目只要求这四块:设计变量 $[l,\theta]^T$、目标函数(别漏长度 100)、四条边界约束。
第 4 步(作业答案,顺带全解):令两个偏导为零
$\sin\theta\ne0$(否则槽深为 0),故
再对 $\theta$ 求偏导(注意 $l$ 与 $\theta$ 独立,$A=l\sin\theta\cdot B$,$B=24-2l+l\cos\theta$):
把 $l=\dfrac{12}{2-\cos\theta}$ 代入,此时 $B=24-2l+l\cos\theta=24-l(2-\cos\theta)=24-12=12$,于是
代回:$l=\dfrac{12}{2-0.5}=8$ cm;底宽 $8$、顶宽 $16$、深 $4\sqrt3\approx6.93$ cm;
验算:$A=8\times\frac{\sqrt3}{2}\times(24-16+4)=8\times0.866\times12=83.14$ ✓
重点作业1-2:图解法三问(14 分)——后面两次作业的母题
题目四小问(含分值):(1) 可行域范围,用阴影画出、约束函数标在对应线条上(6 分);(2) 目标函数等值线至少 4 条(2 分);(3) 标出无约束最优解 $\vec x^{*(1)}$ 和约束最优解 $\vec x^{*(2)}$(4 分);(4) 若加入等式约束 $h=3x_1-x_2=0$,标出 $\vec x^{*(3)}$(2 分)。
第 1 步:看懂这个函数长什么样
$f=(x_1-3)^2+(x_2-6)^2$ 是"到定点 $(3,6)$ 的距离平方"。所以:
- 等值线是以 $(3,6)$ 为圆心的同心圆,半径越小、$f$ 越小;
- 无约束最优就是圆心本身 $(3,6)$,$f=0$;
- 有约束时,最优解是"从圆心往外扩,最后碰到可行域的那个圆与可行域的交点"。
第 2 步:画可行域(四条约束各管一边)
| 约束 | 边界 | 可行侧 |
|---|---|---|
| $g_1=x_1^2+x_2^2-9\le0$ | 圆,圆心原点、半径 3 | 圆内(原点是圆心,代入得 $-9\le0$) |
| $g_2=x_1-x_2-1\le0$ | 直线 $x_2=x_1-1$,过 $(1,0)$、$(0,-1)$ | 直线上方(代原点:$0-0-1=-1\le0$) |
| $g_3=-x_1\le0$ | $x_1=0$(纵轴) | 右半平面 |
| $g_4=-x_2\le0$ | $x_2=0$(横轴) | 上半平面 |
四条取交集:第一象限内、圆内、且直线 $x_2=x_1-1$ 上方的那块"弓形"。
第 3 步:(1) 无约束最优解——先看它是否可行
$\nabla f=[2(x_1-3),\ 2(x_2-6)]^T=\vec 0\Rightarrow\vec x=(3,6)$,$f=0$。但它可行吗?
不可行(在圆外)。所以无约束最优解只能作为参照点画在圆外,标 $\vec x^{*(1)}=(3,6)$、$f=0$(注意:图上要标,但它不是本题的解)。
第 4 步:(2) 约束最优解——最优在 $g_1$ 上,用"梯度平行"求
因为圆心 $(3,6)$ 在可行域外,等值线从圆心往外扩时,最先碰到的是圆弧 $g_1=0$(直线 $g_2=0$ 离得远)。所以约束最优必在圆弧上,且在该点等值线与圆弧相切——相切的数学表述就是两个梯度平行:
把两式相除消掉 $\mu_1$($x_1,x_2\ne0$):
几何含义:最优点的 $x_2$ 是 $x_1$ 的两倍,即它落在过原点、斜率 2 的射线上。再代回圆方程:
目标值(把 $x_2=2x_1$ 代回):$f=(x_1-3)^2+(2x_1-6)^2=5(x_1-3)^2$,在 $x_1=3/\sqrt5$ 处
校核另一约束:$g_2=1.3416-2.6833-1=-2.3417<0$,不起作用 ✓;$g_3,g_4$ 也都 $<0$ ✓。
顺带算乘子:K-T 条件写成 $\nabla f+\mu_1\nabla g_1=\vec 0$,取第一分量 $\mu_1=-\dfrac{2(x_1-3)}{2x_1}=\dfrac{3-x_1}{x_1}=\dfrac{3-1.3416}{1.3416}=1.2361>0$ ✓(说明 $-\nabla f$ 落在 $\nabla g_1$ 的正方向上,几何上"想往外走被圆挡住")。
第 5 步:(3) 加等式约束 $h=3x_1-x_2=0$
$h=0$ 即 $x_2=3x_1$(过原点、斜率 3 的直线)。它与圆 $x_1^2+x_2^2=9$ 的交点就是候选:
展开:$\frac{9}{10}[(11-2\sqrt{10})+(19-6\sqrt{10})]=\frac{9}{10}(30-8\sqrt{10})=27-\frac{36\sqrt{10}}{5}\approx14.1553$。
校核:$g_1=0$(在圆上)、$g_2=0.9487-2.8460-1=-2.897<0$、$g_3,g_4<0$,可行 ✓。
第 6 步:三问对比(答题时写这张表最清楚)
| 情形 | 最优点 | $f$ | 起作用约束 | 怎么求的 |
|---|---|---|---|---|
| 无约束 | $(3,\ 6)$ | $0$ | 无(但不可行) | $\nabla f=0$ |
| 只有不等式 | $(1.3416,\ 2.6833)$ | $13.7508$ | $g_1$ | $\nabla f\parallel\nabla g_1$ + 圆方程 |
| 再加等式 $h=0$ | $(0.9487,\ 2.8460)$ | $14.1553$ | $g_1,\ h$ | $h$ 与圆方程联立 |
第 7 步:作图四个采分点
- 坐标系 + 刻度,标出 $x_1,x_2$ 轴;
- 四条边界线:圆 $g_1=0$(半径 3)、直线 $g_2=0$(过 $(1,0),(0,-1)$)、两条坐标轴 $g_3=0,g_4=0$,每条线旁标 $g_1\sim g_4$(题目明确要求);
- 可行域打阴影(第一象限 + 圆内 + 直线上方那块);
- 至少 4 条等值线(同心圆,如 $f=4,9,16,25$),并用箭头标出 $f$ 增大的方向(向外),最后接触点即 $\vec x^{*(2)}$。
作业1-3与优化设计相关的成语(12 分)
题:写三个与优化设计相关的成语或词组(不要用"设计变量、约束函数"这类术语),并一一说明。
三个成语 + 对应知识点
| 成语 | 说明 | 对应本课概念 |
|---|---|---|
| 精益求精 | 在已有可行方案上继续改进参数,使性能进一步提高 | 可行解 → 最优解;迭代改进 |
| 权衡利弊 | 目标之间或目标与约束冲突时,综合比较、选更合理的方案 | 多目标优化、约束冲突 |
| 物尽其用 | 材料、工时、能源有限时提高利用率、获得更大效益 | 约束下的最大化(下料问题) |
答题格式:成语 + 一句解释 +(可选)一句"对应优化设计里的什么"。三个就够,多写不加分。
作业1-4线性规划:Excel 规划求解(12 分)
题:甲产品每件耗材料 9 kg、3 工时、4 kW,获利 100 元;乙产品每件耗 4 kg、10 工时、5 kW,获利 60 元;每天可供材料 363 kg、工时 300、电 200 kW。求最大利润的日产量。
第 1 步:设变量、写模型
第 2 步:顶点法验算(线性规划最优必在顶点)
| 顶点(哪两条边界交点) | $x_1$ | $x_2$ | 是否可行 | $P$ |
|---|---|---|---|---|
| $g_1=0$ 与 $g_3=0$ | $35$ | $12$ | 是($g_2=225\le300$) | $4220$ |
| $g_2=0$ 与 $g_3=0$ | $20$ | $24$ | 是($g_1=276\le363$) | $3440$ |
| $g_1=0$ 与 $g_2=0$ | $31.15$ | $20.65$ | 否($g_3=228>200$) | — |
| $x_2=0$ 与 $g_1=0$ | $40.33$ | $0$ | 是 | $4033$ |
| $x_1=0$ 与 $g_2=0$ | $0$ | $30$ | 是 | $1800$ |
| 原点 | $0$ | $0$ | 是 | $0$ |
最大 $P=4220$,在 $(35,12)$ 取到;此时 $4\times35+5\times12=200$ 恰好把电用完($g_3$ 起作用),材料和工时都还有余量。
Excel 做法:把 $x_1,x_2$ 放在两个单元格(可变单元格),目标格写 $=100x_1+60x_2$,约束格分别写三条消耗式,用"数据 → 规划求解"设"最大值"、添加约束、选"单纯形线性规划",求解后出报告。题目要求截全过程图,别只截最后答案。
三、作业 2:数学基础五连(K-T 是重点)
作业2-1方向导数:$f=x_1^2-x_1x_2+x_2^2+5$ 在 $\vec x_0=[1,1]^T$ 处(完整推导)
题:求 $\vec x_0=(1,1)^T$ 处沿与 $x_1$ 轴成 $\alpha$ 角方向的方向导数,并问:(1) $\alpha$ 为何值时方向导数最大;(2) 最小;(3) 为零。
第 1 步:求梯度(先偏导,再代点)
代入 $(1,1)$:$\dfrac{\partial f}{\partial x_1}=2-1=1$,$\dfrac{\partial f}{\partial x_2}=-1+2=1$,所以
梯度是向量,指向"$f$ 上升最快的方向";它的模 $\sqrt2$ 是"上升最快时每单位长度涨多少"。
第 2 步:把"与 $x_1$ 轴成 $\alpha$ 角"写成单位向量
第 3 步:点乘,得到表达式
给定 $\alpha$ 直接代:$\alpha=0$ 得 $1$;$\alpha=90^\circ$ 得 $1$;$\alpha=180^\circ$ 得 $-1$。
第 4 步:合并成余弦,才能一眼看出最大/最小
来历:$\cos\left(\alpha-\frac{\pi}{4}\right)=\cos\alpha\cos\frac{\pi}{4}+\sin\alpha\sin\frac{\pi}{4}=\dfrac{\cos\alpha+\sin\alpha}{\sqrt2}$,两边乘 $\sqrt2$ 即得。
$\sqrt2$ 是正常数,整个式子由 $\cos(\alpha-\frac{\pi}{4})\in[-1,1]$ 决定。
第 5 步:逐个回答三问
| 问 | 要满足 | 解出 $\alpha$ | 值 | 几何含义 |
|---|---|---|---|---|
| (1) 最大 | $\cos\left(\alpha-\frac{\pi}{4}\right)=1$ | $\alpha=\frac{\pi}{4}+2k\pi$($45^\circ$) | $\sqrt2$ | 与梯度同向,上升最快 |
| (2) 最小 | $\cos\left(\alpha-\frac{\pi}{4}\right)=-1$ | $\alpha=\frac{5\pi}{4}+2k\pi$($225^\circ$) | $-\sqrt2$ | 与梯度反向,最速下降 |
| (3) 为零 | $\cos\left(\alpha-\frac{\pi}{4}\right)=0$ | $\alpha=\frac{3\pi}{4}+k\pi$($135^\circ$ 或 $315^\circ$) | $0$ | 与梯度垂直,沿等值线走 |
第 6 步:走一小步验证(理解为什么是这些数)
$f(1,1)=6$。沿各方向走 $\varepsilon=0.01$,用精确 $f$ 算 $\Delta f$ 再除以 $0.01$:
| 方向 | $\alpha$ | 到达点 | $f$ | $\Delta f/\varepsilon$ | 公式值 |
|---|---|---|---|---|---|
| 沿 $x_1$ 轴 | $0$ | $(1.01,\ 1)$ | $6.0101$ | $\approx1.01$ | $\cos0+\sin0=1$ ✓ |
| 梯度方向 | $\pi/4$ | $(1.00707,\ 1.00707)$ | $6.0142$ | $\approx1.42$ | $\sqrt2\approx1.414$ ✓ |
| 等值线切线 | $3\pi/4$ | $(0.99293,\ 1.00707)$ | $6.00015$ | $\approx0.015$ | $0$ ✓ |
| 负梯度 | $5\pi/4$ | $(0.99293,\ 0.99293)$ | $5.9858$ | $\approx-1.42$ | $-\sqrt2$ ✓ |
$1.01$ 比 $1$ 略大,是因为 $\varepsilon$ 不是无穷小、还有二阶项;$\varepsilon$ 越小越接近。
第 7 步:一句话统一三问
设 $\varphi$ 是 $\vec d$ 与梯度的夹角,则 $\varphi=\alpha-\frac{\pi}{4}$:
$\varphi=0$ 最大($+\sqrt2$)、$\varphi=\pi$ 最小($-\sqrt2$)、$\varphi=\frac{\pi}{2}$ 为零。作业比 PPT 多问的"最小、为零",就是把 $\cos\varphi$ 的三个特殊值各取一遍。
第 8 步:与 PPT 例题(§2.1)对照
PPT:$f=x_1^2+x_2^2-4x_1-2x_2+5$,在 $(0,0)$ 处
PPT 问"变化率最大的方向和数值":
注意 PPT 的 $\vec p$ 是上升最快的方向;"最速下降"是它的反方向,别混。
易错点
- 方向没单位化:拿 $[1,\tan\alpha]^T$ 直接点乘,结果不是方向导数。
- 把梯度方向说成"最速下降":梯度是上升最快,负梯度才下降最快。
- 通解漏写:$\alpha$ 要写 $+2k\pi$ 或 $+k\pi$。
- 辅助角合并错:是 $\sqrt2\cos(\alpha-\frac{\pi}{4})$,不是"加"。
- 算完不检查:$\alpha=0$ 时应等于 $\partial f/\partial x_1=1$。
作业2-2无约束极值 + 海赛判定(10 分):三元二次函数
题:求下式的极小点和极值(海赛矩阵判定要有过程)。
第 1 步:求梯度(逐项偏导,别漏交叉项)
对 $x_1$ 求偏导:$2x_1^2\to4x_1$;$2x_1x_3\to2x_3$;其余项不含 $x_1$($x_2x_3$ 也不含),所以
对 $x_2$:$5x_2^2\to10x_2$;$2x_2x_3\to2x_3$;$-6x_2\to-6$;
对 $x_3$:$x_3^2\to2x_3$;$2x_2x_3\to2x_2$;$2x_1x_3\to2x_1$;
第 2 步:令梯度为零,解三元一次方程组
由 (1):$x_3=-2x_1$。全部约掉 2 后代入 (3):$x_1+x_2+x_3=0\Rightarrow x_1+x_2-2x_1=0\Rightarrow x_2=x_1$。
代入 (2)(同样先约 2):$5x_2+x_3-3=0\Rightarrow5x_1-2x_1=3\Rightarrow3x_1=3\Rightarrow x_1=1$,于是 $x_2=1$,$x_3=-2$。
第 3 步:求海赛矩阵(对梯度再求一次偏导)
逐个算:$\partial(4x_1+2x_3)/\partial x_1=4$、$/\partial x_2=0$、$/\partial x_3=2$;$\partial(10x_2+2x_3-6)/\partial x_1=0$、$/\partial x_2=10$、$/\partial x_3=2$;$\partial(2x_1+2x_2+2x_3)$ 分别得 $2,2,2$。所以
$\mathbf H$ 必须对称:$H_{13}=H_{31}=2$、$H_{23}=H_{32}=2$ ✓。二次函数的海赛是常矩阵,与代哪一点无关。
第 4 步:算三个顺序主子式(这是给分点)
按第一行展开(每个元素乘它的代数余子式,注意 $+,-,+$ 的符号):
三个主子式全 $>0$ ⇒ $\mathbf H$ 正定 ⇒ $\vec x^*$ 是极小点。
第 5 步:把点代回原函数求极值
逐项替换($x_1=1,x_2=1,x_3=-2$):
答:极小点 $\vec x^*=[1,1,-2]^T$,极小值 $F_{\min}=0$。
真题 2016 二-1 只问"求梯度与海赛矩阵",比作业少最后两步。
易错:①$2x_1x_3$ 对 $x_1$ 求导得 $2x_3$(不是 $2x_1$);②$\Delta_3$ 的符号 $+,-,+$;③算完 $\Delta_3$ 忘了回头写"所以正定、所以极小"。
作业2-3二次函数矩阵化 + 凸性证明
题:把 $f=x_1^2+x_2^2-10x_1-4x_2+60$ 写成 $f=\frac12\vec X^T\mathbf A\vec X+\mathbf B^T\vec X+C$,并证明它在 $\mathbb R^2$ 上是凸函数(提示:用海赛矩阵)。
第 1 步:先把 $\frac12\vec X^T\mathbf A\vec X$ 展开,看系数怎么对上
设 $\mathbf A=\begin{bmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{bmatrix}$ 对称($a_{12}=a_{21}$),则
对比 $f$ 的二次项 $1\cdot x_1^2+0\cdot x_1x_2+1\cdot x_2^2$:
这就是公式 $\mathbf A=\begin{bmatrix}2a&b\\b&2c\end{bmatrix}$ 的来源($a,b,c$ 是 $x_1^2,x_1x_2,x_2^2$ 的系数)。
第 2 步:写出 $\mathbf A,\mathbf B,C$
验算:$\frac12\vec X^T\mathbf A\vec X=x_1^2+x_2^2$,$\mathbf B^T\vec X=-10x_1-4x_2$,加 $C=60$ 正是原函数 ✓。
第 3 步:求梯度与海赛
二次函数的 $\mathbf H$ 是常矩阵,等于 $\mathbf A$——这一点在作业 2-2 里已经用过。
第 4 步:证明 $\mathbf H$ 处处正定
主子式全 $>0$ ⇒ $\mathbf H$ 在 $\mathbb R^2$ 上处处正定(当然也半正定)。
第 5 步:套凸性判据(三句话,一句都不能少)
- 定义域 $D=\mathbb R^2$ 是凸集(任两点连线仍在平面内);
- $f$ 有二阶连续偏导(多项式);
- $f$ 的 $\mathbf H$ 处处半正定 $\iff$ $f$ 是凸函数(这是定理)。本题更强:处处正定 ⇒ 严格凸。
结论:$f$ 在 $\mathbb R^2$ 上是(严格)凸函数。
顺带:这个函数的最小值(可作验算)
$\nabla f=\vec0\Rightarrow x_1=5,x_2=2$;$\mathbf H$ 正定 ⇒ 极小点;$f(5,2)=25+4-50-8+60=31$。因为是凸函数,这个局部极小就是全局最小。
易错:$\mathbf A$ 的对角线是 $2a,2c$(不是 $a,c$);只写 $\mathbf H$ 正定却不说"定义域是凸集",会被扣分(凸性 = 凸集 + 凸函数)。
作业2-4拉格朗日乘子法(与 PPT 例 2-4 同构)
第 1 步:构造拉格朗日函数(把约束"并进"目标)
思路:原来要"在一条直线上找最小",现在变成"在平面上找 $L$ 的驻点",直线上的约束由 $\partial L/\partial\lambda=0$ 自动保证。
第 2 步:分别对 $x_1,x_2,\lambda$ 求偏导,令其为零
三个方程、三个未知量 $(x_1,x_2,\lambda)$——这就是"$n+l$ 个方程解 $n+l$ 个未知量"。
第 3 步:消去 $\lambda$,先得到 $x_1,x_2$ 的关系
由 (1) 解 $\lambda=\dfrac{-2x_1+3x_2}{3}$;由 (2) 解 $\lambda=\dfrac{3x_1-2x_2}{2}$。两者相等:
第 4 步:回代约束 (3),解出具体点
第 5 步:代回目标函数求极值
第 6 步:充分性(是极小还是极大?)
由 (3) 解出 $x_2=\dfrac{62-3x_1}{2}$,代回 $f$ 得一元的二次函数:
(验算常数项:$62^2/4=961$ ✓)
答:极值点 $(12,13)$,极小值 $f=-155$。
易错:①$L$ 里 $h$ 的符号(写成 $-\lambda h$ 也能做,只要前后一致);②三个方程必须全列,只列两个解不出;③$\lambda$ 的具体值不影响最优点,别在 $\lambda$ 上纠结太久。
重点作业2-5:K-T 判定(三元四约束,PPT 有两个原例)
题:用 K-T 条件判断 $\vec x^*=[1,2,3]^T$ 是否为下式的最优解。
第 1 步:验可行(不可行就直接结束,别浪费时间)
把 $\vec x^*=(1,2,3)$ 逐条代入:
全部 $\le0$ ⇒ 可行。
第 2 步:找起作用约束
$g_1=0$、$g_2=0$ 取等号 ⇒ 起作用,$J=\{1,2\}$;$g_3,g_4$ 严格小于零 ⇒ 不起作用,对应乘子 $\mu_3=\mu_4=0$(别忘了写这句)。
第 3 步:算梯度(只算 $\nabla f$、$\nabla g_1$、$\nabla g_2$)
第 4 步:列 K-T 方程($-\nabla f=\sum\mu_j\nabla g_j$)
K-T 条件是 $\nabla f+\mu_1\nabla g_1+\mu_2\nabla g_2=\vec0$,移项即 $-\nabla f=\mu_1\nabla g_1+\mu_2\nabla g_2$:
写成分量方程组:
第 5 步:解乘子,并检查是否非负
(3) 只含 $\mu_2$,先解它:$\mu_2=3$。代进 (1):
用 (2) 校核(题目给了三个方程两个未知数,一定有一个是多余校验):
$\mu_1=4.5\ge0$、$\mu_2=3\ge0$,符号全部合格。
第 6 步:下结论
可行 + K-T 方程有解 + 起作用约束的乘子非负 ⇒ $\vec x^*=[1,2,3]^T$ 满足 K-T 条件,是约束极值点(最优解)。
① §2.6"库恩-塔克条件举例":$f=(x_1-2)^2+x_2^2$,$g_1=x_1^2+x_2-1\le0$、$g_2=-x_2\le0$、$g_3=-x_1\le0$,检验 $\vec x^*=[1,0]^T$:$g_1=g_2=0$ 起作用,$-\nabla f=[2,0]^T$,解得 $\mu_1=1,\mu_2=1$,均 $\ge0$ ⇒ 是约束极值点。
② §2.6 例 2:$f=(x_1-2)^2+(x_2-2)^2$ 同约束——这就是 2016 真题四-2 的母题。
作业(三元四约束)只是把二元两约束"加维",六步法一字不改。
易错:①$-\nabla f$ 与 $\nabla f$ 符号搞反,导致 $\mu$ 全负;②忘写 $\mu_3=\mu_4=0$;③梯度代错点($9x_1^2$ 别写成 $9x_1$);④解出 $\mu$ 后不写"$\ge0$,满足"就下结论。
四、作业 3:无约束三大法(15+15+20 分)
作业3-1阻尼牛顿法(15 分):$f=4(x_1+1)^2+2x_2^2+x_3^2+x_1+x_2+10$
初始:$\vec x^{(0)}=[0,0,0]^T$,$\varepsilon=0.1$,用梯度准则 $\|\nabla f\|<\varepsilon$。
第 1 步:求梯度(注意 $4(x_1+1)^2$ 的链式法则)
$4(x_1+1)^2$ 求导:$4\cdot2(x_1+1)\cdot1=8(x_1+1)=8x_1+8$,再加 $x_1$ 的导数 1,得 $8x_1+9$。
第 2 步:求海赛矩阵及逆(本题是对角阵,逆最好求)
为什么 $\mathbf H$ 正定:主子式 $8,32,64$ 全正。这句话要写,否则"$\vec d=-\mathbf H^{-1}\vec g$ 是下降方向"没有依据。
第 3 步:$k=0$,算梯度、判断是否需要迭代
第 4 步:牛顿方向 $\vec d^0=-\mathbf H^{-1}\nabla f$
第 5 步:沿 $\vec d^0$ 作一维搜索(这是"阻尼"的关键,基本牛顿直接取 $\alpha=1$)
设 $\vec x=\vec x^{(0)}+\alpha\vec d^0=\left[-\frac98\alpha,\ -\frac14\alpha,\ 0\right]^T$,代入 $f$:
逐项展开:$4(1-\frac94\alpha+\frac{81}{64}\alpha^2)=4-9\alpha+\frac{81}{16}\alpha^2$;$2\cdot\frac{\alpha^2}{16}=\frac{\alpha^2}{8}$。合并:
第 6 步:更新点并判收敛
第 7 步:求极小值
答:极小点 $\vec x^*=[-1.125,-0.25,0]^T$,极小值 $8.8125$。
本题函数是二次、$\mathbf H$ 正定,最佳步长恰为 1,所以与基本牛顿一步结果相同——答题时要说明这一点(采分点)。
作业3-2共轭梯度法(15 分):$f=\frac12x_1^2+x_2^2$,$\vec x^{(0)}=[2,1]^T$
第 1 步:求梯度、算初始点
第 2 步:第一步取负梯度方向(和梯度法一样)
沿它一维搜索:$\vec x=\vec x^{(0)}+\alpha\vec d^{(0)}=\left[2-2\alpha,\ 1-2\alpha\right]^T$,
第 3 步:算新梯度、共轭系数 $\beta$
$\beta$ 是"新梯度模方 ÷ 旧梯度模方",分子是新、分母是旧,写反是常见错。
第 4 步:构造共轭方向 $\vec d^{(1)}=-\nabla f(\vec x^{(1)})+\beta_0\vec d^{(0)}$
含义:在负梯度基础上"往回偏一点",使新方向与旧方向关于 $\mathbf H$ 共轭(而不是像梯度法那样互相垂直)。
第 5 步:沿 $\vec d^{(1)}$ 再搜索一次
$\vec x=\vec x^{(1)}+\alpha\vec d^{(1)}=\left[\frac23-\frac89\alpha,\ -\frac13+\frac49\alpha\right]^T$。注意第二分量恰好是 "$-t/2$",若令 $t=\frac23-\frac89\alpha$,则
完全平方,最小值在 $t=0$,即 $\alpha_1=\dfrac23\cdot\dfrac98=\dfrac34$,于是
二维二次函数,$n=2$ 步到极小——这就是"$n$ 步二次收敛"。
第 6 步:验证共轭性(可选,但写了显得懂)
说明两方向确实关于 $\mathbf H$ 共轭。
作业3-3DFP 变尺度法(20 分):$f=4x_1^2+x_2^2-40x_1-12x_2+136$,$\vec x^{(0)}=[8,9]^T$
题目要求:过程计算保留 3 位小数。
第 1 步:梯度、海赛、初始方向
取 $\mathbf H_0=\mathbf I$,则 $\vec d^{(0)}=-\mathbf H_0\nabla f(\vec x^{(0)})=\begin{bmatrix}-24\\-6\end{bmatrix}$(此时等价于最速下降)。
第 2 步:沿 $\vec d^{(0)}$ 一维搜索
$\vec x=\left[8-24\alpha,\ 9-6\alpha\right]^T$,代入:
逐块展开:$4(64-384\alpha+576\alpha^2)=256-1536\alpha+2304\alpha^2$;$(9-6\alpha)^2=81-108\alpha+36\alpha^2$;$-320+960\alpha$;$-108+72\alpha$;$+136$。合并
第 3 步:算点位差 $\vec s$、梯度差 $\vec y$
$\vec s$ 是点位差、$\vec y$ 是梯度差,这两个千万别写反。
第 4 步:算两个内积(DFP 公式的分母)
第 5 步:按 DFP 公式校正尺度矩阵
第一项修正:$\vec s\vec s^T=\begin{bmatrix}9.850&2.463\\2.463&0.616\end{bmatrix}$,除以 $80.031$ 得 $\begin{bmatrix}0.1231&0.0308\\0.0308&0.0077\end{bmatrix}$。
第二项修正($\mathbf H_0=\mathbf I$,故 $\mathbf H_0\vec y=\vec y$):$\vec y\vec y^T=\begin{bmatrix}630.396&39.400\\39.400&2.462\end{bmatrix}$,除以 $632.858$ 得 $\begin{bmatrix}0.9961&0.0623\\0.0623&0.0039\end{bmatrix}$。
第 6 步:第二次方向与一维搜索
对二次函数,一维搜索有显式公式($\vec d^T\nabla f=0$):
第 7 步:结论与验算
$\vec x^*=[5,6]^T$,$f^*=4(25)+36-200-72+136=0$。若继续迭代可得 $\mathbf H_2=\operatorname{diag}(0.125,0.5)=\mathbf H_f^{-1}$——验证"$n$ 步后尺度矩阵收敛到海赛逆"。
易错:①$\vec s,\vec y$ 写反;②$\mathbf H_1$ 里一项加、一项减;③$\alpha_1$ 用二次函数的显式公式比重新展开 $\varphi$ 快得多(考场上推荐)。
五、作业 4:一维搜索 + 约束方法(15+20+20+25+20 分)
作业4-10.618 法(15 分):$f=(x-2)^2+3$,$[0,10]$,$\varepsilon=10^{-3}$
题:编程求极小点和极小值。收敛条件:$\left|\dfrac{b-a}{b}\right|<\varepsilon$ 或 $\left|\dfrac{y_2-y_1}{y_2}\right|<\varepsilon$,精度 $0.001$。
第 1 步:理解"每轮只算一个新点"
在 $[a,b]$ 内对称取两点:
比较 $y_1,y_2$:若 $y_1<y_2$,极小点在 $x_2$ 左侧,新区间取 $[a,x_2]$;此时原来的 $x_1$ 恰好落在新区间的 $0.618$ 位置上,可以复用为新 $x_2$,只需再算一个新的 $x_1$。反之取 $[x_1,b]$,复用 $x_2$ 为新 $x_1$。这就是"每轮只算 1 个点"的原因。
第 2 步:首轮计算
$y_1<y_2$ ⇒ 舍掉 $[x_2,b]=[6.18,10]$,新区间 $[0,6.18]$,复用 $x_1=3.82$ 作新 $x_2$,只新算 $x_1=6.18-0.618\times6.18=2.3608$。
第 3 步:逐轮列表(前 5 轮)
| $k$ | $a$ | $b$ | $x_1$ | $x_2$ | $y_1$ | $y_2$ | 保留 |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 10 | 3.8200 | 6.1800 | 6.31240 | 20.47240 | $y_1<y_2$ → $[0,6.18]$ |
| 1 | 0 | 6.1800 | 2.3608 | 3.8200 | 3.13015 | 6.31240 | $y_1<y_2$ → $[0,3.82]$ |
| 2 | 0 | 3.8200 | 1.4592 | 2.3608 | 3.29242 | 3.13015 | $y_1>y_2$ → $[1.4592,3.82]$ |
| 3 | 1.4592 | 3.8200 | 2.3608 | 2.9182 | 3.13015 | 3.84307 | $y_1<y_2$ → $[1.4592,2.9182]$ |
| 4 | 1.4592 | 2.9182 | 2.0166 | 2.3608 | 3.00027 | 3.13015 | $y_1<y_2$ → $[1.4592,2.3608]$ |
第 4 步:收敛判断与结果
每轮检查两个条件:相对区间长度 $\left|\frac{b-a}{b}\right|$、相对函数差 $\left|\frac{y_2-y_1}{y_2}\right|$,满足其一即停。程序在第 9 轮因函数值差 $2\times10^{-5}<10^{-3}$ 停止:
与精确解 $x=2$、$f=3$ 相比误差 $<10^{-3}$,满足精度。
说明:你报告里的 $x^*=2.000733$ 与这里 $2.000898$ 的细微差别,来自"先判区间还是先判函数值"的检查顺序,都合格。
第 5 步:作业附加问——压缩到 $1/10,1/100,1/1000$ 要几轮
每轮区间乘 $0.618$,$n$ 轮后长度变成 $0.618^n(b-a)$,要它 $\le\varepsilon(b-a)$:
| 目标压缩 | $\varepsilon$ | $n\ge$ | 轮次(向上取整) |
|---|---|---|---|
| $1/10$ | $0.1$ | $\ln0.1/\ln0.618=4.78$ | 5 |
| $1/100$ | $0.01$ | $9.57$ | 10 |
| $1/1000$ | $0.001$ | $14.35$ | 15 |
作业4-2二次插值法(20 分):$\varphi=(x+1)(x-2)^2$,$[0,5]$,$\varepsilon=0.01$
第 1 步:为什么用三点插值
0.618 法只用"谁大谁小",收敛是线性的;二次插值用三点的函数值拟合一条抛物线,直接取抛物线的顶点当近似极小点,通常更快。前提:三点呈"中间低"($y_1>y_2<y_3$)。
第 2 步:首轮三点与系数
取 $x_1=a=0$、$x_2=\frac{a+b}{2}=2.5$、$x_3=b=5$:
满足 $4>0.875<54$ ✓。拟合抛物线 $p(x)=a_0+a_1x+a_2x^2$,用差商求系数:
抛物线顶点($p'=0$):
第 3 步:按"四种情况"缩短区间
比较 $x_p$ 与中点 $x_2$、$y_p$ 与 $y_2$:这里 $x_p=1.389<2.5$ 且 $y_p=0.8921>y_2=0.875$ ⇒ $x_p$ 在中点左侧、但函数值更高,说明极小点在 $x_p$ 右边,故令 $a\leftarrow x_p=1.389$,新区间 $[1.389,5]$。
| $x_p$ 位置 | $y_p$ 与 $y_2$ | 新区间 | 理由 |
|---|---|---|---|
| $x_p>x_2$ | $y_p<y_2$ | $[x_2,b]$ | $x_p$ 更优且在右,舍左半 |
| $x_p>x_2$ | $y_p\ge y_2$ | $[a,x_p]$ | $x_p$ 变差,极小在 $x_p$ 左边 |
| $x_p\le x_2$ | $y_p<y_2$ | $[a,x_2]$ | $x_p$ 更优且在左,舍右半 |
| $x_p\le x_2$ | $y_p\ge y_2$ | $[x_p,b]$ | $x_p$ 变差,极小在 $x_p$ 右边 |
第 4 步:逐轮(前 4 轮)
| 轮 | $a$ | $b$ | 中点 $x_2$ | $x_p$ | $y_p$ | $y_2$ | 处理 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 5 | 2.5 | 1.3889 | 0.89215 | 0.87500 | $a\leftarrow1.389$ |
| 2 | 1.3889 | 5 | 3.1944 | 2.0775 | 0.01847 | 5.98420 | $b\leftarrow3.194$ |
| 3 | 1.3889 | 3.1944 | 2.2917 | 1.9278 | 0.01528 | 0.28002 | $b\leftarrow2.292$ |
| 4 | 1.8403 | 2.2917 | 1.8403 | 1.9748 | 0.00189 | 0.07246 | $a\leftarrow1.840$ |
第 5 步:结果与验算
迭代 10 轮后区间长度 $<0.01$,得
解析验算:$\varphi=(x+1)(x-2)^2$,$\varphi'=3(x-2)(x+2/3)$,根为 $x=2$ 与 $x=-\frac23$;二阶导 $\varphi''=6x-4$,$\varphi''(2)=8>0$(极小)、$\varphi''(-\frac23)=-8<0$(极大)。所以 $x^*=2$、$\varphi^*=0$ ✓。
作业4-3牛顿类方法(20 分):$f=(x_1-2)^4+(x_1-2x_2)^2$,$\vec x^{(0)}=[1,1]^T$,$\varepsilon=10^{-10}$
第 1 步:梯度与海赛
第一分量:$(x_1-2)^4\to4(x_1-2)^3$;$(x_1-2x_2)^2\to2(x_1-2x_2)\cdot1$。第二分量:$2(x_1-2x_2)\cdot(-2)=-4(x_1-2x_2)$。
第 2 步:在极小点处海赛为什么"坏"
精确极小点 $x_1=2,x_2=1$,此时
奇异——不能直接求逆。这就是为什么报告里改用伪逆(pinv)+ Armijo 步长:
第 3 步:Armijo 步长(保证函数值下降)
从 $\alpha=1$ 开始,若
就令 $\alpha\leftarrow\alpha/2$,直到满足为止(即"函数值至少按斜率的一小部分下降")。
第 4 步:结果
45 次迭代达到 $10^{-10}$ 精度。为什么这么多步:函数含四次项,极小点附近非常平坦,且 $\mathbf H$ 在 $x^*$ 奇异,牛顿法退化为线性收敛。
重点作业4-4:混合惩罚函数(25 分)——与作业 1-2 同模型
初始:$\vec x^{(0)}=[2,2]^T$,$r^0=2$,$c=0.5$,$\varepsilon=10^{-6}$。
第 1 步:为什么要"混合"
不等式约束用内点法(障碍项,把点挡在可行域内),等式约束用外点法(惩罚项,把点压到 $h=0$ 上)。两类约束性质不同,所以各用各的项:
验一下符号:可行域内 $g_j<0$,所以 $\frac1{g_j}<0$,前面加负号后 $-r\cdot\frac1{g_j}=+\frac{r}{|g_j|}>0$——越靠近边界 $|g_j|\to0$,惩罚越大,点被"推"回内部,这就是障碍。
第 2 步:初始点与惩罚因子
$\vec x^{(0)}=(2,2)$:$g_1=8-9=-1<0$、$g_2=2-2-1=-1<0$、$g_3=-2<0$、$g_4=-2<0$ ⇒ 严格内点 ✓(内点法要求)。但 $h=6-2=4\ne0$,所以等式项此时很大,先把点往 $h=0$ 上压。
$r^0=2$,之后 $r\leftarrow cr=0.5r$:$r=2,\ 1,\ 0.5,\ 0.25,\dots\to0$。$r\downarrow0$ 时障碍减弱,最优点从内部逼近边界;同时 $\frac{1}{\sqrt r}\uparrow\infty$,等式惩罚加重。
第 3 步:每一轮做什么
固定 $r$,用无约束方法(本题用 fminsearch)求 $\Phi$ 的极小点 $\vec x^*(r)$;然后 $r\leftarrow0.5r$,以上一轮的解作初值,重复,直到 $\|\vec x^{k+1}-\vec x^k\|<10^{-6}$。
第 4 步:迭代序列(数值结果)
| 轮 | $r$ | $x_1^*(r)$ | $x_2^*(r)$ | $F$ | $g_1$ |
|---|---|---|---|---|---|
| 1 | 2 | 1.041510 | 2.604419 | 15.365654 | $-1.13$ |
| 2 | 1 | 1.002797 | 2.674925 | 15.044945 | $-0.84$ |
| 3 | 0.5 | 0.981409 | 2.725069 | 14.799883 | $-0.61$ |
| 4 | 0.25 | 0.969753 | 2.760416 | 14.616809 | $-0.44$ |
| … | … | … | … | … | … |
| 末 | $\approx10^{-9}$ | 0.948685 | 2.846044 | 14.155331 | $\approx0$ |
注意 $g_1$ 从 $-1.13$ 一路趋向 $0$:点从内部一步一步贴近圆弧——这正是内点法的特征。
第 5 步:结论与解析验算
为什么是这个点:最优点处 $h=0$($x_2=3x_1$)且 $g_1=0$(在圆上),联立
与作业 1-2 第 (4) 问完全一致——两种方法(图解法、惩罚函数法)指向同一点。
约束值验算(用 $\vec x^*$ 代回):$g_1=-1.4\times10^{-5}\approx0$、$g_2=0.9487-2.8460-1=-2.8974$、$g_3=-0.9487$、$g_4=-2.8460$、$h=3(0.9487)-2.8460\approx1.2\times10^{-5}\approx0$。
第 6 步:用 K-T 反验(说明它确实是最优)
起作用约束是 $g_1$ 和 $h$。K-T:$\nabla F+\mu_1\nabla g_1+\lambda\nabla h=\vec0$,
解得 $\mu_1\approx1.2136\ge0$、$\lambda\approx0.6$($\lambda$ 对等式约束无符号要求)。乘子非负 ⇒ 该点是 K-T 点,凸问题下即全局最优。
易错:①初始点必须在严格内点($g_j<0$),边界上会因 $1/0$ 溢出;②$r$ 必须递减(写成递增全错);③等式项系数要随 $r$ 增大,别忘;④程序里要对越界点赋大值防止 $1/g$ 变号。
作业4-5汽车主动稳定杆系统:谈谈对机械优化设计的理解(20 分)
答题框架(三要素 → 选方法 → 工程检验)
一、建模:把对象翻译成三要素
- 设计变量:稳定半杆的直径、壁厚、长度;扭杆刚度;衬套径向/扭转刚度;行星减速器的模数、齿数、传动比、级数;电机额定功率、转速。
- 目标函数:系统质量最小、抗侧倾力矩最大、响应时间最短、能耗最低(多目标时可加权)。
- 约束条件:半杆强度、疲劳寿命、刚度;齿轮接触与弯曲强度、传动比范围、行星轮装配条件;电机功率与转速;底盘布置空间、最小离地间隙。统一写成 $g_i(\vec x)\le0$、$h_j(\vec x)=0$。
二、选方法:按问题结构选
- 单参数(如半杆直径)→ 一维搜索(0.618 / 二次插值);
- 多变量 + 强度刚度约束 → 约束优化(惩罚函数、复合形、SQP);
- 质量/响应/成本冲突 → 多目标优化(加权法、主要目标法)+ 灵敏度分析。
三、工程检验:优化结果不是终点
强度校核、干涉检查、试验验证;考虑材料分散性、制造公差、装配误差 → 可靠性/稳健性优化;结构-电磁-控制多学科耦合。
结尾点睛:机械优化设计的实质 = 用数学模型描述设计问题 + 用合适算法寻找最优方案 + 用工程判断检验和修正结果。
六、考场:作业题怎么"长"成真题
| 作业母题 | 真题变形(已出现) | 要补/要减的动作 |
|---|---|---|
| 作业 2-1 方向导数 | 2016 填空 2:求梯度、海赛矩阵 | 只算不解,省掉 $\max/\min$ 讨论 |
| 作业 2-2 极值 | 2016 计算 3-3:牛顿法求 $f=16x_1^2+25x_2^2+5$ | "求极值"换成"牛顿法一步" |
| 作业 2-5 K-T | 2020 计算二:四点判 K-T + 局部/全局 | 加"逐点判可行"与"凸规划 ⇒ 局部即全局" |
| 作业 1-2 图解法 | 2020 计算二:画设计空间/可行域/等值线 | 换成 $f=x_1^2+x_2$ 的函数 |
| 作业 4-1 0.618 | 2016 计算 3-4:$\alpha+20/\alpha$,一轮 | 只做一轮、按表格填数 |
| 作业 3-1 阻尼牛顿 | 2016 计算 3-1:最速下降 + 一维搜索 | 方向从 $-\mathbf H^{-1}\vec g$ 换成 $-\vec g$ |
| 作业 4-4 混合惩罚 | 2016 简答 6:按混合罚函数法构造罚函数(不求解) | 只写 $\Phi$ + 内点/外点项意义 |
真题模拟卷
两套卷子都是扫描件整理,题干已逐字核对。先限时做,再看“判卷要点”折叠块。
2020-06-16《机械优化设计》期末卷(宣城机械 17)
2020一、简答(4×5=20 分)
1. 研究函数的变化率对最优化计算有什么意义?简述如何研究函数的变化率?
2. 数值迭代法的基本思想是什么?迭代格式是什么?收敛条件有什么作用?
3. 什么是等式约束?对于等式约束说说你知道的处理方法与措施?
4. 试列举你知道的无约束优化方法,并简单说明其搜索方向产生的思想?
判卷要点
1. 变化率由方向导数/梯度刻画:梯度方向是函数增长最快的方向,负梯度是最速下降方向,与梯度垂直方向导数为零(沿等值线切线)。这为迭代法提供搜索方向(最速下降、共轭梯度、变尺度都基于梯度)。研究方法:一阶偏导与梯度、二阶偏导与海赛矩阵、泰勒展开。
2. 步步逼近、步步下降;$\mathbf{x}^{k+1}=\mathbf{x}^k+\alpha_k\mathbf{d}^k$;核心是搜索方向、最佳步长、收敛判断。收敛条件(点距/函数值/梯度准则)用来判断何时停止迭代——保证结果达到精度又不做无用的计算。
3. 等式约束 $h_v(\mathbf{x})=0$。处理方法:拉格朗日乘子法(升维)、消元法(降维)、惩罚函数法(外点/混合,把 $h^2$ 加入目标)。
4. 见第4章 §4.9 Q1(六种方法 + 方向思想)。
2020二、计算(4+8+2+6=20 分):$f=x_1^2+x_2$,圆 + 直线约束
约束优化问题的数学模型为
1. 绘制上述问题的设计空间、可行域和目标函数等值线图,并标出 $x_A,x_B,x_C,x_D$ 点;
2. 判断 $x_A,x_B,x_C,x_D$ 点中约束极值点,若不是说明理由;若是利用 K-T 条件计算判断;
3. 回答这些点中哪些是局部最优点?哪些是全局最优点?
4. 请你自己另外指定 4 点,并说明其可行性、适用性。
$x_A=\begin{bmatrix}3\\0\end{bmatrix}$,$x_B=\begin{bmatrix}0\\-3\end{bmatrix}$,$x_C=\begin{bmatrix}0\\0\end{bmatrix}$,$x_D=\begin{bmatrix}0\\3\end{bmatrix}$。
判卷要点(完整答案见第2章 §2.7 真题块)
- 图(4 分):圆 $x_1^2+x_2^2=9$、直线 $x_1+x_2=1$、弓形可行域阴影、抛物线等值线 $x_2=c-x_1^2$、四点标注。
- K-T(8 分):$A$ 不可行($g_2=2>0$);$D$ 不可行($g_2=2>0$);$C$ 可行但无起作用约束且 $\nabla f=[0,1]^T\ne0$,不满足 K-T;$B$ 可行、$g_1$ 起作用,$\mu_1=\frac16\ge0$ → 满足 K-T。
- 局部/全局(2 分):局部最优 = $B(0,-3)$;全局最优 = $B(0,-3)$,$F_{\min}=-3$。($(-1,2)$、$(2,-1)$ 两交点处 $\mu_1=-\frac13<0$,不是 K-T 点。)
- 自选点(6 分):4 点各写“可行/不可行 + 是否 K-T/极值点”,如 $(0.5,0.5)$ 满足 K-T 但非极小(说明 K-T 只是必要条件)。
2020三、简述产生可行初始点的算法步骤并画框图(15 分)
判卷要点
见第5-6章 §5.5 与 §5.7 真题块:步骤 5 分 + 框图 10 分(框、菱形、是否分支、循环、次数判断、输出)。
2020四、绘图并说明复合形法“反射-收缩”迭代过程(15 分)
判卷要点
见第5-6章 §5.7 真题块:两幅图(反射成功 / 反射失败收缩)+ 七步文字。三点共线、$\alpha=1.3$、$\beta=0.5$、判据 $f(\mathbf{x}_R)<f(\mathbf{x}_H)$ 必须写全。
2020五、应用(2×15=30 分):圆木锯梁 + 型材下料
判卷要点
见第1章 §1.5 两个真题块。圆木题:几何约束 $b^2+h^2\le D^2$ 是最大采分点,程序化写成 FUN/CONS 两个子程序。下料题:先枚举方案表,再写 $\min\sum x_j$、$\sum a_{ij}x_j\ge n_i$、$x_j$ 非负整数。
2016 年期末卷(填空 + 名解 + 简答 + 计算 + 应用)
2016 卷题型更全,适合查漏:填空题 16 空(覆盖全书概念)、名词解释/简答、计算 4 题(梯度海赛、K-T、牛顿法、黄金分割)、应用 2 题(悬吊钢丝绳、另一建模题)。
2016一、填空题(16 空,答案)
| # | 题目 | 答案 |
|---|---|---|
| 1 | 组成优化设计数学模型的三要素是__、__、__ | 设计变量、目标函数、约束条件 |
| 2 | $f=x_1^2+x_2^2-4x_1x_2+5$ 在 $[2,4]^T$ 处的梯度为__,海赛矩阵为__ | $[-12,0]^T$;$\begin{bmatrix}2&-4\\-4&2\end{bmatrix}$ |
| 3 | 目标函数是一项设计所追求的指标的数学反映,因此对它最基本的要求是能用来评价设计的__,同时必须是设计变量的__ | 优劣;可计算函数 |
| 4 | 建立优化设计数学模型的基本原则是确切反映__的基础上力求__ | 工程实际问题;简洁 |
| 5 | 约束条件的尺度变换常称__,这是为改善数学模型性态常用的一种方法 | 规格化(归一化) |
| 6 | 随机方向法所用的步长一般按__来确定,此法是指依次迭代的步长按一定的比例__的方法 | 加速步长法;递增(衰减) |
| 7 | 最速下降法以__方向作为搜索方向,因此最速下降法又称为__法,其收敛速度较__ | 负梯度;梯度;慢 |
| 8 | 二元函数在某点取得极值的充分条件是__,必要条件是该点的海赛矩阵正定 | $\nabla f(X_0)=0$(该点梯度为零) |
| 9 | 拉格朗日乘子法的基本思想是通过增加变量将__优化问题变成__优化问题,这种方法又被称为__法 | 约束;无约束;升维 |
| 10 | 改变复合形形状的搜索方法主要有__、__、__、__ | 反射、扩张、收缩、压缩 |
| 11 | 坐标轮换法的基本思想是把__的优化问题转化为__的优化问题 | 多变量;一系列单变量 |
| 12 | 在选择约束条件时应特别注意避免出现__的约束,另外应当尽量减少不必要的约束 | 相互矛盾 |
| 13 | 目标函数是 $n$ 维变量的函数,它的函数图像只能在__空间中描述出来,为了在 $n$ 维空间中反映目标函数的变化情况,常采用__的方法 | $n+1$ 维;目标函数等值面(等值线) |
| 14 | 数学规划法的迭代公式是__,其核心是__和__ | $\mathbf{X}^{k+1}=\mathbf{X}^k+\alpha_k\mathbf{d}^k$;建立搜索方向;计算最佳步长 |
| 15 | 协调曲线法是用来解决__的多目标优化设计问题的 | 设计目标相互矛盾 |
| 16 | 机械优化设计的一般过程中,__是首要和关键的一步,它是取得正确结果的前提 | 建立优化设计数学模型 |
2016二、名词解释(补充:9 个高频概念)
| 名词 | 答案 |
|---|---|
| 凸规划 | 目标函数 $f(\mathbf{x})$ 与全部约束 $g_j(\mathbf{x})$ 都是凸函数(或线性)的约束优化问题。 |
| 可行搜索方向 | 指当设计点沿该方向作微量移动时,目标函数值下降、且不会越出可行域的方向。 |
| 设计空间 | $n$ 个设计变量为坐标组成的实空间,是所有设计方案的组合。 |
| 可靠度 | 产品在规定条件下和规定时间内完成规定功能的概率。 |
| 收敛性 | 某种迭代程序产生的序列 $\{\mathbf{X}^k\}$ 收敛于 $\lim\limits_{k\to\infty}\mathbf{X}^{k+1}=\mathbf{X}^*$(即收敛到最优解)。 |
| 非劣解 | 多目标优化中,找不到一个 $\mathbf{X}$ 能使某个目标函数值改善而不使另一个目标函数值变坏的解。 |
| 黄金分割法 | 将一线段分成两段,使整段长与较长段长之比等于较长段与较短段长之比(比值 0.618),据此安排试点、逐次缩小区间的搜索方法。 |
| 可行域 | 满足所有约束条件的设计点在设计空间中的活动范围。 |
| 斐波那契法 | 用斐波那契数列确定试点、逐次缩短区间的搜索方法(分数法)。 |
2016三、简答 7 题
1. 什么是优化步长?如何理解“一元函数求极值”?
2. 数值迭代法的基本思想、迭代格式、收敛条件。
3. 什么是共轭方向?如何产生?
4. 列举无约束优化方法并说明搜索方向思想。
5. 随机方向法的可行搜索方向如何产生?
6. 罚函数法(内点/外点)的基本原理与惩罚项意义。
7. 等式约束的处理方法。
判卷要点
1:沿给定方向使 $\varphi(\alpha)$ 取极小的步长,$\varphi'(\alpha)=0$;一维搜索就是一元函数求极值。
2–5:见第4章 §4.9、第5-6章 §5.7。
6:见第5-6章 §5.7 混合罚函数真题块(内点障碍项、外点惩罚项的意义)。
7:拉格朗日乘子法(升维)、消元法(降维)、惩罚函数法。
2016四、计算 4 题
1. 求 $f=x_1^2+x_2^2-4x_1x_2+5$ 在 $[2,4]^T$ 的梯度与海赛矩阵。
2. $f=(x_1-10)^2+(x_2-2)^2$,$g_1=-x_2^2+4x_1-8\le0$,$g_2=x_1-6\le0$,$g_3=-x_2\le0$,判断 $x_A(2,0),x_B(0,4),x_C(6,4),x_D(-4,0)$ 是否满足 K-T,并判断局部/全局最优。
3. 牛顿法求 $f=16x_1^2+25x_2^2+5$ 的极小点,$\mathbf{X}^0=[2,2]^T$。
4. 黄金分割法求 $\varphi(\alpha)=\alpha+20/\alpha$ 的极小点,$[0.2,1]$,迭代一次。
判卷要点(完整过程见第2、3章)
1:$\nabla f(2,4)=[-12,0]^T$,$\mathbf{H}=\begin{bmatrix}2&-4\\-4&2\end{bmatrix}$(不定)。
2:$x_B$ 不可行($g_2=8>0$);$x_A,x_D$ 可行但不满足 K-T;$x_C$ 的 K-T 方程第二分量不成立,也不满足;全局最优 $(6,2)$,$F_{\min}=16$。
3:$\mathbf{X}^1=[0,0]^T$,$f_{\min}=5$。
4:$\alpha_1=0.5056,\alpha_2=0.6944$,$y_1=40.0626>y_2=29.4962$,新区间 $[0.5056,1]$。
2016五、六:产生可行初始点 + 应用建模
判卷要点
五:见第5-6章 §5.5 + 框图。
六:两根钢丝绳悬吊重物,建模见第1章 §1.5 真题块(目标为总重 $\gamma(l_1A_1+l_2A_2)$,约束为两绳强度、挂点位移、截面积上下限)。
考场 10 条(开卷也要背)
- K-T 六步法先写“可行性”,不可行直接结论,别浪费 8 分。
- 建模题先写“设计变量 + 单位”,再目标、再约束,最后规范化检查——按块给分。
- 求最大的目标函数一定加负号,约束一定整理成 $\le0$。
- 复合形法画图:三点共线 + 形心去掉最坏点 + 收缩图 + 判据文字。
- 框图必须有菱形判断、是/否分支、循环和次数判断。
- 0.618 法每轮只算一个新点;表格列 $a,b,\alpha_1,\alpha_2,y_1,y_2$。
- 牛顿法先判 $\mathbf{H}$ 正定;二次函数一步到位要说明。
- DFP 中 $\mathbf{s}$ 是点位差、$\mathbf{y}$ 是梯度差,别写反。
- 内点 $r\downarrow0$、外点 $M\uparrow\infty$,方向写反全题扣分。
- 开卷找不到就翻本页目录/搜索,别死磕一题——90 分钟做完 80% 就是胜利。