网站建设技术工具,常州注册公司,湖南网站建设公司排行榜,深圳网页技术开发公司本系列文章主要是我在学习《数值优化》过程中的一些笔记和相关思考#xff0c;主要的学习资料是深蓝学院的课程《机器人中的数值优化》和高立编著的《数值最优化方法》等#xff0c;本系列文章篇数较多#xff0c;不定期更新#xff0c;上半部分介绍无约束优化#xff0c;… 本系列文章主要是我在学习《数值优化》过程中的一些笔记和相关思考主要的学习资料是深蓝学院的课程《机器人中的数值优化》和高立编著的《数值最优化方法》等本系列文章篇数较多不定期更新上半部分介绍无约束优化下半部分介绍带约束的优化中间会穿插一些路径规划方面的应用实例 二十、低维度严格凸的QP二次规划 1、低维度严格凸的QP二次规划数学描述 低维度严格凸二次规划其数学描述如下式所示其中 M Q M_Q MQ是严格正定的对称矩阵,目标函数是严格凸函数维度n是低维的 min x ∈ R n 1 2 x T M Q x c Q T x , s.t. A Q x ≤ b Q \operatorname*{min}_{x\in\mathbb{R}^{n}}\frac{1}{2}x^{\mathrm{T}}M_{\mathcal{Q}}xc_{\mathcal{Q}}^{\mathrm{T}}x\text{, s.t. }A_{\mathcal{Q}}x\leq b_{\mathcal{Q}} x∈Rnmin21xTMQxcQTx, s.t. AQx≤bQ M Q M_Q MQ是严格正定的因此可以对其进行Cholesky分解Cholesky 分解是把一个对称正定的矩阵表示成一个下三角矩阵L和其转置的乘积的分解。它要求矩阵的所有特征值必须大于零故分解的下三角的对角元也是大于零的。 M Q L Q L Q T M_{\cal Q}L_{\cal Q}L_{\cal Q}^{\mathrm{T}} MQLQLQT 这个QP问题等价于关于y的最小二范数问题 y L Q T x L Q − 1 c Q o r x L Q − T y − ( L Q L Q T ) − 1 c Q yL_{\cal Q}^{\mathrm T}xL_{\cal Q}^{-1}c_{\cal Q}\quad\mathrm{or}\quad xL_{\cal Q}^{-\mathrm T}y-\left(L_{\cal Q}L_{\cal Q}^{\mathrm T}\right)^{-1}c_{\cal Q} yLQTxLQ−1cQorxLQ−Ty−(LQLQT)−1cQ 我们可以把上面x关于y的表达式代入到目标函数中整理后得到等价的表达式如下所示 min y ∈ R n 1 2 y T y , s . t . E y ≤ f \min_{y\in\mathbb{R}^n}\frac12y^\mathrm{T}y,\mathrm{~s.t.~}Ey\leq f y∈Rnmin21yTy, s.t. Ey≤f 其中 E A Q L Q − T , f A Q ( L Q L Q T ) − 1 c Q b Q EA_{\mathcal{Q}}L_{\mathcal{Q}}^{-\mathrm{T}},fA_{\mathcal{Q}}\big(L_{\mathcal{Q}}L_{\mathcal{Q}}^{\mathrm{T}}\big)^{-1}c_{\mathcal{Q}}b_{\mathcal{Q}} EAQLQ−T,fAQ(LQLQT)−1cQbQ 对上述表达式求解得到最优的y后在多面体中找一个范数最小的点也即离原点最近的点再将得到的y代入到上面x关于y的表达式即可得到最优的x。 线性不等式约束 E y ≤ f Ey\leq f Ey≤f构成了如下图所示的可行域在该可行域内找一个使得下式最小的解即y的二范数的平方的最小的解也就是可行域中离原点最近的点。 min y ∈ R n 1 2 y T y 1 2 ∣ ∣ y ∣ ∣ 2 2 \min_{y\in\mathbb{R}^n}\frac12y^\mathrm{T}y\frac12{||y||_2}^2 y∈Rnmin21yTy21∣∣y∣∣22 2、一维的QP二次规划 与之前介绍的LP线性规划类似一维情况下的数学描述及可行域的计算如下图所示所不同的是确定了可行域后QP更容易得到最优解只需要找到可行域中距离原点最近的点即可若原点位于可行域左侧则可行域左端点即为最优解同理若原点位于可行域右侧则可行域右端点即为最优解若原点位于可行域内部则原点即为最优解。 3、二维的QP二次规划 与之前介绍的LP线性规划类似二维情况下的解决思路依然是在加入新的约束后若之前的最优解依然在可行域中则最优解不变若之前的最优解已经不在可行域中了则需要将之前的约束边界投影到当前新加入的约束边界上转化得到一维的可行域再在这个一维的可行域上寻找新的最优解与LP不同的是得到一维的可行域后只需要将原点也投影到新加入的约束边界上然后找到一维可行域中与原点的投影点距离最近的点即可 4、更一般的d维QP二次规划 与前文介绍的d维的LP线性规划的主要思想类似d维的二次规划在当前最优解不满足新加入的约束时也将其转换成d-1维的二次规划这跟上面2维二次规划时转换成1维二次规划的思想是相同的这种思想有点像递归的思想。 上图中给出的伪代码中输入参数H即不等式约束 a T y b a^\mathrm{T}yb aTyb,也即一系列半空间如果此时H的维度是一维的则直接采用上文中介绍的一维情况的解决方法求解若此时c不是一维的则初始化一个空集 I I I可以提前用Fisher-Yates算法对H的序列进行打乱打乱后进行for循环时每次依次从H中取一个h然后判断 情况1若当前最优解属于h则当前最优解满足约束h不需要计算新的最优解直接将h添加到集合 I I I中继续进行下一轮for循环处理下一个约束h 情况2若当前的最优解不属于h则需要计算一个新的最优解x将已经加入到集合 I I I中的约束投影到约束h的边界上得到低一个维度的H’将原点也投影到h上得到低一个维度的原点vM是h的一个正交基然后将低一个维度的H’作为参数递归调用LowDimMinNorm()函数本身进行降维处理直至降为1维情况。然后就可以得到新的y’运用关系式 y ← M y ′ v y\leftarrow My^{\prime}v y←My′v得到新的最优解y此时约束h已经满足将其添加到集合 I I I中本轮循环结束继续进行下一轮for循环处理下一个约束h。 for循环结束后即可得到满足所有约束hi的最优解y然后再带入到x关于y的表达式得到满足所有约束的最优解x。 在前文介绍的LP线性规划中把d维的问题转换成d-1维的问题并逐步转换为1维问题是通过高斯消元法完成的接下来介绍在QP二次规划中如何把高维问题转换成低维问题。 在上图中的例子中之前的约束构成的空间如绿色区域所示新加入的约束h如图中灰色区域所示新的最优解 y ∗ y^* y∗必然位于约束h所确定的平面上且位于之前的约束构成的区域的内部原点o在约束h所确定的平面上的投影点为v由勾股定理可得他们满足以下表达式 ∥ y ∗ − o ∥ 2 ∥ y ∗ − v ∥ 2 ∥ v − o ∥ 2 \|y^*-o\|^2 \|y^*-v\|^2\|v-o\|^2 ∥y∗−o∥2∥y∗−v∥2∥v−o∥2 假设我们已知约束h所确定的平面中以v为原点的一组标准正交基M然后约束h所确定的灰色平面中所有点均可表示为该组标准正交基的坐标因此 y ∗ y^* y∗满足如下表达式其中 y 1 ′ y_1^{\prime} y1′和 y 2 ′ y_2^{\prime} y2′是 y ∗ − v y^*-v y∗−v在标准正交基下的坐标 y ∗ − v y 1 ′ M 1 y 2 ′ M 2 M y ′ y^*-vy_1^{\prime}M_1y_2^{\prime}M_2My^{\prime} y∗−vy1′M1y2′M2My′ 将上式代入到 ∥ y ∗ − o ∥ 2 ∥ y ∗ − v ∥ 2 ∥ v − o ∥ 2 \|y^*-o\|^2 \|y^*-v\|^2\|v-o\|^2 ∥y∗−o∥2∥y∗−v∥2∥v−o∥2中可得以下表达式因为M是标准正交基所以 M T M I M^TMI MTMI所以求范数后可以约去 ∥ M y ′ ∥ 2 ∥ v − o ∥ 2 ∥ y ′ ∥ 2 ∥ v − o ∥ 2 ∥ y ∗ ∥ 2 \|My\|^2\|v-o\|^2\|y\|^2\|v-o\|^2\|y^*\|^2 ∥My′∥2∥v−o∥2∥y′∥2∥v−o∥2∥y∗∥2 因为v-o是常量所以求最小的y*可以转换为求最小的y’把一个线性等式约束上的最小范数问题转化为一个无约束的最小范数问题。 接下来看一下上面提到的点v和标准正交基M如何求约束h g T y f g^Tyf gTyf,可知当 y f g g T g y\frac{\color{red}{fg}}{\color{red}{g^Tg}} ygTgfg必然满足该约束所以v可取为 v f g g T g v\frac{\color{red}{fg}}{\color{red}{g^Tg}} vgTgfg g是h约束所确定平面的法向量那么平面的标准正交基均垂直于g我们可以先构造下图中绿色的这样一组正交基其某一个维度的模长为||g||然后再通过旋转把模长为||g||的那个基变得跟g同方向其他的绿色基自然也就变成了我们想要的图中黄色的基M。其相关数学表达式如下所示 u g − ∥ g ∥ e i ug-\|g\|e_i ug−∥g∥ei H I d − 2 u u T u T u HI_d-\frac{2uu^\mathrm{T}}{u^\mathrm{T}u} HId−uTu2uuT 先根据g和ei计算出u再代入上式计算出H注意这里的H不是约束的意思然后把H转置一下得到 H T H^T HT后去掉第i列就得到我们想要的M了M中的d-1个列向量是由H中的d-1个行向量构成的 参考资料 1、数值最优化方法高立 编著 2、机器人中的数值优化
