Enumeration-based approach to solving parametric linear complementarity problems
Enumeration-based approach to solving parametric linear complementarity problems
复制标题
基于枚举的方法来解决参数线性互补问题
DOI：
10.1016/j.automatica.2015.09.019
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
M. Morari
中科院分区：
文献类型：
--
作者：
M. Herceg;C. Jones;M. Kvasnica;M. Morari
本文提出了一种求解参数线性互补问题的方法，该方法依赖于一种枚举技术来发现所有的可行基。枚举过程是基于评估活动约束的所有可能组合和可行性测试。虽然已知枚举方法在约束的数量上呈指数增长，但PLCP的制定允许将廉价的秩检验并入以快速修剪探索中的不可行方向。基于枚举的PLCP求解器的发展的动机是，它代表了一种直接的方法来解决参数线性和二次优化问题，以及它们的混合整数对应。这些类型的问题经常出现在线性和混合系统的模型预测控制领域。基于枚举的PLCP求解器提供了另一种在混合模型预测控制领域计算显式解的方法，在某些重要情况下可以非常有效。
This paper presents a solution method for parametric linear complementarity problems (PLCP) that relies on an enumeration technique to discover all feasible bases. The enumeration procedure is based on evaluating all possible combinations of active constraints and testing for feasibility. Although the enumeration approach is known to grow exponentially in the number of constraints, the formulation of the PLCP allows incorporation of cheap rank tests to quickly prune the infeasible directions in the exploration. The motivation for the development of the enumeration based PLCP solver is that it represents a direct method to solve parametric linear and quadratic optimization problems as well as their mixed-integer counterparts. These types of problems often arise in the field of model predictive control for linear and hybrid systems. The enumeration based PLCP solver offers another alternative to compute explicit solutions in the field of hybrid model predictive control that can be extremely effective in some important cases.