convex optimization basics¶

optimization terminology¶

凸优化问题的形式和普通的优化问题类似，但是要求约束条件的函数都是凸的。并且如果有取等的约束条件，那么该函数必然是仿射变换。原因在于本来约束条件不能是等式，而都是小于等于的形式，但是一个等式能被等价地写作两个小于等于的形式，即该函数小于等于0，以及相反符号的该函数小于等于0，那么两者都应该是凸函数，符合条件的只有仿射变换。

solution set¶

一个凸优化问题的解的集合一定是凸的。如果我们优化的函数是严格凸的，那么解集应该只有一个点。

local minima are global minima¶

注意这个local的定义，要求我们取到的minima不是边界点，因为这个local的范围应该是以local optimal value为中心的一个2-范数球。

rewriting the constraints¶

对于一个program，我们可以把他的限制条件改写成一个，也就是\(x \in C\)，这个C就相当于整个feasible set。个人认为，这样的做法，是为了在后面某些定理的证明或者描述过程中，具体的限制条件不要紧的情况下使用的。而且进一步的，我们可以把整个函数的定义域扩充成全集，但是要把criterion function改写为原来的criterion function 加上一个indicator function（指定的范围为集合C）。

first-order optimality condition¶

对于一个program（目标函数可微），一个可行点x是最优点的充要条件为这个点的梯度与任意可行点y与该x的差值的点积大于等于0。换句话说，如果x是最优点，那么从这点出发的所有可行的方向都应该和这点的梯度夹角小于等于90度。

remark：如果可行域是\(\mathbb{R}^n\)，那么x的梯度应该为\(\mathbb{R}^n\)空间中的零向量。所以其实我们可以想，如果这个最优点是落在一个很光滑的坑里面，那么他的梯度应该就是零向量。或者我们说的更加直接一点，因为条件中有了目标函数可微，所以如果最优点是凸集的一个内点，那么这点的梯度应该为零向量。如果这个点是凸集的边界点，那么其负梯度应该指向集合外部。

transformation and change of variables¶

如果函数h是一个单调增函数，那么要求函数f(x)的最小值，可以转化为求函数h(f(x))的最小值，两者完全等价，但是套上函数h之后，也许就得到了凸函数，让问题变得非常容易解决。

remark：最典型的例子就是最大似然估计

我们不仅可以对函数外层做复合，我们也可以先对自变量做变换，但是这要求更严格的条件，具体的方式见原课程notes，但是要注意的是，对定义域做变换，最常用的变换仍然是线性变换。

eliminating equality constraints¶

回忆一下我们在线性代数中所学的，对于一个线性方程组，我们总能把解写成通解的形式，这意味着，对于线性的约束，我们能够将自变量换成这种通解的形式，然后就只用考虑非等号的约束条件。当然要注意，非等号的约束的自变量也必须写成通解的形式。

remark：这种做法不一定是最好的，因为表示通解的矩阵可能非常dense，不管A是不是sparse，这会导致计算量的增加

relaxing nonaffine equalities¶

如果我们在一个优化问题中（注意是普遍的优化问题，不一定是凸优化），扩充可行域，那么我们得到的optimal value将比原来的优化问题的optimal value更小或者相等。通常我们这样做是为了将一个非凸的问题转化为一个凸的问题，或者将一个困难的凸的问题转化为简单的凸的问题。