##
**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.

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

### MSC:

65H10 | Numerical computation of solutions to systems of equations |

65K05 | Numerical mathematical programming methods |