Nonmonotone techniques for smooth optimization

The focus of this thesis is the study and the application of nonmonotone strategies. These techniques are basically introduced to improve numerical results of existing optimization algorithms. Their first aim is that of relaxing the monotone requirement imposed by the globalization techniques. In fact, these monotone conditions might slow down the convergence rate of inher- ently nonmonotone optimization methods. This relaxation must not harm global convergence results. In this thesis we apply nonmonotone strategies to both line search and trust-region globalization techniques. We first considered Generalized Nash Equilibrium Problems (GNEPs) and their KKT reformulation into a highly nonlinear constrained smooth system of equations. In order to obtain global and fast local convergence, we take into account an existing trust-region method that is locally superlinear under an error bound condition only. A nonmonotone strategy has been applied, showing that the resulting algo- rithm performs significantly better than the original one. Global conver- gence properties have been proved for the new algorithm, while superlinear convergence is directly inherited from the existing method. The resulting algorithm is competitive with a standard software for nonlinear equations, not only on GNEPs, but also on quasi-variational inequalities. The second contribution of this thesis is the development of a framework for nonmonotone line search based decomposition methods. This is the first time in which nonmonotonicity is combined with decomposition methods for general constrained problems. Note that the choice of the direction and the line search are not fixed in advance, in fact the framework proves conver- gence for all those combinations of directions and line searches that are able to satisfy some mild assumptions. A specific realization of this abstract algo- rithm has been implemented in two versions, monotone and nonmonotone. The two algorithms have been compared on a set of network equilibrium problems. Also on this application, the nonmonotone version outperformed its monotone counterpart both on the total number of iterations and the function evaluations. In the end, a new family of nonmonotone techniques is proposed to build algorithms that are able to control the amount of nonmonotonicity intro- duced in each of the phases of the optimization procedure. This tool might be very helpful to understand in which combination of methods, problems and phases is more important to apply a nonmonotone strategy.