Subspace Methods for Nonlinear Optimization (CSIAM Transactions on Applied Mathematics, 2021)
Subspace techniques such as Krylov subspace methods have been wellknown and extensively used in numerical linear algebra. They are also ubiquitous andbecoming indispensable tools in nonlinear optimization due to their ability to handle large scale problems. There are generally two types of principals: i) the decisionvariable is updated in a lower dimensional subspace; ii) the objective function or constraints are approximated in a certain smaller subspace of their domain. The key ingredients are the constructions of suitable subspaces and subproblems according to thespecific structures of the variables and functions such that either the exact or inexactsolutions of subproblems are readily available and the corresponding computationalcost is significantly reduced. A few relevant techniques include but not limited to direct combinations, block coordinate descent, active sets, limited-memory, Andersonacceleration, subspace correction, sampling and sketching. This paper gives a comprehensive survey on the subspace methods and their recipes in unconstrained andconstrained optimization, nonlinear least squares problem, sparse and low rank optimization, linear and nonlinear eigenvalue computation, semidefinite programming,stochastic optimization and etc. In order to provide helpful guidelines, we emphasize on high level concepts for the development and implementation of practical algorithms from the subspace framework.