Apollo进阶课程[5]——Optimization Inside Motion Planning

约束问题的核心：

• 目标函数的定义，目标函数比较清晰，对于后面的求解更有帮助。
• 约束，比如路网约束、交规、动态约束等。
• 约束问题的优化，比如动态规划、二次规划等。

动态规划是在从动力系统中出来，通过类似于有限元的方式，把问题从连续空间抽象成离散空间，然后在离散空间中通过aggregating的方式将重复计算进行简化。这种方法可以逼近连续空间中的最优解，但是计算复杂度很高。
牛顿法：考虑斜率的变化率进行收敛，利用泰勒展开的二次项逼近函数 ，它的收敛次数是指数平方，也叫二次收敛。牛顿法要求 locally convex 才能保证收敛，也就是导数是严格单调递增的。

二次规划：本质脱离不了泰勒展开条件。但是它的求解过程涉及更复杂的情况。因为二次规划方法并不一定是处理一维问题，可能涉及更高阶求导。

分段解决问题，每段求一个最优解，然后将它们来比较。
启发式搜索：首先通过动态规划方式对整个问题有一个粗浅的认识，然后找到目前的最优解作为牛顿法的起点，通过二次规划进行细化。
二次规划问题：

求解方法：求高阶导数为0的点.

Lagrangian method：从更高的维度看问题。通过增加松弛变量的方式去掉约束条件，变成一个可以解决的问题。

不等式的约束条件求解方法：使用 active set method，最优解可能落到边界上，如果真的是边界最优，不等式约束就可以转化为等式约束问题求解。
二次规划问题的方法KKT：

对于求解非线性优化问题，通常就是用启发式方法来求解。先用动态规划给出一个粗略解，给出一个凸空间。然后用二次规划方法在凸空间里去寻找最优解。