Comparison of active-set and gradient projection-based algorithms for box-constrained quadratic programming
- PDF / 988,702 Bytes
- 10 Pages / 595.276 x 790.866 pts Page_size
- 1 Downloads / 206 Views
FOCUS
Comparison of active-set and gradient projection-based algorithms for box-constrained quadratic programming Serena Crisci1
· Jakub Kružík2,3 · Marek Pecha2,3 · David Horák2,3
© Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract This paper presents on four chosen benchmarks an experimental evidence of efficiency of active-set-based algorithms and a gradient projection scheme exploiting Barzilai–Borwein-based steplength rule for box-constrained quadratic programming problems, which have theoretically proven rate of convergence. The crucial phase of active-set-based algorithms is the identification of the appropriate active set combining three types of steps—a classical minimization step, a step expanding the active set and a step reducing it. Presented algorithms employ various strategies using the components of the gradient for an update of this active set to be fast, reliable and avoiding undesirable oscillations of active set size. Keywords Quadratic programming · Active set · Gradient projection
1 Introduction
arg min f (x) s.t. l ≤ x ≤ u, x
The article compares MPRGP (Modified Proportioning with reduced gradient projections) (Dostál 2009) and GP (Gradient Projections) (Bertsekas 1999) combined with BoxVABBmin steplength rule (Crisci et al. 2019), which represent efficient algorithms for the solution of convex quadratic programming (QP) problems with box constraints, i.e. for minimizing quadratic functional subject to constraints
Communicated by Yaroslav D. Sergeyev.
B
Serena Crisci [email protected] Jakub Kružík [email protected] Marek Pecha [email protected] David Horák [email protected]
f (x) =
1 T x Ax − x T b 2 (1)
where f (x) is the cost function, A ∈ Rn×n is positive semidefinite Hessian, x is the solution, b is the right hand side, l and u are the lower and the upper bound, respectively. The comparison is carried out on several benchmarks. The first benchmark is a set of randomly generated QP problems with prescribed number of active constraints and spectral condition numbers. The next tested QP problems arise from machine learning problems for classification of two datasets which are solved by SVMs (support vector machines). A variant of the standard journal bearing problem from MINPACK-2 (Averick et al. 1991) test problem collection is the third benchmark. Finally, we compare the algorithms on a string displacement problem with a prescribed lower bound. The paper is divided as follows. Sections 2 and 3 describe the MPRGP and GP algorithms, respectively. The numerical experiments are presented in Sect. 4. Finally, we draw our conclusions in Sect. 5.
1
Department of Mathematics and Computer Science, University of Ferrara, Via Machiavelli 30, 44121 Ferrara, Italy
2
Institute of Geonics of the Czech Academy of Sciences, Studentska 1768, 708 00 Ostrava-Poruba, Czech Republic
2 The MPRGP algorithm
Department of Applied Mathematics, VSB - Technical University of Ostrava, FEECS, 17. listopadu 15/2172, 708 33 Ostrava-Poruba, Czech Republic
To describe t
Data Loading...
