The use of linear programming for the solution of sparse sets of nonlinear equations. (English) Zbl 0636.65053

The authors propose a trust region algorithm using polyhedral norms for solving sparse sets of nonlinear equations. It is based on minimizing the \(l_ 1\)-norm of the linearized residual vector within an \(l_{\infty}\)- norm trust region. So they should solve at each iteration a linear programming problem only instead of minimizing a quadratic form over a Euclidean ball (a nonlinear programming problem), i.e. case of \(l_ 2\)- norm. This approach is motivated by the fact that linear programming techniques are easily applied.
Trust region methods based on norms other than \(l_ 2\)-norm have been proposed in other contexts. R. Fletcher [Math. Programming 2, 133- 165 (1972; Zbl 0249.90067)] developed an algorithm for the linearly constrained optimization problem where the trust region is defined in terms of the \(l_{\infty}\)-norm, and K. Madsen [J. Inst. Math. Appl. 16, 321-328 (1975; Zbl 0355.65038)] described an algorithm for the minimax problem that also uses the \(l_{\infty}\)-norm. However, in the context of solving sets of nonlinear equations the choice of norms in this paper yields a different algorithm from all of these. It seems that this algorithm is performant and robust for given numerical experiments with sparse structure.
Reviewer: Pham Dinh Tao


65H10 Numerical computation of solutions to systems of equations
65K05 Numerical mathematical programming methods


Full Text: DOI