论文标题
在整数最佳控制中产生的离散子问题的有效解决方案，总变化正则化
Efficient Solution of Discrete Subproblems Arising in Integer Optimal Control with Total Variation Regularization
论文作者
论文摘要
我们考虑一类Integer线性程序（IP），这些程序作为对控制问题的解决方案的信任区域子问题的离散化，其中控制输入是在一个维度域中的整数值函数在一个维度域中的数字值函数，并且在目标中差异为差异，并且可以将其差异为差异。 我们证明，求解所考虑的问题类的实例等于在分层有向的无环图上求解资源约束的最短路径问题（RCSPP）。这种结构发现产生了一种基于拓扑排序和相应的运行时间复杂性的算法解决方案方法，在基础控制问题的离散间隔数量上是二次的运行时间复杂性，这是问题实例大小的主要量词。我们还使用$ a^*$算法考虑RCSPP的解决方案。具体而言，对拉格朗日放松的分析为$ a^*$算法和预处理过程提供了一致的启发式功能，可以使用这些过程来加速RCSPP的$ a^*$算法，而不会丢失计算解决方案的最佳性。 我们通过在几个整数最佳控制问题上执行信任区域算法来生成IP实例。数值结果表明，加速的$ a^*$算法和拓扑排序的表现明显优于通用IP求解器。此外，加速的$ a^*$算法能够超过较大的问题实例的拓扑排序。
We consider a class of integer linear programs (IPs) that arise as discretizations of trust-region subproblems of a trust-region algorithm for the solution of control problems, where the control input is an integer-valued function on a one-dimensional domain and is regularized with a total variation term in the objective, which may be interpreted as a penalization of switching costs between different control modes. We prove that solving an instance of the considered problem class is equivalent to solving a resource constrained shortest path problem (RCSPP) on a layered directed acyclic graph. This structural finding yields an algorithmic solution approach based on topological sorting and corresponding run time complexities that are quadratic in the number of discretization intervals of the underlying control problem, the main quantifier for the size of a problem instance. We also consider the solution of the RCSPP with an $A^*$ algorithm. Specifically, the analysis of a Lagrangian relaxation yields a consistent heuristic function for the $A^*$ algorithm and a preprocessing procedure, which can be employed to accelerate the $A^*$ algorithm for the RCSPP without losing optimality of the computed solution. We generate IP instances by executing the trust-region algorithm on several integer optimal control problems. The numerical results show that the accelerated $A^*$ algorithm and topological sorting outperform a general purpose IP solver significantly. Moreover, the accelerated $A^*$ algorithm is able to outperform topological sorting for larger problem instances.
