Active set expansion strategies in MPRGP algorithm. (November 2020)

• Record Type: Journal Article
• Authors: Kružík, J.; Horák, D.; Čermák, M.; Pospíšil, L.; Pecha, M.
• Is Part Of: Advances in engineering software. Volume 149(2020)
• Publication Date: 2020-11
• Subjects: MPRGP -- Active set -- Expansion step -- Quadratic programming -- PERMON; Computer-aided engineering -- Periodicals; Engineering -- Computer programs -- Periodicals; Engineering -- Software -- Periodicals; Periodicals; 620.0028553
• DOI: 10.1016/j.advengsoft.2020.102895
• Languages: English
• ISSNs: 0965-9978

Abstract

Highlights: From 8 up to 78 pct decrease in the number of Hessian multiplication compared with standard expansion. Two new adaptive step lengths for expansion step with 5 different combination of vectors used for their computations and search directions. New alternative expansion strategy based on projected conjugate gradient step. Abstract: 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.