DASE 7113 · 课程精讲

优化问题分类

共 40 页。按原课件顺序,左侧看原页,右侧读讲解。

逐页目录 · 共 40 页
  1. 为什么要给优化问题分类
  2. 复习:变量、目标、约束
  3. 先判断合法,再比较好坏
  4. 可行域:全部规则允许的交集
  5. 凸集合:集合内两点连线不能跑出去
  6. 超平面:二维时就是一条直线
  7. 超平面:三维时就是一个平面
  8. 证明超平面是凸集:逐行代回定义
  9. 半空间:保留直线或平面的一侧
  10. 证明半空间凸:非负权重保留不等号
  11. 多面体:有限个半空间共同允许的区域
  12. 把复杂证明拆成一个通用结论
  13. 凸集交集的证明:同一个点通过两次检查
  14. 线性等式也可以包含在多面体里
  15. 凸函数:曲线在两端连线的下面
  16. 一阶条件:每条切线都托在函数下面
  17. 证明:凸性为什么推出切线条件
  18. 证明:切线条件为什么又能推出凸性
  19. 二阶条件:斜率不能越走越小
  20. 证明:凸函数的二阶导为什么非负
  21. 证明:二阶导非负怎样推出凸性
  22. 二阶导非负,还要检查定义域是不是凸
  23. 梯度:把各坐标的偏导数装进一个列向量
  24. Jacobian:多个输出对多个输入的变化表
  25. Hessian:再对梯度求一次导数
  26. 半正定:所有方向上的二次型都非负
  27. 四个矩阵逐一判断
  28. 多元的一阶凸性条件:切线变成切平面
  29. 多元二阶条件:Hessian 在每个方向都不能向下弯
  30. 常见凸函数:求导与范数证明分别怎么做
  31. 凸性证明题:如何组织每一步
  32. 变量类型:能取小数,还是只能选整数
  33. 目标函数:线性、凸、非凸怎样分
  34. 为什么凸函数的“≤0 区域”是凸的
  35. 为什么凸函数的“=0 区域”却未必凸
  36. 整数规划、混合整数规划、连续优化
  37. 无约束和有约束
  38. 线性规划和非线性规划
  39. 判断标准凸规划,要检查三处
  40. 分类完成后,能知道什么
原第 1 页

为什么要给优化问题分类

原课件第1页
点击原页可打开 PDF。

不同优化问题要用不同方法。就像解一元方程前要看它是一次还是二次,优化前也要检查变量、目标和约束的性质。

这一讲先学“凸”:集合里两点之间的线段是否还在集合内;函数图像是否位于两点连线下方。再用这两个概念区分连续、整数、线性、非线性和凸优化问题。

分类可以同时成立。例如一个线性规划通常既是连续优化,也是有约束凸优化。

原第 2 页

复习:变量、目标、约束

原课件第2页
点击原页可打开 PDF。

变量 x 是你要选择的数,可以包含多个分量;目标 f(x) 用一个数评价选择;约束规定什么选择合法。

例如生产两种产品:x=(x1,x2) 是产量;总成本 f=2x1+3x2;产能规则可能是 x1+x2≤10,还要有 x1,x2≥0。只有满足规则的产量才进入比较。

本页不等式用 gi(x)≥0,标准形式用 gi(x)≤0。例如 x1≥0 改写成 −x1≤0,整个左边一起变号。

原第 3 页

先判断合法,再比较好坏

原课件第3页
点击原页可打开 PDF。

标准形式是:

minxf(x),gi(x)≤0 (i=1,…,m),hj(x)=0 (j=1,…,p).

m 是不等式数量,p 是等式数量。可行解满足全部约束;最优解是所有可行解里目标值最小的解。

例如 minx2,条件 x≥2。若不看约束,会选 0;但 0 不合法。合法区间是 [2,∞),其中平方最小的点是 x*=2,目标值为 4。

因此不要先求无约束最优点就结束,还要把它放回全部约束中检查。

原第 4 页

可行域:全部规则允许的交集

原课件第4页
点击原页可打开 PDF。

可行域 A 是所有合法变量组成的集合:

A={x:gi(x)≤0 ∀i, hj(x)=0 ∀j}.

符号 ∀ 表示“每一个都要满足”。设第 i 条不等式允许的集合是 Gi,第 j 条等式允许的集合是 Hj,则:

A=(⋂i=1mGi)∩(⋂j=1pHj).

∩ 是交集,意思是同时属于。比如 x≥0,y≥0,x+y=1:先保留第一象限,再保留直线 x+y=1,最后只剩 (1,0) 与 (0,1) 之间的线段。

若规则是 x≥2 且 x≤1,没有数能同时满足,可行域就是空集。

原第 5 页

凸集合:集合内两点连线不能跑出去

原课件第5页
点击原页可打开 PDF。

取集合 A 里的任意两点 x,y。连接它们的整条线段都在集合里,就称 A 为凸集。

z=λx+(1−λ)y,0≤λ≤1.

λ 是两点的混合权重。λ=0 得 y,λ=1 得 x,λ=1/2 得中点。权重都非负且加起来等于 1,所以 z 在线段上。

读图用“任取两点、画连接线”检验:实心圆盘、三角形、长方体都凸;有凹口的区域常不凸。圆周也不凸:两个相反端点的中点在圆心,圆心却不在圆周上。

证明凸性要覆盖所有点对;证明不凸,只需找出一对点,让其中某个线段点落到集合外。

对应课堂录音Week02 Supplement01 00:00:00–00:04:28
原第 6 页

超平面:二维时就是一条直线

原课件第6页
点击原页可打开 PDF。

超平面的统一写法是:

H={x∈Rn:aTx=b},a≠0.

Rn 表示 n 个实数组成的空间;上标 T 表示转置;aTx=∑i=1naixi 是内积。a 是决定方向的非零向量,b 决定位置。

右图的方程是 0.5x1+x2=3,改写为 x2=3−0.5x1,读出斜率 −0.5。这条线经过 (0,3) 和 (6,0)。两点之差 (6,−3) 沿直线方向,与系数向量 (0.5,1) 的内积是 0.5×6−3=0,所以系数向量与直线垂直,叫法向量。

原第 7 页

超平面:三维时就是一个平面

原课件第7页
点击原页可打开 PDF。

三维有三个坐标,一个线性方程写为:

a1x1+a2x2+a3x3=b.

右图画的是 0.5x1+2x2−x3=−3。改写为 x3=0.5x1+2x2+3,选定水平坐标 x1,x2,就能算出对应的高度 x3。例如 x1=x2=0 时高度为 3,x1=0,x2=1 时高度为 5。图中的边缘是绘图裁切,平面本身向外延伸。

再加不等式才会截去一部分平面。例如平面 x1+x2+x3=1 加上 x1,x2,x3≥0,只保留三个轴截点 (1,0,0),(0,1,0),(0,0,1) 围成的三角形。

原第 8 页

证明超平面是凸集:逐行代回定义

原课件第8页
点击原页可打开 PDF。

要证明凸性,目标是说明:任取超平面里两点,它们的任意加权中间点仍满足原方程。

  1. 任取 x,y∈H。由“属于超平面”得 aTx=b、aTy=b。
  2. 取 0≤λ≤1,设 z=λx+(1−λ)y。
  3. 把 z 代回定义式,并用线性运算展开:
aTz=aT[λx+(1−λ)y](1)=λaTx+(1−λ)aTy(2)=λb+(1−λ)b=b.(3)

z 也满足 aTz=b,所以 z∈H。两点和权重都是任意选的,证明完成。

原第 9 页

半空间:保留直线或平面的一侧

原课件第9页
点击原页可打开 PDF。

把超平面的等号改为不等号,得到半空间:

L={x:aTx≤b}.

其中 aTx=b 是边界;≤ 选择一侧,并包含边界。二维叫半平面,三维及高维统一叫半空间。

以 x1+2x2≤4 为例:先画直线 x1+2x2=4,再测试原点。原点代入为 0≤4,成立,所以保留原点所在的一侧。若不等号是 ≥,就保留另一侧。

只有边界直线不够:整个被保留的区域都属于半空间。

原第 10 页

证明半空间凸:非负权重保留不等号

原课件第10页
点击原页可打开 PDF。

任取 x,y∈L,就有 aTx≤b 和 aTy≤b。取 λ∈[0,1],令 z=λx+(1−λ)y。

因为两个权重都非负,可以分别乘上去再相加:

aTz=λaTx+(1−λ)aTy(1)≤λb+(1−λ)b=b.(2)

第一行使用内积的线性,第二行使用原来的两个约束。因此 z 仍在半空间内,L 是凸集。权重非负很关键,乘负数会使不等号反向。

原第 11 页

多面体:有限个半空间共同允许的区域

原课件第11页
点击原页可打开 PDF。

课件定义:

P={x∈Rn:ajTx≤bj, j=1,…,m}.

j 是约束编号。每条不等式允许一个半空间,全部同时满足就取交集。比如 x≥0,x≤1,y≥0,y≤1 的交集是一个实心正方形。

多面体可以无界。例如 x≥0,y≥0 给出整个第一象限,仍然是多面体。几何课里常画的封闭立体只是其中一种。

要证明任意多面体都凸,可以先证明一个一般结论:凸集的交集仍然凸。

原第 12 页

把复杂证明拆成一个通用结论

原课件第12页
点击原页可打开 PDF。

本页用到的结论是:如果 A1 和 A2 都凸,那么 A1∩A2 也凸。

既然每个半空间都凸,就先把前两个相交,得到凸集;再与第三个相交,仍然凸;这样做有限次,整个多面体就凸。

这里一定是“交集”,即所有规则同时满足。“并集”只要求满足其中一个,没有这个性质。例如 [0,1] 与 [2,3] 各自是凸区间,但并集中的两点 1 和 2 的中点 1.5 不在并集里,所以并集不凸。

原第 13 页

凸集交集的证明:同一个点通过两次检查

原课件第13页
点击原页可打开 PDF。
  1. 任取 x,y∈A1∩A2。按交集定义,这两点同时在 A1 内,也同时在 A2 内。
  2. 任取 λ∈[0,1],定义 z=λx+(1−λ)y。
  3. 因为 A1 凸,而 x、y 在其中,所以 z∈A1。
  4. 因为 A2 凸,同理 z∈A2。
  5. 同一个 z 同时属于两个集合,所以 z∈A1∩A2。

这就证明交集凸。把“两个集合”换成任意多个,同样的逐项检查仍然成立,因此所有线性约束共同形成的可行域是凸集。

原第 14 页

线性等式也可以包含在多面体里

原课件第14页
点击原页可打开 PDF。

一个等式可以改写成两个方向相反的不等式:

cTx=d⟺{cTx≤d,−cTx≤−d.

第二条乘以 −1 就是 cTx≥d。一个数既不大于 d,又不小于 d,只能等于 d。

例如 x+y=1 可以写为 x+y≤1 与 −x−y≤−1。因此混合了线性等式与不等式的系统仍然定义多面体,也仍然是凸集。

不要只保留其中一条:只保留 x+y≤1 得到半平面,比原来的直线大很多。

原第 15 页

凸函数:曲线在两端连线的下面

原课件第15页
点击原页可打开 PDF。

先要求定义域 A 是凸集,再要求任意 x,y∈A、λ∈[0,1] 都满足:

f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y).

左边先平均输入再算函数;右边先算两端函数值再平均。在图上,右边是两端点连成的弦的高度,左边是函数本身的高度。函数不高于弦,就叫凸。

例如 f(t)=t2,两端输入为 0 和 2,中点为 1。函数值为 f(1)=1,弦的中点高度为 [f(0)+f(2)]/2=2,所以中点落在弦下方。

右图的曲线有一段高于弦。在线段上找到一个这样的点,就违反了“对任意两点及权重都成立”的条件,因此右图的函数不凸。

对应课堂录音Week02 Supplement01 00:00:00–00:04:28Week07 Part01 01:59:13–02:04:42
原第 16 页

一阶条件:每条切线都托在函数下面

原课件第16页
点击原页可打开 PDF。

直接用凸函数定义,需要检查所有点对和它们之间的弦。为了更方便判断,改看每个点的切线。对于定义在凸区间上的可微一元函数,凸性等价于:

f(y)≥f(x)+f′(x)(y−x),任意 x,y.

右边是在 x 处作切线,再走到横坐标 y 时预测的高度。f′(x) 是切线斜率,y−x 是横向移动量,两者乘积是切线预测的高度变化。

图中真实变化为 f(y)−f(x),切线预测变化为 f′(x)(y−x);凸函数的真实高度至少有切线那么高。

用 f(t)=t2 检查。任取切点 x,有 f(x)=x2、f′(x)=2x。在横坐标 y 处,曲线高度与切线高度之差可化成一个平方。

f(y)−[f(x)+f′(x)(y−x)]=y2−x2−2x(y−x)=(y−x)2≥0.

任意 x、y 都满足该不等式,因此这个函数凸。比如切点 x=1、观察点 y=2,切线高度是 3,曲线高度是 4。

动手试 · 同一条曲线上的弦和切线

在 f(x)=x² 上固定 x=−1。移动另一个点,再改变区间内的位置 t。

对应课堂录音Week02 Supplement01 00:00:00–00:04:28
原第 17 页

证明:凸性为什么推出切线条件

原课件第17页
点击原页可打开 PDF。

先看目标:要得到 f(y)−f(x)≥f′(x)(y−x)。左边是两点的函数值之差,右边含导数,因此尝试把凸性定义整理成“函数值之差 ≥ 差商”。固定任意 x、y,取 0<λ<1,在线段上取点 x+λ(y−x)=(1−λ)x+λy,再让 λ 缩小,使这个点靠近 x。

  1. 由凸性:
f(x+λ(y−x))≤(1−λ)f(x)+λf(y).
  1. 两边减去 f(x):
f(x+λ(y−x))−f(x)≤λ[f(y)−f(x)].
  1. 除以正数 λ,不等号方向不变:
f(x+λ(y−x))−f(x)λ≤f(y)−f(x).
  1. 若 y≠x,左边再写成差商乘位移:
f(x+λ(y−x))−f(x)λ(y−x)(y−x).

当 λ→0+,差商趋于 f′(x),于是得到 f′(x)(y−x)≤f(y)−f(x)。若 x=y,两边都是 0,直接成立。

对应课堂录音Week02 Supplement01 00:10:41–00:15:20
原第 18 页

证明:切线条件为什么又能推出凸性

原课件第18页
点击原页可打开 PDF。

现在假设任意切线都在函数下方,要证明函数在弦下方。任取 x、y、λ∈[0,1],令 z=λx+(1−λ)y。关键构造是:两次都在同一个 z 处取切线,再按 λ 与 1−λ 加权,这样才能把导数项抵消。

  1. 把切点固定在 z,分别看 x、y,得到:
f(x)≥f(z)+f′(z)(x−z),f(y)≥f(z)+f′(z)(y−z).
  1. 第一式乘 λ,第二式乘 1−λ,再相加:
λf(x)+(1−λ)f(y)≥f(z)+f′(z)[λ(x−z)+(1−λ)(y−z)].
  1. 方括号展开为:
λx+(1−λ)y−[λ+(1−λ)]z=z−z=0.

导数项完全消失,剩下 λf(x)+(1−λ)f(y)≥f(z),正是凸函数定义。两个方向都证明后,才能说“当且仅当”。

对应课堂录音Week02 Supplement01 00:15:21–00:19:19
原第 19 页

二阶条件:斜率不能越走越小

原课件第19页
点击原页可打开 PDF。

在凸开区间上,二次可微的一元函数凸,当且仅当:

f″(x)≥0对区间内每个 x.

一阶导 f′(x) 是斜率,二阶导 f″(x) 是斜率变化率。二阶导非负意味着沿 x 增大方向,斜率不减:可以从负到 0,再到正,形成向上开的碗形。

例如 f(x)=x2,f′(x)=2x、f″(x)=2≥0,所以凸。直线 f(x)=3x+1 的二阶导为 0,也凸;凸不要求必须弯曲。

斜率不减,不代表函数一定先下降再上升。例如 ex 的斜率始终为正,所以一直上升;−logx 在 x>0 上的斜率始终为负,所以一直下降,但二阶导 1/x2>0,仍然凸。图中的“先降后升”只是斜率穿过零点的一种情形。

若函数在闭区间的端点连续,可在内部使用导数判据,再取极限把凸性不等式延伸到端点。只在某一个点算出 f″≥0,还不足以判断整个函数。

对应课堂录音Week02 Supplement01 00:15:21–00:19:19
原第 20 页

证明:凸函数的二阶导为什么非负

原课件第20页
点击原页可打开 PDF。

凸性已经给出切线条件。把切点分别放在 x 和 y,可得:

f(y)−f(x)≥f′(x)(y−x),f(x)−f(y)≥f′(y)(x−y).

第二式改写为 f(y)−f(x)≤f′(y)(y−x)。把两式合起来:

f′(x)(y−x)≤f(y)−f(x)≤f′(y)(y−x).

因此 [f′(y)−f′(x)](y−x)≥0。对 y≠x,除以正数 (y−x)2,得到:

f′(y)−f′(x)y−x≥0.

令 y 趋近 x,左边就是 f″(x),所以 f″(x)≥0。这里除以的是平方,因此无论 y 在 x 左边还是右边,不等号都不会反向。

对应课堂录音Week02 Supplement01 00:19:24–00:20:00
原第 21 页

证明:二阶导非负怎样推出凸性

原课件第21页
点击原页可打开 PDF。

假设整个区间内 f″≥0。按课件用分部积分证明时,取 f″ 连续。先取 y>x。积分范围内 y−t≥0,所以被积函数非负。

I=∫xyf″(t)(y−t)dt≥0.

t 是积分中的临时变量。选 u=y−t,是因为它在上端 t=y 时为0;选 dv=f″(t)dt,积分后便剩下 f′(t),能接回切线的斜率。分部积分中 du=−dt,v=f′(t):

I=[f′(t)(y−t)]xy+∫xyf′(t)dt(1)=0−f′(x)(y−x)+f(y)−f(x).(2)

所以 f(y)≥f(x)+f′(x)(y−x)。若 y<x,把上下限换过来:I=−∫yxf″(t)(y−t)dt=∫yxf″(t)(t−y)dt≥0,所以同一等式继续成立。若 y=x,则两边都为0。

这样对所有 x、y 都得到切线条件,再由第18页的证明得到凸性。积分式也可理解为“真实函数值减去切线预测值”的精确差额。

用 f(t)=t2,x=1,y=2 检查:I=∫122(2−t)dt=[4t−t2]12=1。函数真实增量是 4−1=3,切线预测增量为 2(2−1)=2,两者正好差1。

如果二阶导存在,但不连续

用中值定理也能证明。对任意 a<b,对 f′ 用中值定理,得到 f′(b)−f′(a)=f″(ξ)(b−a)≥0,所以 f′ 不减。再对 f 用中值定理,得到 f(y)−f(x)=f′(η)(y−x)。若 y>x,则 f′(η)≥f′(x),而 y−x>0。若 y<x,则 f′(η)≤f′(x),而 y−x<0,乘上它之后不等号反向。两种情况下都有 f(y)−f(x)≥f′(x)(y−x)。

原第 22 页

二阶导非负,还要检查定义域是不是凸

原课件第22页
点击原页可打开 PDF。

课件举 f(x)=1/x2,定义域是 (−∞,0)∪(0,∞)。求导:

f′(x)=−2x3,f″(x)=6x4>0.

每个允许的 x 上二阶导都为正,但整个定义域分成两块。取 x=−1,y=1,中点 0 不在定义域,因此定义域不凸。

所以这个函数在 (0,∞) 上凸,在 (−∞,0) 上也凸,却不能按本课定义称为在这两个区间的并集上凸。

做导数判定始终分两步:先检查定义域凸,再检查整个域内的导数条件。

原第 23 页

梯度:把各坐标的偏导数装进一个列向量

原课件第23页
点击原页可打开 PDF。

多元函数 f:Rn→R 输入 n 个数,输出一个数。对第 j 个变量求偏导时,把其他变量先当常数。

∇f(x)=[∂f/∂x1⋮∂f/∂xn].

∇ 读作 nabla。本课梯度是 n×1 的列向量;同一标量函数的 Jacobian 是 1×n 行向量,为梯度的转置。

在点 x0 附近移动 Δx=x−x0,一阶近似为:

f(x)≈f(x0)+∇f(x0)TΔx.

例如 f(x1,x2)=x12+3x2,在 (1,2) 有 f=7、∇f=(2,3)T。移动到 (1.1,2.2) 时,预测增量 2×0.1+3×0.2=0.8,预测值 7.8;真实值为 1.12+3×2.2=7.81。

对应课堂录音Week03 Part01 00:40:18–00:46:17Week03 Part01 00:46:18–00:51:08
原第 24 页

Jacobian:多个输出对多个输入的变化表

原课件第24页
点击原页可打开 PDF。

若 f:Rn→Rm,输入有 n 个分量,输出有 m 个分量,则 Jacobian 的形状是 m×n。第 i 行第 j 列记录 ∂fi/∂xj。

Jf=[∂f1/∂x1⋯∂f1/∂xn⋮⋮∂fm/∂x1⋯∂fm/∂xn].

例如 f(x1,x2)=(x12+x2, x1x2, ex2)T。输出有 3 个,输入有 2 个,所以:

Jf=[2x11x2x10ex2]∈R3×2.

输入变化 Δx 是 2×1,乘积 JΔx 是 3×1,正好预测三个输出的变化。课件把向量函数的“梯度”约定为这个矩阵的转置,即 n×m;使用时跟着维度判断。

矩阵三行分别这样算。第一个输出 x12+x2 分别对 x1,x2 求偏导,得到 2x1,1。第二个输出是乘积 x1x2,对 x1 求导时把 x2 当常数,得 x2,对 x2 求导时得 x1。第三个输出只含 x2,所以这行是 0,ex2。

对应课堂录音Week02 Supplement02 00:00:00–00:04:48
原第 25 页

Hessian:再对梯度求一次导数

原课件第25页
点击原页可打开 PDF。

标量函数的 Hessian(黑塞矩阵)记录所有二阶偏导:

∇2f(x)=H,Hij=∂∂xj(∂f∂xi).

它是 n×n 矩阵,也是梯度的 Jacobian。这里的“2”表示再求一次导数,不是把梯度的每个分量平方。逐行做:先求一个一阶偏导,再分别对所有变量求导。

以 f(x1,x2)=x12+3x1x2+2x22 为例:

∇f=[2x1+3x23x1+4x2],∇2f=[2334].

左上角是 ∂(2x1+3x2)/∂x1=2;右上角是对 x2 求导得 3;第二行来自对 3x1+4x2 求导:对 x1 得3,对 x2 得4。二阶偏导连续时,两个混合偏导相等,H 是对称矩阵。

对应课堂录音Week02 Supplement02 00:00:00–00:04:48
原第 26 页

半正定:所有方向上的二次型都非负

原课件第26页
点击原页可打开 PDF。

对称矩阵满足 HT=H,即主对角线两侧的元素镜像相同。这样的 H 半正定,简称 PSD,是指:

vTHv≥0对所有向量 v.

v 可以理解为任选的方向。判断 PSD 的常用办法有:所有特征值非负;把 H 写成 LLT;或者检查所有主子式非负。

特征值 λ 表示一个特殊方向上的放大倍数:若非零向量 v 满足 Hv=λv,则 vTHv=λ‖v‖22。负特征值会直接给出一个负二次型方向。

为何分解法有效?若 H 为 n×n,L 可以是 n×r 的实矩阵;于是 LTv 是 r×1 向量。若 H=LLT,则:

vTHv=(LTv)T(LTv)=‖LTv‖22≥0.

这里的“所有主子式”包括任意选取相同行、列编号得到的主子阵行列式;“顺序主子式”只看左上角逐渐扩大的那些。右图的嵌套方框标出的正是用来求顺序主子式的子阵。若选第 1、3 行和第 1、3 列,得到的也是主子阵,行列式也是主子式,但这个子阵没有出现在嵌套方框里。不能只用“顺序主子式非负”判断 PSD:例如 H=diag(0,−1) 的顺序主子式是 0、0,但取 v=(0,1)T,就有 vTHv=−1,所以不是半正定。若对称矩阵的所有顺序主子式严格为正,则它正定,因此也半正定。

对应课堂录音Week02 Supplement02 00:00:00–00:04:48Week02 Supplement02 00:04:51–00:08:46
原第 27 页

四个矩阵逐一判断

原课件第27页
点击原页可打开 PDF。

用 vTHv 展开,通常比直接求特征值更直观。

  1. H1=diag(1,1,2):二次型为 v12+v22+2v32,任何非零向量都会得到正数,因此正定,也半正定。
  2. H2=diag(1,1,−2):取 v=(0,0,1) 得 −2,取 (1,0,0) 得 1,所以既有正方向又有负方向,称为不定矩阵。
  3. H3=[1−3−310]:二次型为 u2−6uv+10v2=(u−3v)2+v2,非零时严格大于 0,因此正定。也可检查顺序主子式:左上角为 1,整个行列式为 1×10−(−3)2=1,两者都严格为正。
  4. H4=[−1−3−310]:取 (u,v)=(1,0) 得 −1,取 (0,1) 得 10,因此不定。

否定半正定只需找到一个负值方向;证明半正定要覆盖所有方向。配方、分解和特征值都可以用来完成后者。

对应课堂录音Week02 Supplement02 00:04:51–00:08:46Week02 Supplement02 00:08:47–00:09:51
原第 28 页

多元的一阶凸性条件:切线变成切平面

原课件第28页
点击原页可打开 PDF。

一元条件中的“斜率乘位移”,在多元情形变成“梯度与位移的内积”:

f(y)≥f(x)+∇f(x)T(y−x).

梯度与位移都为 n×1,所以先把梯度转置成 1×n,再相乘,结果才是一个高度变化量:∇f(x)T(y−x)=∑i(∂f/∂xi)(yi−xi)。函数在凸开域上可微时,这个对全部 x、y 成立的条件等价于凸性。右边是 x 处的一阶仿射近似,几何上为托在图像下方的支撑平面。

例如 f(x)=‖x‖22,梯度 2x。计算“函数减去切平面”:

f(y)−f(x)−2xT(y−x)=yTy−2xTy+xTx(1)=‖y−x‖22≥0.(2)

因此这个多元平方函数凸,证明与一元的 (y−x)2≥0 完全对应。

对应课堂录音Week02 Supplement02 00:08:47–00:09:51
原第 29 页

多元二阶条件:Hessian 在每个方向都不能向下弯

原课件第29页
点击原页可打开 PDF。

在凸开域上,二次可微的多元函数凸,当且仅当每个点的 Hessian 都半正定:

∇2f(x)⪰0对全部 x.

⪰0 表示矩阵半正定。它要求所有方向的曲率非负,而不只是矩阵对角线非负。

为什么检查二次型?固定起点 x 和方向 v,沿直线定义一元函数 ϕ(t)=f(x+tv)。对 t 求导时,第 i 个输入 xi+tvi 的导数是 vi,把各输入的贡献相加就得到 ϕ′(t)。再套用一次链式法则得到 ϕ″(t)。

ϕ′(t)=∇f(x+tv)Tv,ϕ″(t)=vT∇2f(x+tv)v.

若每点的 Hessian 半正定,就有 ϕ″(t)≥0。取 v=y−x,则 ϕ(0)=f(x)、ϕ(1)=f(y)。一元凸性给出 ϕ(t)≤(1−t)ϕ(0)+tϕ(1),换回 f 就是多元凸性定义。反过来,若 f 凸,沿任意方向的 ϕ 都凸,特别是 ϕ″(0)=vT∇2f(x)v≥0,所以 Hessian 半正定。

为什么不能只看对角线?第25页的 f=x12+3x1x2+2x22 有 Hessian H=[2334],对角线2、4都正。取 v=(3,−2)T,先算 Hv=(0,1)T,再算 vTHv=−2<0。沿这条线,f(3t,−2t)=−t2 向下弯,所以原函数不凸。

原第 30 页

常见凸函数:求导与范数证明分别怎么做

原课件第30页
点击原页可打开 PDF。
  1. 线性函数:f(x)=cTx。梯度是常数 c,Hessian 为零矩阵;零矩阵半正定,所以线性函数凸。
  2. 二次函数:f=12xTPx+qTx+r,其中 P 对称且半正定。梯度 Px+q,Hessian 是 P,所以凸。xk 在二次项的左、右两个 x 中各出现一次,因此求导得 12[(Px)k+(PTx)k]=(Px)k,最后一步用到 P 对称。例如 P=[2114] 时,二次项展开得 x12+x1x2+2x22,求两次偏导就回到 P。
  3. 负熵:f=∑ixilogxi,定义域 xi>0。先用乘积法则:ddxi(xilogxi)=1·logxi+xi·(1/xi)=logxi+1。再求一次导数得 1/xi;不同变量间的二阶偏导为 0。因此 H=diag(1/xi),二次型 ∑ivi2/xi≥0,所以凸。

三种范数:‖x‖1=∑i|xi|,‖x‖2=∑ixi2,‖x‖∞=maxi|xi|。例如 (3,−4) 的三种范数依次为 7、5、4。

范数在某些点不可微,直接用三角不等式和齐次性证明:

‖λx+(1−λ)y‖≤‖λx‖+‖(1−λ)y‖=λ‖x‖+(1−λ)‖y‖.

一般齐次性是 ‖ax‖=|a|‖x‖;此处权重非负,所以可省绝对值。零点不可微不会妨碍函数凸。

对应课堂录音Week02 Part01 00:00:22–00:06:47Week02 Part01 00:06:48–00:07:17
原第 31 页

凸性证明题:如何组织每一步

原课件第31页
点击原页可打开 PDF。

本页用红叉和红勾区分两种证明任务。9月14日课堂说明:这里的一般凸性判别定理证明不考;要掌握的是判断给定函数或集合是否凸。

图中任务要做什么
上半红叉:证明一般判别定理对任意二次可微函数,证明“凸当且仅当二阶导非负”。这是第17–21页讨论的理论推导。
下半红勾:证明具体函数或集合凸题目给定一个明确的函数或集合,由你选择定义、一阶条件、二阶条件等方法完成判断。

具体题按下面的步骤组织:

  1. 先写定义域。检查它是不是凸集。
  2. 再选工具。一元可微函数可检查导数;多元函数先求梯度、再求 Hessian;绝对值或范数可直接用定义与三角不等式。
  3. 写清关键判断。算出 Hessian 后,还要说明为什么它对所有输入都半正定。证明集合凸,则要验证任意两点的凸组合仍满足全部条件。
  4. 给出结论。把刚验证的条件与采用的判别方法连接起来。

例如证明 f(x)=ex 凸:定义域 R 为凸区间;求得 f′(x)=ex、f″(x)=ex>0,对全部 x 成立,所以 f 凸。这里是在使用判别定理。

对应课堂录音Week02 Supplement01 00:04:33–00:05:30Week02 Supplement01 00:15:21–00:19:19
原第 32 页

变量类型:能取小数,还是只能选整数

原课件第32页
点击原页可打开 PDF。

连续变量可以在实数范围内变化,例如功率 2.4 千瓦、速度 1.7 米/秒。离散变量只能取分开的值,例如车辆数 0、1、2,或开关 0、1。

  • x∈Rn:n 个连续变量。
  • x∈{0,1}n:n 个二元变量,常用 1 表示选中、0 表示不选。
  • 连续与离散混合:例如同时决定一家仓库是否开设,以及开设后的供货量。

课件问车道数量是哪种。实际车道条数必须是整数,不能建 2.4 条;如果为了近似分析先允许 2.4,这个模型叫连续松弛,得到结果后还要处理整数限制。

原第 33 页

目标函数:线性、凸、非凸怎样分

原课件第33页
点击原页可打开 PDF。

本页从目标的形状分类:

  • 线性或仿射:f=cTx+d。斜率固定,图像是直线或平面。
  • 凸:例如 f(x)=x2,可弯曲,但始终满足弦在图像上方。
  • 非凸:例如 f(x)=(x2−1)2,可能有多个山谷。它的二阶导 12x2−4 在 x=0 时为负,故在整个实数域上不凸。

线性函数本身也是凸函数,所以这几个标签不是完全排斥的。仅看目标凸还不能断定整个优化问题凸,还要检查变量允许范围和约束。

方向也有关系:凸优化通常最小化凸函数;最大化问题则对应最大化凹函数,或者把目标取负改成最小化。

原第 34 页

为什么凸函数的“≤0 区域”是凸的

原课件第34页
点击原页可打开 PDF。

把所有使函数值不超过0的点收集起来,得到阈值为 0 的下水平集:

G={x:g(x)≤0}.

若 g 凸,任取 x、y 都满足 g(x),g(y)≤0。对 z=λx+(1−λ)y,由凸性:

g(z)≤λg(x)+(1−λ)g(y)≤λ·0+(1−λ)·0=0.

所以 z 仍合法,G 凸。第一个不等号来自函数凸,第二个来自两个端点可行。

例如 g(x,y)=x2+y2−1 凸,条件 g≤0 给实心单位圆盘。若写成 g≥0,得到圆盘外部,中点可能落进圆内,所以不能沿用结论。不等式方向必须一起看。

如果 g 不凸,就直接检查它的约束区域。例如 g(x)=x3 在实数域不凸,因为 g″(x)=6x 在负半轴为负。约束 x3≤0 等价于 x≤0,其可行域仍是凸区间 (−∞,0]。

原第 35 页

为什么凸函数的“=0 区域”却未必凸

原课件第35页
点击原页可打开 PDF。

线性等式 h(x)=0 给超平面,已证明是凸集。但如果 h 只是凸函数,等值集合可能不凸。

例如 h(x,y)=x2+y2−1 是凸函数,等式 h=0 给单位圆周。两点 (1,0)、(−1,0) 都在圆周上,中点 (0,0) 却满足 h=−1,不在圆周上。

为什么上一页证明不适用?凸性只能推出 h(z)≤0,而等式还要求 h(z)≥0,这个方向没有得到。

标准凸规划的等式写成仿射形式,如 Ax=b。遇到非线性等式,可以先检查是否能等价改写。例如 x2=0 和 x=0 允许的是同一个点,改写后就是仿射等式。

原第 36 页

整数规划、混合整数规划、连续优化

原课件第36页
点击原页可打开 PDF。

这页按变量类型给整个问题命名:

类别变量典型决定
整数规划所有决策变量都取整数,课件用二元变量举例哪些设施开设、安排多少台车
混合整数规划一部分整数,一部分连续是否开厂,同时决定生产量
连续优化实数变量各时段的功率、模型权重

例如 z∈{0,1} 表示是否开厂,q≥0 为产量,约束 q≤100z。z=0 时迫使 q=0;z=1 时允许 0≤q≤100。这就是混合整数模型。

二元只是整数变量的一种。即使目标和约束的表达式线性,{0,1} 本身也不是凸集,因为 0 和 1 的中点 0.5 不允许。

原第 37 页

无约束和有约束

原课件第37页
点击原页可打开 PDF。

无约束问题通常写成 minx∈Rnf(x),在目标函数定义的范围内没有额外的等式或不等式。

有约束问题还列出 gi(x)≤0 或 hj(x)=0。这些规则可能把最佳点推到边界上。

例如 f(x)=(x−3)2:无约束时选 x=3,目标为 0;加入 x≤2 后,最优点是 x=2,目标为 1。此时 f′(2)=−2≠0,因为向右虽能下降,却被约束挡住。

因此“令梯度等于 0”适合寻找无约束内部候选点;有约束最优还要考虑哪些方向可走。

原第 38 页

线性规划和非线性规划

原课件第38页
点击原页可打开 PDF。

连续变量下,若目标和所有约束都是线性或仿射表达式,就是线性规划(LP):

mincTx+d,Ax≤b,Cx=e.

A、C 是已知系数矩阵,b、e 是已知右端向量。可行域由有限个半空间和超平面相交得到,所以是多面体。

例如 min2x+3y,条件 x+y≥4,x,y≥0,是线性规划。若目标改为 x2+y2,即使约束不变,也属于非线性规划(NLP)。

非线性规划只要求目标或某个约束有非线性项,并不等于非凸。刚才的平方目标配线性约束仍是凸问题。

原第 39 页

判断标准凸规划,要检查三处

原课件第39页
点击原页可打开 PDF。

标准凸规划写成:

minx∈Df(x),gi(x)≤0,hj(x)=0.
  1. 基础定义域 D 凸,目标 f 凸。
  2. 每个不等式函数 gi 凸,方向统一为 ≤0。
  3. 每个等式函数 hj 仿射,例如 hj=ajTx−bj。

每条凸不等式的合法区域凸,每条仿射等式的合法区域凸,它们与定义域相交后仍凸。这就保证了“在一个凸的可行域上最小化凸目标”的结构。

例如 minx2+y2,条件 x+y=1、x,y≥0:目标 Hessian 为 2I 半正定;等式仿射;非负条件改成 −x,−y≤0,也是凸函数。因此是凸规划。

这个例子也能心算出答案:由 x+y=1 得 y=1−x,且 0≤x≤1。代回目标:

x2+(1−x)2=2(x−12)2+12.

平方最小为0,恰好在 x=1/2;所以 x=y=1/2,最小目标值为1/2。定义域、约束、目标以及最终答案在这里都能逐项对上。

原第 40 页

分类完成后,能知道什么

原课件第40页
点击原页可打开 PDF。

“局部最小”是与附近的可行点比较最好;“全局最小”是与全部可行点比较最好。凸优化的重要性质是:可行域中的局部最小点也是全局最小点。直观上,若远处有更好点,沿连接线稍微走一点就应变好,这与“局部已经最好”矛盾。

用定义写这个理由:若 x* 是局部最优,而存在可行 y 使 f(y)<f(x*),那么对很小 t>0:

f((1−t)x*+ty)≤(1−t)f(x*)+tf(y)<f(x*).

这个点可行、又任意接近 x*,与局部最优矛盾。

看一个局部最小比全局最小差的例子。在 [−1,2] 上最小化 f(x)=−x2。在 −1 附近只能往右走,函数先上升,因此 −1 是局部最小点,值为 −1。区间内离 0 最远的是 2,所以全局最小值是 f(2)=−4。整数问题还要处理离散选择,算法也会不同。

实际检查顺序是:变量连续还是离散 → 有哪些约束 → 目标凸不凸 → 不等式方向与凸性 → 等式是否仿射。得到类别后,再选择求解方法。