内点法

内点法

世界最新医学信息文摘-家长指引

2023年2月20日发(作者：河道清淤方案)

数值优化（NumericalOptimization）学习系列-序列⼆次规划和内点法（SQ。。

。

概述

对于⾮线性约束最优化问题，序列⼆次规划和内点法是两类⾮常重要的算法，也是⼤规模问题的利器。序列⼆次规划⽅法将原始问题

分解为⼀系列⼆次规划问题逐步求解；内点法将将约束添加到⽬标函数中转换为⼀系列⽆约束问题逐步求解。两类算法共同思想将原

始问题转换为可求解问题。

1.序列⼆次规划概述

2.内点法概述

3.总结

序列⼆次规划(SQP)概述

序列⼆次规划(SequentialQuadraticProgramming)对于⾮线性约束最优化问题是⼀个⾮常有效的算法，将原始问题划分为⼀系列⼆次规

划的⼦问题进⾏求解。

本节中介绍的SQP都属于激活集算法，有两种类型的激活-SQP算法，⼀是IQP，将原始问题转换为⼀系列不等式约束⼆次规划；⼆是

EQP，将原始问题转换为⼀系列等式约束⼆次规划问题。

⼤部分的SQP问题分为两个步骤进⾏求解，第⼀步通过局部⽅法寻找有效集；⼆是通过LineSearch或者TR进⾏最优化。

局部SQP⽅法

等式约束问题

问题描述如下

其主要思想是根据当前点寻找下⼀个优化点通过转换问题⼆次规划问题。

思路1，KKT条件

原始问题的拉格朗⽇⽅程为，根据KKT条件有

其中

对于等式⽅程问题可以采⽤⽜顿⽅程进⾏求解，迭代步骤如下

其中通过⽜顿KKT条件得到

注：推导过程简单，可以参考之前的章节。

思路2，根据当前点进⾏建模

对于当前点进⾏⼆次泰勒展开，转换为

展开⽅式为⽬标函数进⾏⼆次泰勒展开，约束进⾏⼀次泰勒展开。根据KKT也有

通过转换可以转换为上述求解步骤。

求解框架

不等式约束问题

对于不等式约束，同理可以进⾏泰勒展开。

IPQ和EPQ

：顾名思义将原始转换为⼀系列带有不等式约束的⼆次规划问题，该⽅法在实际中效果⾮常好，问题是对于⼀般的⼆次规划问题求

解复杂度较⾼，虽然可以将该次的最优解作为下⼀次⼦问题的初始解，仍然存在热启动问题。

：每次只考虑激活集，即等式约束。相对于IPQ每个⼦问题相对⽐较容易求解。

其他

最优化步骤中可以通过线搜索或者信赖域⽅法进⾏求解。

内点法

内点法和SQP⽅法类似对于求解⼤规模⾮线性约束⾮常有效。另外内点法(Interior-Point)和障碍⽅法（barriermethods）具有相同含

义。

两类转换思路

内点法可以求解的问题，可以转换为

连续⽅法（continuationmethods）

根据KKT条件，上述问题可以转换

类似于之前做法，可以通过不断改变参数来搜寻⼀条中⼼路径逐渐优化原始问题。

障碍⽅法（barriermethods）

问题可以转换为

其中参数是正数，控制搜索过程。通过KKT条件求解该问题，会发现和上述转换类似。

最原始的转换⽅式，直接转换为

该转换可能带来的问题是可能找不到最优解。

其他

1.内点法可以从对偶问题中获取关键思路

2.可以结合线搜索和信赖域⽅法进⾏求解

总结

通过本节学习可以了解序列⼆次规划和内点法求解⾮线性约束最优化问题的关键思路。