最优化基础知识总结（1）

最优化基础知识总结（1）

1. 最速下降方向：负梯度方向

2. 梯度：沿各个坐标轴方向的偏导数组成的函数向量。

3. 方向导数：梯度·某一方向的单位向量，$(\nabla f(X){)}^T\cdot P/\Vert P\Vert$。

4. 黑塞矩阵：二阶偏导数，按列排列。第一列，为$f_1(X)$的偏导数；

5. 雅各布矩阵：向量值函数的一阶偏导数，按行排列。第一行，为$\vec{f}(X)$的第一个分量的梯度。

   1. 对于一个f:Rⁿ->R的多元数量值函数，黑塞矩阵和雅各布矩阵互为转置矩阵，黑塞矩阵按列排，雅各布矩阵按行排。

6. 典型函数的梯度和黑塞矩阵：

   1. $f(X)=X^{T}AX+b^{T}X;\nabla f(X)=(A+A^T)X+b;{\nabla }^{2}f(X)=A+A^T;$

   2. $f(X)=\Vert X{\Vert }_2;\nabla f(X)=\frac{1}{\Vert X{\Vert }_2}X;{\nabla }^{2}f(X)=\frac{1}{\Vert X{\Vert }_2}(E_n-\frac{X{X}^T}{\Vert X{\Vert }_2^2});$

   3. $$\begin{gathered} f(X)=\exp (g(X)+h(X));\nabla f(X)=\exp (g(X)+h(X))\cdot (\nabla g(X)+\nabla h(X)); \\ {\nabla }^{2}f(X)=\exp (g(X)+h(X))\cdot [(\nabla g(X)+\nabla h(X))\cdot (\nabla g(X)+\nabla h(X){)}^T+{\nabla }^{2}g(X)+{\nabla }^{2}h(X)]; \end{gathered}$$

7. 无约束优化问题的最优性条件：$X^{\star }$驻点，$\nabla f(X^{\star })=0$

   1. 一阶条件：

      1. 必要条件：极小值在驻点处取得

   2. 二阶条件：

      1. 必要条件：若$X^{\star }$是局部极小点，则${\nabla }^{2}f(X^{\star })$半正定。
      2. 充分条件：若$X^{\star }$是驻点，且${\nabla }^{2}f(X^{\star })$正定，那么$X^{\star }$是严格局部极小点。
      3. 注意：二阶条件不能更改，比如充分条件不能弱化成半正定。

8. 凸组合：$Y=k_1{x}_1+k_2{x}_2+...+k_n{x}_n$，若$k_1+k_2+...+k_n=1$，则称Y是X的凸组合。

9. 凸集：欧式空间的一个集合，其中任意两点之间的连线，仍然属于该集合，则称之为凸集。（等价定义：集合S中任意有限个点的凸组合仍属于该集合。）

   1. 符号语言：$a{x}_1+(1-a)x_2=x\in S$
   2. 超平面：{P^TX=a, P is a known n-dimentional vector}
   3. 半空间：{P^TX<=a}。
   4. 射线：{X = X⁰+aP, a>=0} P是方向向量
   5. 多面集：{AX<=a}。有限个半空间的交集
   6. 凸锥： { ∑ i = 1 k λ i α i ∣ λ i > = 0 , i = 1 , 2 , ⋯   , k } \{\sum_{i=1}^k \lambda_i \alpha_i|\lambda_i>=0,i=1,2,\cdots,k \} {∑i=1k​λi​αi​∣λi​>=0,i=1,2,⋯,k}向量集的非负线性组合。
   7. 多面锥：{AX<=0}
   8. 凸集的交集仍为凸集。

10. 多面集表示定理

11. 凸函数：可行域为非空凸集+$f(\alpha X1+(1-\alpha )X2)\le \alpha f(X1)+(1-\alpha )f(X2)$

    1. 二阶条件：Hesse矩阵存在且为半正定矩阵。（H为正定矩阵，不一定是严格凸函数）
    2. 一阶条件：$f(X^2)\ge f(X1)+{\nabla }^{T}f(X^1)(X^2-X^1)$
    3. $f(X)=X^{T}AX+b^{T}X+c$, A为半正定矩阵。（若A为正定矩阵，则是严格凸函数）
    4. 詹森不等式（凸函数定义的推广，凸函数的充要条件）：$f({\sum }_{i=1}^m{\lambda }_i{X}^i)\le {\sum }_{i=1}^m{\lambda }_{i}f(X^i)$
    5. 当f(x)=ln(x)的时候，詹森不等式可推出为HÖlder不等式：$|X^{T}Y|\le \Vert X{\Vert }_p\Vert Y{\Vert }_q,1/p+1/q=1$

12. 极点：非空凸集S，$x\in S$，如果x不能表示为任意两个不同点的凸组合，那么称x为极点。（二维平面上， { x ∈ R 2 ∣ x < = r } \{x\in R^2|x<=r\} {x∈R2∣x<=r},圆周上的点均为极点）

13. 极方向：对于一个闭凸集S，如果方向d不能表示任意两方向的正的线性组合，则称为极方向。对于集合S中的任意一个点，沿该向量d引出的射线均包含于S中，则称d为集合S的一个方向。有界集没有方向。

14. 保凸运算：f(X)是凸函数，g(X)是凸函数

    1. 仿射变换：f(AX+b)是凸函数。
    2. 透射变换：
    3. 取最大值：max{f(X), g(X),…}是凸函数
    4. 非负求和运算：f(X)+g(X)仍然是凸函数。
    5. 积运算：f(X)g(X)是凸函数，当f(X) g(X)非负且单调递增时成立。

15. 凸规划：目标函数和约束条件都是凸的。

    1. 凸规划的最优解的充要条件：X*为稳定点：$(X-X^{\star }{)}^T\nabla f(X^{\star })\ge 0$
    2. 局部最优解为全局最优解。
    3. 最优解集为凸集。
    4. 凸规划的目标函数为严格凸函数时，若存在最优解，则最优解唯一。

    	无约束优化问题的最优性条件	凸函数的判定	凸规划的最优性条件
    一阶充分		f(Y)>=f(X)+gT(X)(Y-X)	X*是稳定点，则f(X*)是局部极小值
    一阶必要	极小点在驻点处取得	f如果是凸函数，则上式成立（取不等号，f是凸函数；取等号，f是严格凸函数）	若X*是局部极小点，则X*是稳定点。
    二阶充分	H(X*)正定，且X*驻点，则严格局部极小点	H(X)半正定，则f是凸函数；H(X)正定，则f是严格凸函数。
    二阶必要		f是严格凸函数或者是凸函数，则H(X)半正定。且X是在整个凸集S上均半正定。

    ---

16. 线性规划：凸规划的一种，线性函数也是一种凸函数。

    1. 顶点：基本可行解，既是基本解又是可行解。；不能表示为可行域中其它任意两个点的凸组合。
    2. 基：A的列向量组的一个线性极大无关组，记作B。A是一个宽矩阵。
    3. 基本解：BX=b有惟一解，X=B^-1b，即是基本解。
    4. 图解法：针对二维线性规划，可采用图解法；
    5. 最优解必在顶点处取得。

17. 标准形式：
    $$\begin{gathered} min:C^{T}X \\ s.t.:AX=b \\ X\ge 0 \end{gathered}$$

    1. 松弛变量：≤加一个非负变量化为=。松弛变量的取值能够判断该约束是积极约束还是非积极约束，即该约束是在可行域的边界还是可行域的内部。
    2. 剩余变量：≥减一个非负变量化为=。
    3. 自由变量：如果$\exists x_i\in R,令x_i=x_i^{+}-x_i^{-};x_i^{+},x_i^{-}\ge 0$，将原式中的xi替换即可。
    4. b要求非负：确保在迭代过程中解始终在可行域内。

18. 单纯形法：
    1. 最优解：所有判别数均小于0时。
    2. 无有界最有解条件：判别数大于0，所在列$P_j<\vec{0}$。
    3. 判别数：${\sigma }_j=C_B^T{B}^{-1}{P}_j-c_j$，B为基，j=1,2,……,n；通常B会人为设计为E。
    4. 进基列：选择判别数最大的列。使得迭代更加有效，即每次迭代函数值尽可能多的下降。
    5. 进基变量：选${\min }_i\frac{bi}{a_{ik}}|a_{ik}>0$。确保初等行变换不会将b变为负值。
    6. 转轴：初等行变换不改变解空间。

19. 判别数：${\sigma }_j=C_B^T{B}^{-1}{P}_j-c_j$

    1. $$\begin{gathered} A=(B,N),C=(C_B,C_N{)}^T \\ X=(X_B,X_N{)}^T\ge 0 \\ AX=b=B{X}_B+N{X}_N \\ {X}^0=(X_B^0,0{)}^T,A{X}^0=b=B{X}_B^0,f(X^0)=C_B^T{X}_B^0=C_B^T{B}^{-1}b \\ f(X)=C_B^T{X}_B+C_N^T{X}_N=C_B^T{B}^{-1}(b-N{X}_N)+C_N^T{X}_N=f(X^0)-(C_B^T{B}^{-1}N-C_N^T)X_N \\ f(X)-f(X^0)\ge 0,C_B^T{B}^{-1}N-C_N^T\le 0 \end{gathered}$$

    3. B是基，N是非基

    4. X⁰是最优解，是基本可行解，非基变量为0。

20. 两阶段法：出发点是原线性规划A中，不一定直接存在单位矩阵，如果使用非单位矩阵作为基，在计算判别数时，需要矩阵求逆，这是我们不希望出现的，因此引入人工变量直接构造单位矩阵。实际上，更严重的一个问题是，不能直接确定基可行解。当选定一组线性无关的列向量构成B，B^-1b不一定大于0，那么只能重新选择一组线性无关的列向量，去尝试求得一个可行的基本解。

    实际上，此方法，和初等行变换求矩阵逆有相似之处

    1. 辅助线性规划：引入人工变量，构造单位矩阵，并更换目标函数为y1+y2+…+ym；

    2. 求解辅助线性规划，如最优解(Y0,X0)，对应的函数值>0，则原规划无可行解；若=0，则将（0，X0）作为原线性规划的初始基本可行解。

    3. 如果Y*不等于0，则原线性规划无可行解。

    4. 值得注意的是，在第一阶段使用单纯形方法求解的时候，基变量有两种情况：

       1. 全在X里面，那么直接驱走所有人工变量，此时的X0作为第二阶段的初始基本可行解。
       2. 部分在Y里面：此时的yk为基变量，那么其所在行对应的bk=0，不等于0则原规划无可行解
          1. 如果所在行除了yk，其于值都为0，那么该行的约束等价于1*yk=bk=0，等于说原本的AX=b，有重复（等价）的行，直接驱走yk，删掉该行约束就行了。
          2. 如果所在行除了yk，还有值不为0，那么只能是某些个x不为零，相当于1*yk+akj*x_i=bk=0，由于bk等于0，直接把akj当作主元转轴就可以了。该行约束相当于A_k X=0，因此不需要考虑akj的正负，也不用考虑大小，不为0即可。

    5. 下题用两阶段法就比较简单：

       1. m i x : 2 x 1 + 3 x 2 + x 3 s . t . : x 1 + 4 x 2 + 2 x 3 ≥ 8 3 x 1 + 2 x 2 ≥ 6 x i ≥ 0 , i = 1 , 2 , 3
          mix:2x1+3x2+x3s.t.:x1+4x2+2x3≥83x1+2x2≥6xi≥0,i=1,2,3" role="presentation">mix:s.t.:2x1+3x2+x3x1+4x2+2x3≥83x1+2x2≥6xi≥0,i=1,2,3$$\begin{array}{rl}mix:& 2x_1+3x_2+x_3\\ s.t.:& x_1+4x_2+2x_3\ge 8\\ & 3x_1+2x_2\ge 6\\ & x_i\ge 0,i=1,2,3\end{array}$$
          mix:s.t.:​2x1​+3x2​+x3​x1​+4x2​+2x3​≥83x1​+2x2​≥6xi​≥0,i=1,2,3​

21. 大M法：出发点是两阶段法，引入和人工变量，并更换了目标函数，大M法则只需要添加惩罚项，并且原线性规划最优解，就在辅助线性规划中。

    1. 辅助线性规划：引入人工变量，并加入惩罚项$M{e}^{T}Xa$，其中M是一个充分大的数。

    2. 求解辅助线性规划，最有解为（X0,Xa），若e^TXa=0，则X0为最优解；若e^TXa不等于0，则原线性规划无解。

    3. 人工变量不可再进基。

    4. 下题用大M法就比直接使用单纯形方法简单：

       1. m i x : 2 x 1 + 3 x 2 + x 3 s . t . : x 1 + 4 x 2 + 2 x 3 ≥ 8 3 x 1 + 2 x 2 ≥ 6 x i ≥ 0 , i = 1 , 2 , 3
          mix:2x1+3x2+x3s.t.:x1+4x2+2x3≥83x1+2x2≥6xi≥0,i=1,2,3" role="presentation">mix:s.t.:2x1+3x2+x3x1+4x2+2x3≥83x1+2x2≥6xi≥0,i=1,2,3$$\begin{array}{rl}mix:& 2x_1+3x_2+x_3\\ s.t.:& x_1+4x_2+2x_3\ge 8\\ & 3x_1+2x_2\ge 6\\ & x_i\ge 0,i=1,2,3\end{array}$$
          mix:s.t.:​2x1​+3x2​+x3​x1​+4x2​+2x3​≥83x1​+2x2​≥6xi​≥0,i=1,2,3​

22. 修正单纯形算法：只需要计算一次B^-1，之后可通过E_kl矩阵快速计算下一个B^-1。

23. 对偶线性规划问题：

    1. 生产甲、乙两种商品，需要用到ABC三种机器，各自耗时如下，每天最多使用时长如约束列所示。希望最大化利润：max 100x_jia+150x_yi。

    原规划P	甲	乙	约束
    A	5	2	50
    B	7	9	30
    C	8	6	80
    利润	100	150

    m a x : 100 x 1 + 150 x 2 s . t . : 5 x 1 + 2 x 2 ≤ 50 7 x 1 + 9 x 2 ≤ 30 8 x 1 + 6 x 2 ≤ 80 x i ≥ 0 , i = 1 , 2

    max:100x1+150x2s.t.:5x1+2x2≤507x1+9x2≤308x1+6x2≤80xi≥0,i=1,2" role="presentation">max:s.t.:100x1+150x25x1+2x2≤507x1+9x2≤308x1+6x2≤80xi≥0,i=1,2$$\begin{array}{rl}max:& 100x_1+150x_2\\ s.t.:& 5x_1+2x_2\le 50\\ & 7x_1+9x_2\le 30\\ & 8x_1+6x_2\le 80\\ & x_i\ge 0,i=1,2\end{array}$$
    max:s.t.:​100x1​+150x2​5x1​+2x2​≤507x1​+9x2​≤308x1​+6x2​≤80xi​≥0,i=1,2​

    2. 该公司出租ABC三套设备，A可以租50个小时，B可以租30个小时，C可以租80个小时，设计ABC三套设备的每小时租金，现在制定保底方案，至少要求不能比自己生成甲乙赚利润少。同时别人租走设备，不知道用来做什么，假设不小于自家生产甲乙产生的利润（因为你不知道别人租走设备究竟能产生多少价值，那么只能假设不会小于为100、150，不然别人为啥会来租你的设备）。

       	A	B	C	利润约束
       甲	5	7	8	100
       乙	2	9	6	150
       使用时长约束	50	30	80

       m i n : 50 y 1 + 30 y 2 + 80 y 3 s . t . : 5 y 1 + 7 y 2 + 8 y 3 ≥ 100 2 y 1 + 9 y 2 + 6 y 3 ≥ 150 y i ≥ 0 , i = 1 , 2 , 3

       min:50y1+30y2+80y3s.t.:5y1+7y2+8y3≥1002y1+9y2+6y3≥150yi≥0,i=1,2,3" role="presentation">min:s.t.:50y1+30y2+80y35y1+7y2+8y3≥1002y1+9y2+6y3≥150yi≥0,i=1,2,3$$\begin{array}{rl}min:& 50y_1+30y_2+80y_3\\ s.t.:& 5y_1+7y_2+8y_3\ge 100\\ & 2y_1+9y_2+6y_3\ge 150\\ & y_i\ge 0,i=1,2,3\end{array}$$
       min:s.t.:​50y1​+30y2​+80y3​5y1​+7y2​+8y3​≥1002y1​+9y2​+6y3​≥150yi​≥0,i=1,2,3​

24. 对偶规则

    原规划（对偶规划）（P）	对偶规划（原规划）（D）
    min	max
    目标中系数	约束条件右端项
    约束条件右端项	目标中系数
    约束条件≥	变量≥
    约束条件≤	变量≤
    约束条件=	变量无约束
    变量≥	约束条件≤
    变量≤	约束条件≥
    变量无约束	约束条件=

    原规划（对偶规划）（P）	对偶规划（原规划）（D）
    max	min
    目标中系数	约束条件右端项
    约束条件右端项	目标中系数
    约束条件≥	变量≤
    约束条件≤	变量≥
    约束条件=	变量无约束
    变量≥	约束条件≥
    变量≤	约束条件≤
    变量无约束	约束条件=

25. 对偶定理：

    1. §(D)有无界解，对应的对偶规划无可行解。

    2. §与对偶(D)都有最优解的充要条件是它们都有可行解；§和(D)中有一个有最优解，另一个必有最优解，且二者最优值相等。

    3. §的最优解为X*，对应的最优基为B，则(D)的最优解为W0:

    4. $$C_B^T{B}^{-1}=W_0^T$$

    5. 设X是（P）的任一基本解，X对应于基B，W=$(C_B^T{B}^{-1}{)}^T$，若又与W分别是（P）与（D）的可行解，则X与W分别是（P）与（D）的最优解。

    6. X的判别数全部非正，等价于W=$(C_B^T{B}^{-1}{)}^T$是(D)的可行解。

26. 对偶单纯形方法：

    1. 单纯形方法的思想是，保持b>=0，来调节判别数，最后判别数全部小于等于0的时候得到最优解。

    2. 对偶单纯形方法的思想是，保持判别数全部小于等于0（这样的点称为正则解，对应的基称为正则基），来调节b，最后b全部大于等于0的时候得到最优解。

    3. 从以上分析来看，转轴操作的时候，选择bk<0的行，主元为akl，要求 min ⁡ { σ j a k j ∣ a k j < 0 } \min\{\frac{\sigma_j}{akj}|akj<0\} min{akjσj​​∣akj<0}

    4. 比如下题，使用对偶单纯形方法就比较简便：

       1. m i x : 2 x 1 + 3 x 2 + x 3 s . t . : x 1 + 4 x 2 + 2 x 3 ≥ 8 3 x 1 + 2 x 2 ≥ 6 x i ≥ 0 , i = 1 , 2 , 3

          mix:2x1+3x2+x3s.t.:x1+4x2+2x3≥83x1+2x2≥6xi≥0,i=1,2,3" role="presentation">mix:s.t.:2x1+3x2+x3x1+4x2+2x3≥83x1+2x2≥6xi≥0,i=1,2,3$$\begin{array}{rl}mix:& 2x_1+3x_2+x_3\\ s.t.:& x_1+4x_2+2x_3\ge 8\\ & 3x_1+2x_2\ge 6\\ & x_i\ge 0,i=1,2,3\end{array}$$
          mix:s.t.:​2x1​+3x2​+x3​x1​+4x2​+2x3​≥83x1​+2x2​≥6xi​≥0,i=1,2,3​

       2. 由于改写成标准形式时，需要减去剩余变量，因此无直接的单位矩阵，因此就将增广矩阵取反，即存在现成的单位矩阵，此时b为[-8,-6]^T，sigma全为负，调节b即可。