杂记

好久没有更新这个blog了，研究生生活浑浑噩噩的过了一年半了，发现生活和学习中各种问题被自己弄得乱七八糟的，另外成功延续了本科时候考完就忘的优良传统。当时convex optimazition和高等理论计算机上的要死要活的，每天花不少时间刷题，结果没过多久基本就只能记着一堆定理的名字了。。。

考虑到这些决定还是维护一个blog整理一下乱七八糟的生活。

这学期基本忙在TA的事情上，中间做了一些和Multi-armed Bandit有关的东西。学期开始和老板说想看看hashing theory，因为比较将来还是想去工业界的，但是由于一学期杂七杂八的事情就这么拖着了。

接下来时间会多一些，大概做几个打算

一个是把Bubeck的Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems看完，一个是开始看Ping Ling的publication list。另外可能考虑把blog搬个家，毕竟自己coding太弱了，除了搞acm时候写过一些算法题，做模式识别大作业什么的应付一下，其他工程性质的coding完全没接触过。

最优化方法第7章的内容比较多，稍微做了一下逻辑整理，里面各种定理只表达了下大意没有做严格阐述

对于一个优化问题$min f(x)$, 

一、原问题无约束

   1.目标函数为一般函数

   1).一阶条件：

     如果$\bar{x}$是局部极小点，则在该点梯度为0

   2).二阶条件：

     如果$\bar{x}$是局部极小点，则在该点Hessian矩阵半正定；如果梯度为0且Hessian矩阵在$\bar{x}$微分领域内半正定，则$\bar{x}$是局部极小点。

   2.目标函数为凸函数

   1).$\bar{x}$为全局极小点的充要条件是该点梯度为0

二、原问题只有不等式约束

    1.原问题为一般规划问题

    1).几何最优性条件：如果$\bar{x}$是问题的局部最优解，则在该点的下降方向集与局部约束方向锥交集为空

    2).代数最优性条件:

    (1).如果$\bar{x}$是局部极小点,则在该点一定满足Fritz John条件

    (2).由于Fritz John条件中$w_0$可能为0，这时无法提供任何关于目标函数的信息，因此对Fritz John条件加强一条：所有 起作用约束$g_i(\bar{x})$的梯度向量$\nabla g_i(\bar{x})$在该点线性无关,即有KKT条件

    则如果$\bar{x}$是局部极小点，该点一定满足KKT条件

    2.原问题为凸规划问题

    1).如果$\bar{x}$点KKT条件满足，则$\bar{x}$是全局极小点；如果$\bar{x}$是全局极小点，那么$\bar{x}$一定满足KKT 条件

三、原问题具有一般约束

    几个比较不太直观的地方

    *此时如果等式约束不是线性约束的话，仅用梯度无法描述在可行域的运动，因此需要引入一族曲线族，以点在曲线切线方向来定义运动方向。因此可以将原来的可行方向推广至序列化可行方向，也即$\textbf{切锥}$。

    * $\bar{S}$和$\bar{G}$定义看起来很奇怪，但是仔细看一下会发现如果一个局部极小点$\bar{x}$限定在$\bar{S}$中运动，那么在不改变原来的$\bar{w},\bar{v}$的情况下后面几个式子不会发生改变。而$\bar{G}$定义了一组方向，如果沿这组方向运动的话不会改变$\nabla_x L(x, w, v)$的后两项。或者简单来说，如果$\textbf{限定在S并只沿着G的方向运动}$，那么对于Lagrange乘子问题的变化只会反应到$f(x)$上，从而可以分析目标函数的变化,进而转化为考虑$\nabla^2_xL$在$\bar{G}$的半正定性

    1.原问题为一般规划问题

    1).几何最优性条件：如果$\bar{x}$是一个正则点，则在该点的 $\textbf{下降方向集}$, $\textbf{局部约束方向锥}$， $\textbf{切向量集}$三者无交集

    2).代数最优性条件:

    (1).如果$\bar{x}$是局部极小点，则该点一定满足Fritz John条件

    (2).如果$\bar{x}$是局部极小点且为正则点,则该点一定满足KKT条件(注意存在$\bar{x}$不是正则点且不符合KKT条件但是局部极小点的情况)

    (3).如果$(\bar{x}, \bar{w}, \bar{v})$是Lagrange乘子问题的一组解且$\nabla^2_xL$在$\bar{G}$正定，则$\bar{x}$是严格局部极小点；如果$\bar{x}$是局部极小点，$(\bar{x}, \bar{w}, \bar{v})$是Lagrange乘子问题的一组解且$\bar{G} = \bar{T}$成立，则$\nabla^2_xL$在$\bar{G}$半正定。其中$\bar{G} = \bar{T}$等价于$\bar{x}$为正则点。

    2.原问题为凸规划问题  

    1).如果$\bar{x}$点KKT条件满足，则$\bar{x}$是全局极小点；如果$\bar{x}$是全局极小点，那么$\bar{x}$一定满足KKT 条件

    最近在最优化方法课上讲到单纯型法，尽管陆老师给出了很详细的公式推导，但是自己脑子实在太笨对着大段公式反应不过来。于是惯例花了些时间想了想这堆公式自己的理解。如果有理解错误的地方请读者指出。

    首先抛开单纯型法，如果最暴力的方法去找LP问题的最优解应该如何做呢？由于每个基本可行解对应着一个极点，而LP问题被证明最优解一定在极点处取到。同时每个基本可行解一定对应有一个基矩阵，那么直接枚举基矩阵就得到一个指数级的算法。实际上单纯型法最坏的复杂度确实是指数的。

    下面说下单纯型法中几个概念自己的直观理解：

    1.本质上单纯型法就是对上述暴力算法的优化算法，通过选择最大检验数迅速收敛到最优解。

    2.检验数的理解：检验数就是表示 非基变量 在变化时引起的函数值的变化程度。从检验数的形式化表示来看$z_j - c_j = c_BB^{-1}P_j - c_j$, 很容易发现$c_BB^{-1}P_j$中的$B^{-1}P_j$就是变量$x_j$系数在基$B$下的坐标。那么当$x_j$变化时，反应在基$B$下的变化会通过$c_B$影响到函数值，因为第一项为$c_BB^{-1}P_j$，同时由于本身的$c_j$还会对函数结果造成影响，并且两者在推导中符号相反，因此得到检验数的表达为：$c_B$乘该变量系数在当前基下的坐标减去原本的$c_j$

    3.进基出基的理解：由于某个非基变量$x_j$在每变化1时，$x_B$减少的一个单位的其在基$B$下的系数，而函数结果减少一个单位的检验数。因此非基变量增加值为$min\{\frac{\bar{b_i}}{y_{ik}}|y_{ik}>0\}$

    4.为什么在单纯型表里刚好就是高斯消元的结果：其实一句话就能说清楚了，单纯型本质就是一个换基的过程，原基$B$换到新基$B'$时，相当于对系数矩阵施加$B'^{-1}$, 所以结果就是高斯消元的结果。同理最后一行检验数和函数值本质也是一个换基的结果，但是好像没有系数矩阵那么直观了。

    悲剧的算导忘记带回家了，下了本电子版把这个算法学了一下。貌似有不少900+ms估计是水过去的。正解是快速傅里叶变化，原理和实现都很简单，如果之前学过拉格朗日插值的话一句话就能理解这个算法了。

    直接贴代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <complex>
using namespace std;
const int maxint = -1u>>1;
template <class T> bool get_max(T& a, const T &b) {return b > a? a = b, 1: 0;}
template <class T> bool get_min(T& a, const T &b) {return b < a? a = b, 1: 0;}

const int maxn = 1 << 18;

typedef complex<double> CP;
const double pi = acos(-1.0);

int n;

void fft(CP* a, CP* A, int n, bool rev){
    int lg2n = int(log(double(n))/log(2.0)+0.5), x;
    for(int i = 0; i < n; i ++){
        x = 0;
        for(int j = 0; j < lg2n; j ++) if(i&(1<<j)) x += (1<<(lg2n-1-j));
        A[x] = a[i];
    }
    for(int s = 1; s <= lg2n; s ++){
        int m = 1 << s;
        double p = 2.0 * (rev ? -1 : 1) * pi / m;
        CP wm(cos(p), sin(p));
        for(int k = 0; k < n; k += m){
            CP w(1);
            for(int j = 0; j < m/2; j ++){
                CP t = w * A[k+j+m/2];
                A[k+j+m/2] = A[k+j];
                A[k+j] += t;
                A[k+j+m/2] -= t;
                w *= wm;
            }
        }
    }
    if(rev){
        CP tmp(1.0/n, 0.0);
        for(int i = 0; i < n; i ++) A[i] *= tmp;
    }
}

CP a[maxn], b[maxn], c[maxn], A[maxn], B[maxn], C[maxn];
int out[maxn];
char str[maxn];

bool init() {
    if(scanf("%s", str) != 1) return false;
    int l1 = strlen(str);
    reverse(str, str + l1);
    for(int i = 0; i < l1; i++) a[i] = CP(str[i] - '0', 0.0);
    scanf("%s", str);
    int l2 = strlen(str);
    reverse(str, str + l2);
    for(int i = 0; i < l2; i++) b[i] = CP(str[i] - '0', 0.0);
    n = 1;
    while(l1 * 2 > n || l2 * 2 > n) n <<= 1;
    for(int i = l1; i < n; i++) a[i] = CP(0.0, 0.0);
    for(int i = l2; i < n; i++) b[i] = CP(0.0, 0.0);
    for(int i = 0; i < n; i++) c[i] = C[i] = A[i] = B[i] = CP(0.0, 0.0);
    return true;
}
        
    
int main() {
    while(init()) {
        fft(a, A, n, false);
        fft(b, B, n, false);
        for(int i = 0; i < n; i++) C[i] = A[i] * B[i]; 
        fft(C, c, n, true);
        memset(out, 0, sizeof(out));
        for(int i = 0; i < n; i++) {
            int x = (int)round(real(c[i]));
            out[i] += x;
            out[i + 1] += out[i] / 10;
            out[i] %= 10;
        }
        while(n > 1 && !out[n - 1]) n--;
        for(int i = n - 1; i >= 0; i--) {
            printf("%d", out[i]);
        }
        printf("\n");
    }
    return 0;
}