机器人中的数值优化|【一】数值优化基础

数值优化基础

凸集 Convex Sets

凸集的定义

令X是线性空间。如果对于X的子集S中的所有x和y，并且在区间 [0,1]中的所有t，点 $(1-t)x+ty$也属于S，则S称为凸集。
不失一般性，对于所有的凸集，其线性组合点都位于凸集内部：
$$\begin{gathered} \sum {\theta }_i{x}_i\in X \\ \sum {\theta }_i=1,{\theta }_i\ge 0,\forall {\theta }_i \end{gathered}$$

凸集的性质

• 任意凸集之交为凸集。
• X的子空间为凸集。若S为凸集，则对X中任何x，x+S亦为凸集。
• 如果除了端点之外的连接x和y的线段上的每个点都在C的内部，则C是严格凸起的。
• 凸集相加为凸集
  A + B = { x + y ∣ x ∈ A , y ∈ B } A+B=\{x+y \mid x \in A, y \in B\} A+B={x+y∣x∈A,y∈B}
• 凸集相乘为凸集
  A × B = { x × y ∣ x ∈ A , y ∈ B } A \times B=\{x \times y \mid x \in A, y \in B\} A×B={x×y∣x∈A,y∈B}
• 凸集相交不为凸集

High-Order Info of Functions

Functions $f(x)=f\left(x_1,x_2,x_3\right)$

Gradient ∇ f ( x ) = ( ∂ 1 f ( x ) ∂ 2 f ( x ) ∂ 3 f ( x ) ) \nabla f(x)=\left(\begin{array}{l}\partial_1 f(x) \\ \partial_2 f(x) \\ \partial_3 f(x)\end{array}\right) ∇f(x)= ​∂1​f(x)∂2​f(x)∂3​f(x)​ ​

Hessian ∇ 2 f ( x ) = ( ∂ 1 2 f ( x ) ∂ 1 ∂ 2 f ( x ) ∂ 1 ∂ 3 f ( x ) ∂ 2 ∂ 1 f ( x ) ∂ 2 2 f ( x ) ∂ 2 ∂ 3 f ( x ) ∂ 3 ∂ 1 f ( x ) ∂ 3 ∂ 2 f ( x ) ∂ 3 2 f ( x ) ) \nabla^2 f(x)=\left(\begin{array}{ccc}\partial_1^2 f(x) & \partial_1 \partial_2 f(x) & \partial_1 \partial_3 f(x) \\ \partial_2 \partial_1 f(x) & \partial_2^2 f(x) & \partial_2 \partial_3 f(x) \\ \partial_3 \partial_1 f(x) & \partial_3 \partial_2 f(x) & \partial_3^2 f(x)\end{array}\right) ∇2f(x)= ​∂12​f(x)∂2​∂1​f(x)∂3​∂1​f(x)​∂1​∂2​f(x)∂22​f(x)∂3​∂2​f(x)​∂1​∂3​f(x)∂2​∂3​f(x)∂32​f(x)​ ​

在0点处的近似：泰勒展开
$$f(x)=f(0)+x^T\nabla f(0)+\frac{1}{2}{x}^T{\nabla }^{2}f(0)x+O\left({\Vert x-x_0\Vert }^3\right)$$
现在拓展概念，设将$f(x)$为维度从n维到m维的映射，即$f(x):{\mathbb{R}}^n\to {\mathbb{R}}^m$，则有Jacobian矩阵

矩阵和向量微分规则与表格

一些有用的性质

$$\begin{gathered} dA=0 \\ d(\alpha X)=\alpha (dX) \\ d(AXB)=A(dX)B \\ d(X+Y)=dX+dY \\ d(X^T)=(dX{)}^T \\ d(XY)=(dX)Y+X(dY) \\ d<X,Y>=<dX,Y>+<X,dY> \\ d(\frac{X}{\varphi })=\frac{\varphi dX-(d\varphi )X}{{\varphi }^2} \\ dtrX=I \\ df(g(x))=\frac{f}{g}\dot{d}g(x) \end{gathered}$$
规则可以参考wikipedia网站MATRIX CALCULUS

凸函数的性质 Convex Functions

Jensen不等式

凸函数满足Jensen不等式，如下所示
$$f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)$$

一阶条件 First-order conditions

$$f(y)\ge f(x)+\nabla f(x{)}^T(y-x)$$
当$\nabla f(x{)}^T=0$时，有$f(y)\ge f(x)$

二阶条件 Second-order conditions

一个光滑函数为凸函数，当且仅当
$${\nabla }^{2}f(x)⪰0,\forall x$$
即函数的二阶导数半正定
对于非凸函数，局部最小值满足
$${\nabla }^{2}f(x^{\ast })⪰0,$$

强凸性 strong convexity

$$f(y)\ge f(x)+(y-x{)}^T\nabla f(x)+\frac{m}{2}\Vert y-x{\Vert }^2$$
式中前两部分对所有凸函数适用，第三部分也就是最后一部分为min curvature
当$f(x)$有Hessian阵时，有
$$\begin{array}{rl}f(y)& \approx f(x)+(y-x{)}^T\nabla f(x)+\frac{1}{2}(y-x{)}^T{\nabla }^{2}f(x)(y-x)\\ & \ge f(x)+(y-x{)}^T\nabla f(x)+\frac{{\lambda }_{\min }}{2}\Vert y-x{\Vert }^2\end{array}$$
则有
$${\nabla }^{2}f(x)⪰mI$$

Lipchitz常数

Lipchitz常数满足
$$\Vert \nabla f(x)-\nabla f(y)\Vert \le M\Vert y-x\Vert$$
由近似展开可以得到
$$f(y)\le f(x)+(y-x{)}^T\nabla f(x)+\frac{M}{2}\Vert y-x{\Vert }^2$$
有
$$f(y)-f\left(x^{\star }\right)\ge \frac{m}{2}{\Vert y-x^{\star }\Vert }^2$$
$$f(y)-f\left(x^{\star }\right)\le \frac{M}{2}{\Vert y-x^{\star }\Vert }^2$$

条件数 condition number

对于任何函数，有$\kappa =\frac{majoraxis}{minoraxis}$
对于光滑函数，有$\kappa \approx cond({\nabla }^{2}f(x))$
对于可微函数，有$\kappa =M/m$

Sub-differential

对于不光滑的函数，其导数在一点左右不相等，我们称之为sub differential

记为$\partial f(x)=\left\{g:f(y)>f(x)+(y-x{)}^{T}g,\forall y\right\}$

sub-differential的方向不唯一，但是最速下降的方向是负sub-diff中模长最小的方向

单调性Monotonicity

无约束非凸函数优化

$$\begin{gathered} \min f(x) \\ x=(x_1,...,x_n)\in {\mathbb{R}}^n:optimizationvariables \\ f:{\mathbb{R}}^n\to \mathbb{R}:objectivefunction \end{gathered}$$

线性搜索最速梯度下降 Line-Search Steepest Gradient Descent

最速梯度下降的迭代形式如下所示
$$x^{k+1}=x^k-\tau \nabla f\left(x^k\right)$$
其中$\tau$为步长。
选择步长的方法有多种，如下所示

• 1.常数 constant step size
  $$\tau =c$$
• 2.随着时间减小 diminishing step size
  $$\tau =c/k$$
• 3.精确线性搜索 exact line search
  $$\tau =\arg \underset{\alpha }{\min }f(x^k+\alpha d)$$
• 4.非精确线性搜索 inexact line search
  $$\tau \in \left\{\alpha \mid f\left(x^k\right)-f\left(x^k+\alpha d\right)\ge -c\cdot \alpha d^{\mathrm{T}}\nabla f\left(x^k\right)\right\}$$
  其中方法1过于代办，方法2需要满足robbins-monro规则，对于一些很复杂计算很昂贵的函数来说是适合用的，方法3不具备可行性，方法4需要满足Armijo条件，较为容易满足。

Backtracking/Armijo line search

1. 选择搜索方向：$d=-\nabla f\left(x^k\right)$
2. 当$f\left(x^k+\tau d\right)>f\left(x^k\right)+c\cdot \tau d^T\nabla f\left(x^k\right)$时，重复$\tau \leftarrow \tau /2$
3. 迭代$x^{k+1}=x^k+\tau d$

重复直至梯度很小或者sub-diff包含0时。

Backtracking的缺点

当条件数很大，或者函数很差的时候，可能会反复震荡。如下图所示，当我们在优化一个非常扁的椭圆形函数的时候，就会出现这样在椭圆上往复震荡的情况，因此我们发现，很有必要了解到函数的曲率，将其纳入考虑范围。

改进牛顿法 Modified Damped Newton’s Method

牛顿法

根据泰勒二阶展开，有
$$f(x)\approx \hat{f}(x)=f(x_k)+\nabla f(x_k{)}^T(x-x_k)+\frac{1}{2}(x-x_k{)}^T{\nabla }^{2}f(x_k)(x-x_k)$$
最小化二阶近似
$$\nabla \hat{f}(x)={\nabla }^{2}f(x_k)(x-x_k)+\nabla f(x_k)=0$$
得到给定${\nabla }^{2}f(x_k)\succ 0$时，有
$$x=x_k-[{\nabla }^{2}f(x_k){]}^{-1}\nabla f(x_k)$$
牛顿步骤为
$$x_{k+1}=x_k-[{\nabla }^{2}f(x_k){]}^{-1}\nabla f(x_k)$$
其优化过程如下图所示

牛顿法缺点

Hessian阵可能是奇异的，且不稳定的，这样的话我们无法对Hessian阵进行求逆运算。

可行牛顿法

首先初始化$x$, $x\leftarrow x_0\in {\mathbb{R}}^n$
当$||\nabla f(x)||>\delta$时，进行如下计算
$do$：
$d\leftarrow -M^{-1}\nabla f(x)$
$t\leftarrow backtrackionglinesearch$
$x\leftarrow x+td$
$endwhile$
$return$
其中，M是一个接近Hessian阵的正定矩阵，以此来替代线性搜索中的求梯度和求Hessian阵。
如果函数为凸函数，则有
$$\mathbf{M}={\nabla }^{2}f(\mathbf{x})+ϵ\mathbf{I},ϵ=\min \left(1,\Vert \nabla f(\mathbf{x}){\Vert }_{\infty }\right)/10$$
因为M是正定的，因此可以使用Cholesky factorization
$$\mathbf{M}\mathbf{d}=-\nabla f(\mathbf{x}),\mathbf{M}=\mathbf{L}{\mathbf{L}}^{\mathrm{T}}$$
如果函数是非凸的，那么我们通过如下计算M
Bunch-Kaufman Factorization:
$$\mathbf{M}\mathbf{d}=-\nabla f(\mathbf{x}),\mathbf{M}=\mathbf{L}\mathbf{B}{\mathbf{L}}^{\mathrm{T}}$$

补充性质

埃尔米特矩阵 Hermitian matrix

埃尔米特矩阵（英语：Hermitian matrix，又译作厄米特矩阵，厄米矩阵），也称自伴随矩阵，是共轭对称的方阵。埃尔米特矩阵中每一个第i行第j列的元素都与第j行第i列的元素的复共轭。
对于
A = { a i , j } ∈ C n × n A=\left\{a_{i, j}\right\} \in C^{n \times n} A={ai,j​}∈Cn×n
有
$$a_{i,j}=\overline{a_{j,i}}$$
记作
$$A=A^H$$

埃尔米特矩阵的性质

• 若A和B是埃尔米特矩阵，那么它们的和A+B也是埃尔米特矩阵；而只有在A和B满足交换性（即AB = BA）时，它们的积才是埃尔米特矩阵。
• 可逆的埃尔米特矩阵A的逆矩阵A-1仍然是埃尔米特矩阵。 如果A是埃尔米特矩阵，对于正整数n，An是埃尔米特矩阵。
• 方阵$C$与其共轭转置的和$C+(C^{\ast })$是埃尔米特矩阵，
• 方阵$C$与其共轭转置的差$C-C^{\ast }$是斜埃尔米特矩阵。
• 任意方阵$C$都可以用一个埃尔米特矩阵$A$与一个斜埃尔米特矩阵$B$的和表示：
  $$C=A+B\text{ with }A=\frac{1}{2}\left(C+C^{\ast }\right)\text{ and }B=\frac{1}{2}\left(C-C^{\ast }\right)$$
• 埃尔米特矩阵是正规矩阵，因此埃尔米特矩阵可被酉对角化，而且得到的对角阵的元素都是实数。这意味着埃尔米特矩阵的特征值都是实的，而且不同的特征值所对应的特征向量相互正交，因此可以在这些特征向量中找出一组Cn的正交基。
• n-阶埃尔米特矩阵的元素构成维数为$n^2$的实向量空间，因为主对角线上的元素有一个自由度，而主对角线之上的元素有两个自由度。
• 如果埃尔米特矩阵的特征值都是正数，那么这个矩阵是正定矩阵，若它们是非负的，则这个矩阵是半正定矩阵。
  具体参考wikipedia埃尔米特矩阵

LU分解

定义

对于方阵$A$，$A$的 $LU$ 分解是将它分解成一个下三角矩阵$L$ 与上三角矩阵$U$的乘积，也就是
$$A=LU$$

PLU分解

方阵 A 的 PLU 分解是是将它分解成一个置换矩阵 P、一个下三角矩阵 L 与上三角矩阵 U 的乘积，即
$$A=PLU$$

LDU分解

方阵 A 的 LDU 分解是是将它分解成一个单位下三角矩阵 L、对角矩阵 D 与单位上三角矩阵 U 的乘积，即
$$A=LDU$$
更多细节参考wikipediaLU分解

Cholesky分解

如果矩阵A是埃尔米特矩阵，并且是正定矩阵，那么可以使，U是L的共轭转置。也就是说，A可以写成

$$A=L{L}^{\ast }$$
这个分解被称作Cholesky分解。对每一个正定矩阵，Cholesky分解都唯一存在。此外，比起一般的LU分解，计算Cholesky分解更为快捷，并具有更高的数值稳定性。
更多细节参考wikipediaCholesky分解文章来源地址https://www.toymoban.com/news/detail-698081.html

到了这里，关于机器人中的数值优化|【一】数值优化基础的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！