二次规划_2_——起作用集方法

  这个算法很反人类，迭代过程相当复杂，最优化老师说：“明确地告诉你要考的。”
  起作用集方法适用于消元法和Lagrange方法无法处理的不等式约束二次规化问题。其主要思想是：以已知点为可行点，只考虑将该点的起作用约束，最小化 f ( x ) f(x) f(x)，得到新的可行点后重复以上做法。

一、起作用集法适用情形

  适用于具有不等式约束的二次规划问题 m i n     f ( x ) = 1 2 x T H x + c T x s . t .     A x ⩾ b min \ \ \ f(x)=\frac{1}{2}x^THx+c^Tx \\ s.t. \ \ \ Ax\geqslant b min   f(x)=21​xTHx+cTxs.t.   Ax⩾b

二、起作用集法求解步骤

  由于步骤太过繁琐，算法总是跳来跳去，所以在这里我只放上了我自己对于算法的分步与理解。算法可以分为一个初始+三个域，三个域分别为：解 δ \delta δ域、求 α ^ k \widehat\alpha_{k} α k​ 域、算L乘子 λ \lambda λ域。

（1）初始化：初始可行点 x ( 1 ) x^{(1)} x(1)，作用约束集 I ( 1 ) I^{(1)} I(1)，置 k = 1 k=1 k=1;
（2）解增量 δ \delta δ：这时构建增量求解问题： m i n     1 2 δ T H δ + ▽ f ( x ( k ) ) T δ s . t .     a i δ = 0 , i ∈ I ( k ) min \ \ \ \frac{1}{2}\delta^TH\delta+\triangledown f(x^{(k)})^T\delta \\ s.t. \ \ \ a^{i}\delta= 0, i \in I^{(k)} min   21​δTHδ+▽f(x(k))Tδs.t.   aiδ=0,i∈I(k)  得到最优解 δ ( k ) \delta^{(k)} δ(k)。此时进行第一次分流分析：

若 δ ( k ) = 0 \delta^{(k)}=0 δ(k)=0，则说明 x ( k ) x^{(k)} x(k)无法再继续变动，则跳到第4步计算L乘子，判断最优解；
若 δ ( k ) ≠ 0 \delta^{(k)}\neq 0 δ(k)​=0，需要对 x ( k ) x^{(k)} x(k)进行变动，则跳到第3步，求解步长。

（3）求步长 α ^ k \widehat\alpha_{k} α k​：
  上一步求解出了增量 δ \delta δ，这一步将增量视为移动方向 d d d，即 d ( k ) = δ ( k ) d^{(k)}=\delta^{(k)} d(k)=δ(k)。变动过程为： x ( k + 1 ) = x ( k ) + α ^ k d ( k ) x^{(k+1)}=x^{(k)}+\widehat\alpha_{k}d^{(k)} x(k+1)=x(k)+α k​d(k)  步长的选取首先要保证新点是一个可行点，不能违背 x ( k ) x^{(k)} x(k)的非作用下标集中约束，即： a i ( x ( k ) + α ^ k d ( k ) ) ⩾ b i     ,     i ∉ I ( k ) a^i(x^{(k)}+\widehat\alpha_{k}d^{(k)}) \geqslant b_i \ \ \ , \ \ \ i \notin I_{(k)} ai(x(k)+α k​d(k))⩾bi​   ,   i∈/​I(k)​  在特定情况下左侧孤立 α ^ k \widehat\alpha_{k} α k​： i f     a i d ( k ) < 0    :     α ^ k = b i − a i x ( k ) a i d ( k ) \mathbf{if} \ \ \ a^i d^{(k)}<0\ \ :\ \ \ \widehat\alpha_{k}=\frac{b_i-a^ix^{(k)}}{a^id^{(k)}} if   aid(k)<0  :   α k​=aid(k)bi​−aix(k)​  考察所有非作用约束集对应的约束式，可以求出多个 α ^ k \widehat\alpha_{k} α k​，进而对其求最小。同时还要注意，最终 α ^ k \widehat\alpha_{k} α k​的取值还要跟1进行比较： α k = m i n ( 1 , α ^ k ) \alpha_{k}=min{(1,\widehat\alpha_{k})} αk​=min(1,α k​)  得到步长，此时进行第二次分流分析：（这一步无论结果如何都要更新 x ( k ) x^{(k)} x(k)，只是一个回去，一个继续）

若 α k < 1 \alpha_{k}<1 αk​<1，原来非作用约束集中有一个约束式变为作用约束，小数步长直接更新 x ( k + 1 ) x^{(k+1)} x(k+1)（算法中唯一更新x的地方），返回步骤2，重新计算增量 δ \delta δ；
若 α k = 1 \alpha_{k}=1 αk​=1，此时的变动不会触动任何非作用约束，1步长直接更新 x ( k + 1 ) x^{(k+1)} x(k+1)（算法中唯一更新x的地方），跳到第4步计算L乘子，判断最优解。

（4）计算L乘子 λ \lambda λ：
  这一步是算法的出口，通过Lagrange方法最后给出的公式计算乘子 λ \lambda λ： λ = R g k = ( A H − 1 A T ) − 1 A H − 1 g k \lambda=Rg_k=(AH^{-1}A^T)^{-1}AH^{-1}g_k λ=Rgk​=(AH−1AT)−1AH−1gk​  其中 g k = ▽ f ( x ( k ) ) g_k=\triangledown f(x^{(k)}) gk​=▽f(x(k))，是当前迭代点的梯度。
得到每个作用约束对应的乘子之后，进行第三次分流分析：

若 λ < 0 \lambda<0 λ<0，挑选出最小的 λ \lambda λ，在起作用约束集 I I I中去掉下标，返回步骤2计算增量 δ \delta δ。
若 λ ⩾ 0 \lambda\geqslant0 λ⩾0，当前解 x ( k ) x_{(k)} x(k)​是最优解。

三、注

  这个方法思想简单，但是每一块的计算都很精密，过程很繁琐。考试的时候一定要把思路写清楚。