优化理论——二次规划

日期：2024-05-06 05:08 / 作者：佚名

二次规划(QP, Quadratic Programming)定义：目标函数为二次函数，约束条件为线性约束，属于最简单的一种非线性规划。

一个标准的等式约束QP模型如下

$\\begin{aligned}min &\\; \\frac{1}{2}x^THx + g^Tx\\\\ s.t. & \\;a^T_ix=b_i,\\;i=1, 2,...,m \\end{aligned}$

其中 $H$ 是由二阶导构成的Hessian矩阵，这里的向量都是指列向量， $g^T$ 表示转置成行向量。

其对应的Lagrange函数为

$\\begin{aligned}L(x,\\lambda)=\\frac{1}{2}x^THx + g^Tx +\\sum_{i=1}^m\\lambda_i(a^T_i x - b_i) \\end{aligned}$

满足KKT条件，即满足

$\\begin{equation}\\left\\{ \\begin{array}{lr}\\frac{\\partial L}{\\partial x}=Hx + g +\\sum_{i=1}^m\\lambda _ia_i=0\\\\ \\frac{\\partial L}{\\partial \\lambda_i}=a^T_ix -b_i=0 , \\;i=1,2,...,m \\end{array}\\right. \\end{equation}$

将其写成矩阵形式

$\\begin{equation}\ onumber F(x, \\lambda)=\\left[ \\begin{matrix}Hx + g +\\lambda a \\\\ a^Tx-b \\end{matrix}\\right]\\end{equation}=0$

其中

这是一个纯线性方程组，易于求解，KKT方程组的解 $(x^*, \\lambda^*)$ ，即为优化模型的解

一个标准的等式不等式联合约束QP原模型如下

$\\begin{aligned}min &\\; \\frac{1}{2}x^THx + g^Tx\\\\ s.t. & \\;a^T_ix=b_i, i \\in E\\\\ &h^T_jx \\leq t_j,j\\in I\\\\ \\end{aligned}$

$i \\in E$ 表示的是 $m$ 个等式约束集合， $i \\in I$ 表示的是 $n$ 个不等式约束集合。对于不等式约束下的QP问题此处介绍两种求解方案

模型的拉格朗日函数为

$L(x, \\lambda, \\mu)=\\frac{1}{2}x^THx + g^Tx + \\sum_{i=1}^m\\lambda _i(a^T_ix - b_i) + \\sum_{j=1}^n\\mu_j(h^T_jx - t_i)$

内点法在之前的系列中我们已经详细介绍，以原始对偶内点法为例，加入微小量 $\ au$ 扰动后KKT条件为

$\\begin{cases}Hx + g + \\sum_{i=1}^m\\lambda _ia_i+ \\sum_{j=1}^n\\mu_jh_j=0\\\\ a^T_ix=b_i,\\; i=1,...,m\\\\ h^T_jx \\leq t_j\\\\ \\mu_j(h_jx - t_j)=-\ au_j\\\\ \\mu_j \\geq 0 , \\;j=1,...,n \\end{cases}$

为了更快的检查解是否在约束空间内，我们在不等式方程组引入了松弛变量 $s_j$ 则 $s_j=t_j - h_jx$ ，因为判断 $s_j\\geq 0$ 要比判断 $h_jx\\leq t_j$ 方便的多，上式成为

$\\begin{cases}Hx + g + \\sum_{i=1}^m\\lambda _ia_i+ \\sum_{j=1}^n\\mu_jh_j=0\\\\ a^T_ix=b_i,\\; i=1,...,m\\\\ h^T_jx + s_j=t_j\\\\ \\mu_js_j=\ au\\\\ \\mu_j, s_j \\geq 0 , \\;j=1,...,n \\end{cases}$

将其写成矩阵形式

$\\begin{equation}\ onumber F(x,s, \\lambda, \\mu)=\\left[ \\begin{matrix}Hx + g +\\lambda a+ \\mu h \\\\ h^Tx + s -t \\\\ a^Tx-b \\\\ \\mu s - \ au1 \\end{matrix}\\right]\\end{equation}=0$

其中

$\\begin{equation}\ onumber \\lambda=\\left[ \\begin{matrix}\\lambda_1&0&...&0\\\\0&\\lambda_2&...&0\\\\\\vdots&\\vdots&...&\\vdots\\\\0&0&...&\\lambda_m\\end{matrix}\\right]\\end{equation}$ ， $\\begin{equation}\ onumber a^T=\\left[ \\begin{matrix}a^T_1\\\\ a^T_2\\\\\\vdots\\\\a^T_m\\end{matrix}\\right]\\end{equation}$ ， $\\begin{equation}\ onumber b=\\left[ \\begin{matrix}b_1\\\\ b_2\\\\\\vdots\\\\b_m\\end{matrix}\\right]\\end{equation}$ $\\begin{equation}\ onumber u=\\left[ \\begin{matrix}u_1&0&...&0\\\\0&u_2&...&0\\\\\\vdots&\\vdots&...&\\vdots\\\\0&0&...&u_n\\end{matrix}\\right]\\end{equation}$ $\\begin{equation}\ onumber h^T=\\left[ \\begin{matrix}h^T_1\\\\ h^T_2\\\\\\vdots\\\\h^T_n\\end{matrix}\\right]\\end{equation}$ $\\begin{equation}\ onumber t=\\left[ \\begin{matrix}t_1\\\\ t_2\\\\\\vdots\\\ _n\\end{matrix}\\right]\\end{equation}$ $\\begin{equation}\ onumber s=\\left[ \\begin{matrix}s_1\\\\ s_2\\\\\\vdots\\\\s_n\\end{matrix}\\right]\\end{equation}$

牛顿法解方程组

$F(x_{k},s_k, \\lambda_{k}, \\mu_{k}) + F'(x_{k},s_k, \\lambda_{k}, \\mu_{k})(\\Delta x_k, \\Delta s_k, \\Delta \\lambda_k, \\Delta \\mu_k)=0$

即

$\\begin{equation}\ onumber \\left[ \\begin{matrix}H&0&a^T&h^T\\\\h^T&I&0&0\\\\a^T&0&0&0\\\\0&u_k&0&s^T_k\\end{matrix}\\right]\\left[ \\begin{matrix}\\Delta x_k\\\\\\Delta s_k\\\\\\Delta \\lambda_k\\\\\\Delta \\mu_k\\end{matrix}\\right]=-\\left[ \\begin{matrix}Hx_k + g +\\lambda_k a+ \\mu_k h \\\\ h^Tx_k + s_k -t \\\\ a^Tx_k-b \\\\ \\mu_k s_k - \ au_k1 \\end{matrix}\\right]\\end{equation}$

得到 $(\\Delta x_k, \\Delta s_k, \\Delta \\lambda_k, \\Delta \\mu_k)$ 然后更新变量

$(x_{k+1}, s_{k+1}, \\lambda_{k+1}, \\mu_{k+1})=(x_{k}, s_k, \\lambda_{k}, \\mu_{k}) +\\alpha (\\Delta x_k, \\Delta s_k,\\Delta \\lambda_k, \\Delta \\mu_k)$

同时更新 $\ au_{k+1}=- \\sigma\\sum_{j=1}^n\\mu_{j, k}s_{j,k}$ ， $σ∈[0,1]$ 进入 $k+1$ 次迭代直到方程组的解，并且满足 $\ au_k \\leq \\epsilon$

积极集法属于图形法在QP问题上的扩展，其通过求解有限个等式约束QP问题来解决一般约束下的QP模型。当不等式约束条件不多时，也是一种高效的求解QP算法。

积极集法首先将QP中所有的不等式约束视为等式约束。把不等式约束直接转成等式约束当然是存在问题的，不等式约束存在有效和无效两种情况，而有效无效很容易通过该不等式对应的拉格朗日乘子进行判断。不等式约束的互补松弛条件告诉我们，不等式对应的拉格朗日乘子应当满足 $\\lambda_i \\geq 0$ 。

在第 $k$ 次迭代开始时，我们首先检查当前的迭代点 $x_k$ 是否为当前工作集 $W_k$ （有效不等式约束集合）下的最优点。如果不是，我们就通过求解一个等式约束的 QP 命题来得到一个前进方向 $p$ 。在计算 $p$ 的时候，只关注 $W_k$ 中的不等式约束并将其转化为等式约束，而忽略其他不等式约束。令： $d=x - x_k$ ，代入原命题得

$\\begin{aligned}min &\\; \\frac{1}{2}(d+x_k)^TH(d+x_k) + g^T(d+x_k) \\\\ s.t. & \\;a_i^T(d+x_k)=0, i \\in W_k \\end{aligned}$

上式展开后，令 $g_k=Hx_k+g，\\rho_k=\\frac{1}{2}x_k^THx_k + x_k^Tg$ （常数），在第 $k$ 次迭代需要求解的 QP 子命题为

$\\begin{aligned}min &\\; \\frac{1}{2}d^THd + g_k^Td\\\\ s.t. & \\;a_i^Td=0, i \\in W_k \\end{aligned}$

更新： $x_{k+1}=x_k+\\beta_kd_k$

添加有效约束：

迭代需要满足 $a_i^T(x_k+\\beta_kd_k)\\leq b_i$ ，因此步长 $\\beta_k$ 为

$\\begin{aligned}\\beta_k=min\\{1, min_{i\ otin W_k, a_i^Td_k>0}\\frac{b_i-a_i^Tx_k}{a_i^Td_k}\\}\\end{aligned}$

$\\beta_k=1$ ：满足所有等式不等式约束，不需要更新工作集，进一步迭代； $\\beta_k=0$ ：在当前迭代点处有其他的有效约束没有被添加到工作集 $W_k$ 中； $\\beta_k<1$ ：也就是说下降方向 $p_k$ 被某条不在工作集 $W_k$ 内的约束阻拦住了，需要将这条约束添加到工作集来构造新的工作集 $W_{k+1}$ 。

删除无效约束：

计算拉格朗日乘子

$\\begin{cases}Hx^* + g=-\\sum_{i=1}^m a_i\\lambda_i\\\\ \\lambda_i(a^T_i x- b_i)=0\\\\ \\lambda_i \\geq 0, \\;{i \\in W} \\end{cases}$

通过上式计算出不等式约束对应的拉格朗日乘子，如果有一个或者多个 $\\lambda_i$ 的值小于0。那么就表明通过去掉工作集的某一条或几条约束，目标函数值可以进一步下降。因此我们会从对应的 $\\lambda_i$ 值小于 0 的约束中选择一条，将其从工作集 $W_{k}$ 中剔除从而构造出新的工作集 $W_{k+1}$ 。如果有多于一条的可选约束，那么不同的剔除方法会遵循不同原则，默认去除对应 $\\lambda_i$ 值最小的那条约束。