Skip to content

优化基本理论与方法

核心课程，要好好学

怎么不说评分也不布作业呢

与机器学习之间的关系

  • 机器学习：训练映射，最小化损失函数

  • 凸优化：最小化损失函数的优化方法

  • 机器学习的任务主要分为分类（离散）和回归（连续）

分类（Classification）- 0，1 损失

  • 分到正确的类 - 损失为 0
  • 反之损失为 1
  • 0，1 情况下，最小化损失函数是 np 问题，不好解决
  • 常用 Hinge Loss 替代，更好计算
  • 其他的 Loss 函数
    • Squre loss
    • Logistic loss
    • Cross entropy loss（交叉熵）

最大似然估计（Maximum Likelihood Estimation View）

对数化把积转化为和

一般范式

更细的分类

  • 有约束问题
  • 无约束问题

  • 光滑问题：\(f_i(x)\) 都可微

  • 最优解 - 全局最优解

  • 局部解 - 局部最优解

一个常用于证明的方法 - 对任何输入，返回 x = 0

不同类型的 oracle

  • 零阶
  • 一阶
  • 二阶

迭代法

alt text

上述方案有两个最昂贵的步骤

  • 解析复杂性
  • 算数复杂性

n 维箱子约束问题

用无穷范数测量距离

Lipschitz 连续

均匀网格法

构造 \((p+1)^n\) 个点，找出最小的点

  • 零阶迭代方法
  • 定理

上下界估计

复习：线性代数

范数

一阶方法

负梯度方向是最快局部下降

二阶方法

难以理解

f(x) 在 x 处泰勒展开

Hessian - 对称方阵

正半定

正定

\(C^{1.1}_L(R)^n\) 类

引理 1.1

引理 1.2（几何解释）

\(C^{2.2}_M(R)^n\) 类

c3c1 - 凸函数的定义和几条性质

c3c2 - 光滑强突函数

  • F1,1_L - 梯度李普希思连续，等价条件
  • 强突函数的定义、引理、性质和等价条件

c3c3 - lower complexity bound

c3c4 - 上面两个问题类的梯度方法

c4c1 - 衡量强凸函数梯度方法的速度、Accelerated GD（加速梯度算法），定义 estimate sequence

c4c2 - Accelerated GD, Optimal Scheme(Analysis & variant) 衡量下降速度? 完全看不懂

c4c3 - Convext Set 定义：αx+(1−α)y∈Q

  • 引理：level set of 凸集是凸集或空集的 epigraph 是凸集
  • 重要运算 - 凸集的 交/和/笛卡尔积/数乘/Convex hull 是凸集
  • 凸集情况下〈∇f(x∗), x−x∗〉≥0，x* 是 solution
  • 某种情况下有唯一解

c4c4 - Gradient Mapping and the Algorithm（定义好奇怪，不懂

c5c1 - General Convex function - can be nondifferentiable

c5c2 - General Convex

  • 连续性和可微性 - locally bounded and Lipschitz 连续
  • 一些定理
    • Hyperplane
    • projection
    • main theorems

c6c1 - subgradient, Subdifferential

问题：

  • Subdifferential
  • Supporting Hyperplane at the boundary point of a convex set