数值最优化-有效集法求解含有不等式约束的二次规划问题

夏威夷大核桃

已于 2023-02-03 19:18:00 修改

阅读量2.1k

点赞数 1

分类专栏：数值最优化文章标签：人工智能

于 2023-02-03 19:07:04 首次发布

本文链接： https://blog.csdn.net/weixin_51991224/article/details/128770479

版权

数值最优化专栏收录该内容

7 篇文章 0 订阅

订阅专栏

参考链接：(78条消息) 有效集法介绍（Active Set Method）_dymodi的博客-CSDN博客_有效集法

唯一参考书：数值最优化（numerical optimization）

不等式约束的二次规划问题的最一般表述如下所示：

并给出KKT条件（一阶必要条件）的一种表述：

我们还可以给出KKT条件的另一种表述：

其实也就是在 KKT的证明中：我们从这两个等式（12.51和12.52）推导出的KKT条件：

将第二种KKT表述应用在QP问题上，可以得出相应的结果为：

这里对函数求导的地方手算一下就明白了。

下面引入很重要的一条定理：满足KKT条件的解 $x^*$ 在G为半正定的情况下就是全局最优解：

接下来就是介绍对于凸QP问题的primal有效集方法，先给出算法的全部框架，这里引用了来自 dymodi博客的有效集方法算法流程图：这里的流程图存在一个问题是：右下角的判断框 $\alpha =0 ?$ 应该改成： $\alpha =1 ?$ ，修改的原因自己可以斟酌斟酌。

我们对流程图进行高度的概括，将这个流程图分为上下左右来理解：分别是：

上：判断p；
下：计算p；
左：删除约束；
右：迭代与增加约束；

算法收敛性：（这里来自 dymodi博客的最后一段）书中的定理16.6给出了算法的收敛性，即：只要每次沿着 $p_k$ 前进，那么目标函数值沿这个方向是一定会减少的，因此（博客中还说因此：“算法的迭代可以在有限次数内终止”，我觉得这个结论不太充分，但是先这么认为）算法的收敛应与怎么增加和删除约束无关。因而上面流程图的左右两侧的什么时候增加、删除约束只是一种策略，用来帮助我们实现算法的快速收敛。因此，在阅读下面算法的具体细节时，只要时刻牢记算法收敛性的主干条件（沿着 $p_k$ ，函数减小），就会帮助我们理解很多遇到的小问题。

算法背景：每次迭代时引入迭代点 $x_k$ 和工作集 $W_k$ ，代表第k次迭代中的坐标点和当前考虑的有效集。注意此时的迭代点 $x_k$ 一定是在工作集 $W_k$ 下的可行点，即满足KKT条件16.37b。

第一步：判断 $x_k$ 是否为 $q(x)$ 在工作集 $W_k$ 下的最优解。

第二步：如果不是，则求出一个 $q(x)$ 在工作集 $W_k$ 下的最优解 $x$ ：

这时，如果令 $\vec{p} = \vec{x} - \vec{x_k}$ 就会有：

$q(x) = q(x_k+p) = 1/2 p^TGp+g_k^Tp+\rho_k,\quad \rho_k = 1/2x_k^TGx_k+c^Tx_k$

并且满足约束条件：

$a_i^Tp=a_i^T(x-x_k) = a_i^Tx-a_i^Tx_k = b_i-b_i = 0$

由于 $\rho_k$ 的大小与 $p$ 无关，因此求关于 $x$ 的最优化问题，等价为求 $p$ 的最优化问题：

因此，第二步其实是求出这个 $p_k$ 。

第三步：这里我们假设等式约束的优化问题的解 $p_k$ 已经求出，并且 $p_k$ 不是零向量:

我们可以发现， $a_i^T(x_k+\alpha p_k) = a_i^T x_k = b_i$ ，也就是说对任何 $\alpha$ ， $x_k+\alpha p_k$ 总可以满足约束16.39b。并且，我们希望这个迭代可以正常进行下去：

对于 $W_k$ 内的有效约束，等式16.40一定会被满足，但是对于 $i\notin W_k$ 的约束(有效或者not有效约束都有可能)，则不一定成立。因此为使全部约束被满足，则需要：

$a_i^T(x_k+\alpha _kp_k)\geq a_i^Tx_k\geq b_i$

化简后为：

书中提到：为了最大化降低 $q(x)$ ,我们希望的到满足全部上述条件的最大的 $\alpha_K$ ：

但是为什么 $\alpha_k$ 越大，就能更大化的降低目标函数，暂时还不确定。一种可能的想法是：从向量的角度来说， $\alpha_k$ 越大， $x_k+\alpha_k p_k$ 的新迭代点距离原来的迭代点 $x_k$ 越远，因此貌似可以更快地收敛。但只要沿着 $p_k$ ，目标函数就会减小，我们暂且把这个取最大的 $\alpha_k$ 也当作一种策略。

当选出 $\alpha_k$ 后，根据 $\alpha_k$ 值的不同，对应着不同的物理意义和操作：

首先，从 $\alpha_k$ 的定义式就可以看出，它是非负的。
如果 $\alpha_k = 1$ ，我们理解为这次迭代没有受到约束；
如果 $\alpha_k<1$ ，这意味着这次迭代的 $p_k$ 被当前工作集 $W_k$ 之外的约束 $i$ 阻挡，因此我们将这个约束添加进来，构成新的工作集；
如果 $\alpha_k=0$ ，（从定义式可以看出）这时的 $\alpha_k$ 的定义式的分子为零，那么此时的情况是，在原来的迭代点 $x_k$ 上， $b_i-a_i^Tx_k = 0$ 所对应的约束 $i$ 是工作集 $W_k$ 之外的迭代点 $x_k$ 的有效约束。因此，我们也要将这个约束添加进来。

第四步，（和第三步相反）直到我们找到了某个 $x_k$ 是当前工作集下的最优解，也就是这时解出的 $p_k$ 为零，有下面的等式成立：

接下来，我们检查工作集中所有的 $j\in W_k \cap I$ 的约束所对应的 $\lambda _j$ ，如果全部非负，那么根据上面提到的定理16.4，此时的 $x_k$ 就是全局最优解。

但如果存在负的 $\lambda_j$ ，则在工作集里去掉这个约束。

继续迭代，直到结束。

夏威夷大核桃

关注关注

1
点赞
踩
4

收藏

觉得还不错? 一键收藏
0
评论
数值最优化-有效集法求解含有不等式约束的二次规划问题

前进，那么目标函数值沿这个方向是一定会减少的，因此（博客中还说因此：“算法的迭代可以在有限次数内终止”，我觉得这个结论不太充分，但是先这么认为）算法的收敛应与怎么增加和删除约束无关。因而上面流程图的左右两侧的什么时候增加、删除约束只是一种策略，用来帮助我们实现算法的快速收敛。一种可能的想法是：从向量的角度来说，的最后一段）书中的定理16.6给出了算法的收敛性，即：只要每次沿着。，如果全部非负，那么根据上面提到的定理16.4，此时的。的定义式的分子为零，那么此时的情况是，在原来的迭代点。
复制链接

扫一扫