Active set expansion strategies in MPRGP algorithm

0534448 - ÚGN 2021 RIV NL eng J - Journal Article
Kružík, Jakub - Horák, David - Čermák, Martin - Pospíšil, L. - Pecha, Marek
Active set expansion strategies in MPRGP algorithm.
Advances in Engineering Software. Roč. 149, November 2020 (2020), č. článku 102895. ISSN 0965-9978. E-ISSN 1873-5339
R&D Projects: GA MŠMT LQ1602; GA ČR(CZ) GA19-11441S; GA MŠMT ED1.1.00/02.0070
Institutional support: RVO:68145535
Keywords : MPRGP * active set * expansion step * quadratic programming * PERMON
OECD category: Applied mathematics
Impact factor: 4.141, year: 2020
Method of publishing: Limited access
https://www.sciencedirect.com/science/article/pii/S0965997819311627?via%3Dihub

The paper investigates strategies for expansion of active set that can be employed by the MPRGP algorithm. The standard MPRGP expansion uses a projected line search in the free gradient direction with a fixed step length. Such a scheme is often too slow to identify the active set, requiring a large number of expansions. We propose to use adaptive step lengths based on the current gradient, which guarantees the decrease of the unconstrained cost function with different gradient-based search directions. Moreover, we also propose expanding the active set by projecting the optimal step for the unconstrained minimization. Numerical experiments demonstrate the benefits (up to 78% decrease in the number of Hessian multiplications) of our expansion step modifications on two benchmarks – contact problem of linear elasticity solved by TFETI and machine learning problems of SVM type, both implemented in PERMON toolbox.
Permanent Link: http://hdl.handle.net/11104/0312651