An active set method for bound-constrained optimization

Abstract

In this article, a class of algorithms is developed for bound-constrained optimization. The new scheme uses the gradient-free line search along bent search paths. Unlike traditional algorithms for bound-constrained optimization, our algorithm ensures that the reduced gradient becomes arbitrarily small. It is also proved that all strongly active variables are found and fixed after finitely many iterations. A Matlab implementation of a bound-constrained solver LMBOPT based on the new theory was discussed by the present authors in a companion paper (Math. Program. Comput. 14 (2022), 271–318).

Keywords:

• Bound-constrained optimization
• active set strategy
• line search method
• global convergence

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

The LMBOPT software is available at [32].

Notes

1 In practice, one may allow a smaller domain of definition if f satisfies the coercivity condition that, as x approaches the boundary of the domain of definition, $f\left(x\right)$ exceeds the function value $f\left(x^0\right)$ at a known starting point $x^0$. Also, Lipschitz continuity may be relaxed to local Lipschitz continuity if all evaluation points remain in a bounded region.

2 In fact, the solvers LMBFG-EIG-MS, LMBFG-DDOGL, LMBFG-BWX-MS, LMBFG-EIG-curve-inf, LMBFG-EIG-MS-2-2, CGdescent, LMBFG-EIG-inf-2, LMBFGS-TR, LMBFG-MTBT, LMBFG-MT are unconstrained optimization solvers. In order to provide a comprehensive numerical report, we turned them into bound-constrained solvers. For each solver, this modification was done by combining the bent search path (35(35) $x\left(\alpha \right):=\pi [x+\mathrm{\alpha q}],$(35) ) with the corresponding line search strategy.

Additional information

Funding

The third author acknowledges financial support of the Austrian Science Foundation under Project No. P 34317.

Notes on contributors

A. Neumaier

A. Neumaier is a professor emeritus, a mathematician and physicist at the University of Vienna, holding from 1994 to 2022 the chair for computational mathematics at the Faculty of Mathematics. His research interests include global optimization, structure-driven methods for large-scale optimization, quadratic programming, gradient-free optimization, nonlinear parameter estimation, software development, numerical analysis, uncertainty modelling in high dimensions, restricted maximum likelihood, nonlinear parameter estimation, classification and density estimation.

B. Azmi

B. Azmi received an M.Sc. degree in mathematics from the University of Vienna, Vienna, Austria, in 2012, and the Ph.D. degree in mathematics from the University of Graz, Graz, Austria, in 2017. He was a member of the International Research Research Training Group (IGDK 1754) ‘Optimization and Numerical Analysis for Partial Differential Equations with Nonsmooth Structures’, University of Graz. From 2017 to 2021, he worked as a postdoctoral researcher with the Johann Radon Institute for Computational and Applied Mathematics (RICAM), Austrian Academy of Sciences, Vienna. He is currently an assistant professor in numerical optimization with the University of Konstanz, Konstanz, Germany. His research interests include the development of algorithms for partial-differential-equation-constrained optimization problems, stabilization of infinite-dimensional systems and data-driven methods for solving controlled systems.

M. Kimiaei

M. Kimiaei received a B.Sc. degree in pure mathematics from Bu-Ali Sina University, Hamedan, Iran, in 2006 and an M.Sc. degree in applied mathematics (optimization) from Razi University, Kermanshah, Iran, in 2008. From 2017 to 2021, he was a student at Vienna Graduate School on Computational Optimization (VGSCO) at the University of Vienna, Austria, and completed a Ph.D. degree in computational optimization. He has been a postdoctoral researcher at the University of Vienna since 2021. His research interests include nonlinear programming, derivative-free optimization, mixed-integer programming, nonsmooth optimization, nonlinear leasts-quares optimization, sparse optimization, monotone equations and software development.