State-defect constraint pairing graph coarsening method for Karush–Kuhn–Tucker matrices arising in orthogonal collocation methods for optimal control
State-defect constraint pairing graph coarsening method for Karush–Kuhn–Tucker matrices arising in orthogonal collocation methods for optimal control
复制标题
最优控制正交配置方法中Karush-Kuhn-Tucker矩阵的状态-缺陷约束配对图粗化方法
DOI：
10.1007/s10589-015-9821-x
复制
发表时间：
2016
影响因子：
2.2
通讯作者：
Davis, Timothy A.
中科院分区：
文献类型：
--
作者：
Cannataro, Begüm Şenses;Rao, Anil V.;Davis, Timothy A.
为了提高大型稀疏Karush-Kuhn-Tucker矩阵的数值分解效率，利用Legendre-Gauss-Radau正交配置法对最优控制问题进行离散化，提出了一种状态-缺陷约束对图粗化方法。该方法利用了Karush-Kuhn-Tucker矩阵的特殊稀疏结构，这种稀疏结构源于正交配置法。状态-缺陷约束配对图粗化方法将状态的每个分量与其对应的缺陷约束配对，并强制成对的行在重新排序的Karush-Kuhn-Tucker矩阵中相邻。使用各种基准最优控制问题给出了聚合状态-缺陷约束配对的结果，发现所提出的状态-缺陷约束配对图粗化方法显著减少了延迟枢轴的数量和浮点运算的数量，并通过在单位时间内执行更多的浮点运算来提高计算效率。结果表明，当最优控制问题包含状态和控制相等路径约束时，状态-缺陷约束配对图粗化方法对由Legendre-Gauss-Radau配置产生的Karush-Kuhn-Tucker矩阵不太有效，因为这类矩阵可能具有同时对应于缺陷和路径约束的延迟枢轴。然后使用采用最大匹配的交替图粗化方法来尝试进一步减少延迟的枢轴的数量。然而，研究发现，这种交替图粗化方法并不比状态-缺陷约束配对图粗化方法提供更多的优势。
A state-defect constraint pairing graph coarsening method is described for improving computational efficiency during the numerical factorization of large sparse Karush–Kuhn–Tucker matrices that arise from the discretization of optimal control problems via an Legendre–Gauss–Radau orthogonal collocation method. The method takes advantage of the particular sparse structure of the Karush–Kuhn–Tucker matrix that arises from the orthogonal collocation method. The state-defect constraint pairing graph coarsening method pairs each component of the state with its corresponding defect constraint and forces paired rows to be adjacent in the reordered Karush–Kuhn–Tucker matrix. Aggregate state-defect constraint pairing results are presented using a wide variety of benchmark optimal control problems where it is found that the proposed state-defect constraint pairing graph coarsening method significantly reduces both the number of delayed pivots and the number of floating point operations and increases the computational efficiency by performing more floating point operations per unit time. It is then shown that the state-defect constraint pairing graph coarsening method is less effective on Karush–Kuhn–Tucker matrices arising from Legendre–Gauss–Radau collocation when the optimal control problem contains state and control equality path constraints because such matrices may have delayed pivots that correspond to both defect and path constraints. An alternate graph coarsening method that employs maximal matching is then used to attempt to further reduce the number of delayed pivots. It is found, however, that this alternate graph coarsening method provides no further advantage over the state-defect constraint pairing graph coarsening method.
物理优化方法的图收缩：并行计算机上映射数据的质量成本权衡
影响因子：
2.9
作者：
N. Mansour;R. Ponnusamy;A. Choudhary;G. Fox
通讯作者：
G. Fox