Newton-type methods for nonsmooth equations with nonisolated solutions
Final Report Abstract
The project dealt with complementarity systems (CS), which arise from optimization and variational problems. By means of a nonsmooth complementarity function (C-function), such systems can be written as a nonsmooth system of equations. There is a growing interest in systems with solutions that are both nonisolated and degenerate. For smooth systems of equations, it is well known that Jacobian matrices are singular at nonisolated solutions. In addition, degeneracy (the violation of strong complementarity) in a solution implies that the system of equations is nondifferentiable there. Just a few years ago, it could be shown that fast convergence is possible for certain Newton-type methods in the vicinity of solutions that are both nonisolated and degenerate. This approach relies on a piecewise linear C-function and suitable error bound conditions. The main concern of the project was to figure out whether similar results are possible for certain other C-functions, in particular for the Fischer-Burmeister (FB) C-function. In the approach mentioned above (as well as for the classic Newton method), the length of a Newton step growth as the residual of the system of equations. The project succeeded in mitigating this restriction. To this end, structured CS with primal and dual variables (Karush Kuhn Tucker systems) were considered first. For the case when a degenerate solution is isolated with respect to the dual variables only, local superlinear convergence was shown using a novel Levenberg-Marquardt subproblem and an error bound condition. The generalization of this result to unstructured CS with degenerate and nonisolated solutions turned out to be difficult and more time consuming than expected. However, based on the reformulation of CS by the FB C-function and slightly stronger error bound conditions than those used in the approach mentioned above, an appropriate Levenberg-Marquardt method was shown to converge superlinearly with an R-order of at least 4/3. It is also possible to extend the results to C-functions in the Luo-Tseng class. The question for more far reaching generalizations (other C-functions, cone constrained CS) remains open.
Publications
- A special complementarity function revisited. Optimization 68 (2019), 65–79
Behling, R., Fischer, A., Schönefeld, K., Strasdat, N.
(See online at https://doi.org/10.1080/02331934.2018.1470177)
