不同优化问题要用不同方法。就像解一元方程前要看它是一次还是二次,优化前也要检查变量、目标和约束的性质。
这一讲先学“凸”:集合里两点之间的线段是否还在集合内;函数图像是否位于两点连线下方。再用这两个概念区分连续、整数、线性、非线性和凸优化问题。
分类可以同时成立。例如一个线性规划通常既是连续优化,也是有约束凸优化。
共 40 页。按原课件顺序,左侧看原页,右侧读讲解。
直接用凸函数定义,需要检查所有点对和它们之间的弦。为了更方便判断,改看每个点的切线。对于定义在凸区间上的可微一元函数,凸性等价于:
右边是在 x 处作切线,再走到横坐标 y 时预测的高度。 是切线斜率, 是横向移动量,两者乘积是切线预测的高度变化。
图中真实变化为 ,切线预测变化为 ;凸函数的真实高度至少有切线那么高。
用 检查。任取切点 ,有 、。在横坐标 y 处,曲线高度与切线高度之差可化成一个平方。
任意 x、y 都满足该不等式,因此这个函数凸。比如切点 x=1、观察点 y=2,切线高度是 3,曲线高度是 4。
在 f(x)=x² 上固定 x=−1。移动另一个点,再改变区间内的位置 t。
假设整个区间内 。按课件用分部积分证明时,取 连续。先取 。积分范围内 ,所以被积函数非负。
t 是积分中的临时变量。选 ,是因为它在上端 时为0;选 ,积分后便剩下 ,能接回切线的斜率。分部积分中 :
所以 。若 ,把上下限换过来:,所以同一等式继续成立。若 y=x,则两边都为0。
这样对所有 x、y 都得到切线条件,再由第18页的证明得到凸性。积分式也可理解为“真实函数值减去切线预测值”的精确差额。
用 检查:。函数真实增量是 ,切线预测增量为 ,两者正好差1。
用中值定理也能证明。对任意 ,对 用中值定理,得到 ,所以 不减。再对 用中值定理,得到 。若 ,则 ,而 。若 ,则 ,而 ,乘上它之后不等号反向。两种情况下都有 。
对称矩阵满足 ,即主对角线两侧的元素镜像相同。这样的 H 半正定,简称 PSD,是指:
v 可以理解为任选的方向。判断 PSD 的常用办法有:所有特征值非负;把 H 写成 ;或者检查所有主子式非负。
特征值 表示一个特殊方向上的放大倍数:若非零向量 v 满足 ,则 。负特征值会直接给出一个负二次型方向。
为何分解法有效?若 H 为 ,L 可以是 的实矩阵;于是 是 向量。若 ,则:
这里的“所有主子式”包括任意选取相同行、列编号得到的主子阵行列式;“顺序主子式”只看左上角逐渐扩大的那些。右图的嵌套方框标出的正是用来求顺序主子式的子阵。若选第 1、3 行和第 1、3 列,得到的也是主子阵,行列式也是主子式,但这个子阵没有出现在嵌套方框里。不能只用“顺序主子式非负”判断 PSD:例如 的顺序主子式是 0、0,但取 ,就有 ,所以不是半正定。若对称矩阵的所有顺序主子式严格为正,则它正定,因此也半正定。
在凸开域上,二次可微的多元函数凸,当且仅当每个点的 Hessian 都半正定:
表示矩阵半正定。它要求所有方向的曲率非负,而不只是矩阵对角线非负。
为什么检查二次型?固定起点 x 和方向 v,沿直线定义一元函数 。对 t 求导时,第 个输入 的导数是 ,把各输入的贡献相加就得到 。再套用一次链式法则得到 。
若每点的 Hessian 半正定,就有 。取 ,则 、。一元凸性给出 ,换回 f 就是多元凸性定义。反过来,若 f 凸,沿任意方向的 都凸,特别是 ,所以 Hessian 半正定。
为什么不能只看对角线?第25页的 有 Hessian ,对角线2、4都正。取 ,先算 ,再算 。沿这条线, 向下弯,所以原函数不凸。
本页用红叉和红勾区分两种证明任务。9月14日课堂说明:这里的一般凸性判别定理证明不考;要掌握的是判断给定函数或集合是否凸。
| 图中任务 | 要做什么 |
|---|---|
| 上半红叉:证明一般判别定理 | 对任意二次可微函数,证明“凸当且仅当二阶导非负”。这是第17–21页讨论的理论推导。 |
| 下半红勾:证明具体函数或集合凸 | 题目给定一个明确的函数或集合,由你选择定义、一阶条件、二阶条件等方法完成判断。 |
具体题按下面的步骤组织:
例如证明 凸:定义域 为凸区间;求得 、,对全部 x 成立,所以 f 凸。这里是在使用判别定理。
“局部最小”是与附近的可行点比较最好;“全局最小”是与全部可行点比较最好。凸优化的重要性质是:可行域中的局部最小点也是全局最小点。直观上,若远处有更好点,沿连接线稍微走一点就应变好,这与“局部已经最好”矛盾。
用定义写这个理由:若 是局部最优,而存在可行 使 ,那么对很小 :
这个点可行、又任意接近 ,与局部最优矛盾。
看一个局部最小比全局最小差的例子。在 上最小化 。在 附近只能往右走,函数先上升,因此 是局部最小点,值为 。区间内离 0 最远的是 2,所以全局最小值是 。整数问题还要处理离散选择,算法也会不同。
实际检查顺序是:变量连续还是离散 → 有哪些约束 → 目标凸不凸 → 不等式方向与凸性 → 等式是否仿射。得到类别后,再选择求解方法。