线性代数回顾

范数（Norms）

  • 向量的范数定义如下：设为上的向量空间，为到上的映射，若满足：

    • 非负性：，且等号成立当且仅当；
    • 正齐性：；
    • 三角不等式：.

    则称为范数。

  • 在空间中满足条件的范数不止一个，最常见的如范数，范数（也称欧几里得范数）等。这里我们主要讨论一类重要的范数：范数。其定义如下：

    • 设，则上的范数表示为
  • 当，定义无穷范数
- 对第二个等号的简单证明：设$M=\max_i|x_i|$，则若$M=0$，结论显然成立；若$M>0$，则
 
  可以利用夹逼得到
 
  故等号成立。

不等式

  • 关于向量的范数，有一些重要的不等式（这些不等式可以确定一些变量的上下界，因而有助于求解优化问题）：
  1. 柯西-施瓦茨不等式（Cauchy-Schwarz Inequality）
    设向量，则有

这个不等式只涉及空间上的范数，可以用二维向量内积的极坐标表示证明。（向量在向量上的投影可以用表示，这对应最小二乘法在的情形）
实际上我们可以将其推广到任意空间上（之后会详细讨论）。
2. 赫尔德不等式（Hölder’s Inequality）
设且（这里也称为赫尔德共轭对）.那么对任意，有

证明涉及卷积的知识，所以这里先不证明。

  • 下面给出一个应用的例子：

范数球（Norm-balls）

  • 我们考虑以下优化问题：

其中为给定向量。

  • 直接求解这个问题比较复杂。我们可以先从简单情形入手：取三种情况，此时的范围可以用下图表示（实际为高维“范数球”）：
    normball
  1. （绿线内区域）：则目标函数可表示为

又因为是固定的，所以当，即时得到最大值，取到最大值的条件为（即与同向的单位向量）。
2. （蓝线内区域）：则目标函数可表示为

而，即的每个分量取值范围相互独立。那么我们就可以这么取值：若，则令，若，则令（则任意取）此时

显然这是最大值（相当于个独立的优化问题）
3. （红线内区域）：这个情况推导会略复杂一些。我们首先推出上界：

下面我们就要证明这个上界能够取到。我们根据推导逐步分析：

  • 首先，第一个和第二个不等号要取等需要所有均同号且同号或为；
  • 其次，第三个不等号要去等需要。那么我们可以让不是最大值的对应的为，只留下取到最大值的对应的；
  • 最后，第五个不等号要取到需要，即上面的。

上面三个条件都能取到，所以上界就能取到，上界即为最大值。

通过上面这些特殊情况，我们可以归纳出以下规律：当约束为范数时，最大值为，其中满足.即：

  • 事实上，可以由赫尔德不等式推出：

不过反向的不等号的证明比较复杂，这里不讨论。

  • 这里的和也被称为对偶范数（dual norm），这体现了最优化问题的对偶性（之后我们会详细涉及）。
  • 总结一下这里用到的两个解题思想：
    1. 将向量问题转化为标量问题：向量优化问题往往比较复杂，尝试将其转化为各个分量的独立优化问题，会大大降低解决难度；
    2. 证明最优性时，可以先给出其上（下）界，再举例说明上（下）界可以取到。简单而言就是先给出不等式，再化不等式为等式。