Global inexact quasi-Newton method for nonlinear system of equations with constraints. (English) Zbl 1434.65073
A new method to solve nonlinear systems of equations with nonnegative constraints is introduced. This method is an interior point method and is based, whenever possible, on inexact quasi-Newton directions to generate a new iteration. If a quasi-Newton direction is rejected or the new iteration is generated outside the feasibility region, that direction is projected onto the positive octant of \(\mathbb{R}^n\).
The Projected Inexact Quasi-Newton Method (PIQN) method is a derivative-free method in the sense that it is not necessary to know the Jacobian matrix of the function that defines the system of equations to perform the linear search. It is proved that the method has good convergence properties and that, under some reasonable assumptions, the method has a superlinear convergence. Experiments using PIQN algorithm are presented.
The Projected Inexact Quasi-Newton Method (PIQN) method is a derivative-free method in the sense that it is not necessary to know the Jacobian matrix of the function that defines the system of equations to perform the linear search. It is proved that the method has good convergence properties and that, under some reasonable assumptions, the method has a superlinear convergence. Experiments using PIQN algorithm are presented.
Reviewer: Anton Iliev (Plovdiv)
MSC:
| 65H10 | Numerical computation of solutions to systems of equations |
| 65K05 | Numerical mathematical programming methods |
| 90C25 | Convex programming |
| 90C53 | Methods of quasi-Newton type |
| 90C56 | Derivative-free methods and methods using generalized derivatives |
Keywords:
inexact quasi-Newton method; nonlinear system of equations; nonnegative constraints; global method; complementarity problemsReferences:
| [1] | Andreani, R.; Júdice, J. J.; Martínez, J. M.; Patricio, J., On the natural merit function for solving complementarity problems, Math. Program., 130, 211-223 (2011) · Zbl 1236.90127 |
| [2] | Andreani, R.; Júdice, J. J.; Martínez, J. M.; Patricio, J., A projected-gradient interior-point algorithm for complementarity problems, Numer. Algorithms, 57, 457-485 (2011) · Zbl 1229.65097 |
| [3] | Andreani, R.; Júdice, J. J.; Martínez, J. M.; Martini, T., Feasibility problems with complementarity constraints, Eur. J. Oper. Res., 249, 41-54 (2016) · Zbl 1346.90762 |
| [4] | Arenas, F. E.; Martínez, H. J.; Pérez, R., Least change secant update methods for nonlinear complementarity problem, Ing. Cienc., 11, 11-36 (2015) |
| [5] | Arias, C. A.; Martínez, J. M., Fast convergence of an inexact interior-point method for horizontal complementarity problems, Numer. Algorithms, 79, 1187-1210 (2018) · Zbl 06986854 |
| [6] | Arias, C. A.; Martínez, H. J.; Pérez, R., A global quasi-Newton algorithm for nonlinear complementarity problem, Pac. J. Optim., 13, 1-15 (2017) · Zbl 1474.90434 |
| [7] | Broyden, C. G., A class of methods for solving nonlinear simultaneous equations, Math. Comput., 19, 92, 577-593 (1965) · Zbl 0131.13905 |
| [8] | Broyden, C. G.; Dennis, J. E.; Moré, J. J., On the Local and Superlinear Convergence of Quasi-Newton Methods, PB 211 923 (1972), Department of Computer Science, Cornell University |
| [9] | Chandrasekhar, S., Radiative Transfer (1960) · Zbl 0037.43201 |
| [10] | Costa, A.; Martins, J.; Figueiredo, I.; Júdice, J., The directional instability problem in systems with frictional contacts, Comput. Methods Appl. Mech. Eng., 193, 1, 357-384 (2004) · Zbl 1075.74596 |
| [11] | Dennis, J. E.; Moré, J. J., A characterization of superlinear convergence and its applications to quasi-Newton methods, Math. Comput., 28, 549-560 (1974) · Zbl 0282.65042 |
| [12] | Dennis, J.; Schnabel, R., Numerical Methods for Unconstrained Optimization and Nonlinear Equations (1996), Society for Industrial and Applied Mathematics · Zbl 0847.65038 |
| [13] | Dirkse, S.; Ferris, M., The path solver: a nommonotone stabilization scheme for mixed complementarity problems, Optim. Methods Softw., 5, 2, 123-156 (1995) |
| [14] | Facchinei, F.; Pang, J. S., Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer Ser. Oper. Res. Financ. Eng. (2003) · Zbl 1062.90002 |
| [15] | Ferris, M. C.; Pang, J. S., Engineering and economic applications of complementarity problems, SIAM Rev., 39, 669-713 (1997) · Zbl 0891.90158 |
| [16] | Iusem, A.; Júdice, J.; Sessa, V.; Sarabando, P., Splitting methods for the eigenvalue complementarity problem, Optim. Methods Softw., 0, 1-29 (2018) |
| [17] | Júdice, J.; Sherali, H.; Ribeiro, I., The eigenvalue complementarity problem, Comput. Optim. Appl., 37, 1, 139-156 (2007) · Zbl 1181.90261 |
| [18] | Júdice, J.; Sherali, H.; Ribeiro, I., Complementarity active-set algorithm for mathematical programming problems with equilibrium constraints, J. Optim. Theory Appl., 134, 3, 467-481 (2007) · Zbl 1145.90075 |
| [19] | Júdice, J.; Raydan, M.; Rosa, S.; Santos, S., On the solution of the symmetric eigenvalue complementarity problem by the spectral projected gradient algorithm, Numer. Algorithms, 47, 4, 391-407 (2008) · Zbl 1144.65042 |
| [20] | Kanzow, C.; Yamashita, N.; Fukushima, M., Levenberg-Marquardt methods for constrained nonlinear equations with strong local convergence properties, J. Comput. Appl. Math., 172, 375-397 (2004) · Zbl 1064.65037 |
| [21] | Kelly, T., Iterative Methods for Linear and Nonlinear Equations (1995), Society for Industrial and Applied Mathematics · Zbl 0832.65046 |
| [22] | Kostreva, M., Elasto-hydrodynamic lubrication: a non-linear complementarity problem, Int. J. Numer. Methods Fluids, 4, 377-397 (1984) · Zbl 0551.76007 |
| [23] | Li, D.; Fukushima, M., A derivative-free line search and global convergence of Broyden-like method for nonlinear equations, Optim. Methods Softw., 13, 181-201 (2000) · Zbl 0960.65076 |
| [24] | Marini, L.; Morini, B.; Porcelli, M., Quasi-Newton methods for convex constrained nonlinear systems and their application, Optimization-Online (2017), in press |
| [25] | Meintjes, K.; Morgan, A., Chemical equilibrium system as numerical test problems, ACM Trans. Math. Softw., 16, 143-151 (1990) · Zbl 0900.65153 |
| [26] | Morini, B.; Porcelli, M.; Toint, P. L., Approximate norm descent methods for constrained nonlinear systems, Math. Comput., 87, 1327-1351 (2018) · Zbl 1383.65051 |
| [27] | Mounnir, H.; Patrick, M., Smoothing methods for nonlinear complementarity problems, J. Optim. Theory Appl., 160, 711-729 (2014) · Zbl 1396.90085 |
| [28] | Querioz, M.; Júdice, J.; Humes, J., The symmetric eigenvalue complementarity problem, Math. Comput., 73, 1, 1849-1863 (2003) · Zbl 1119.90059 |
| [29] | Wardrop, J. G., Some theoretical aspects of road traffic research, Proc., Inst. Civ. Eng., 4, 325-378 (1952) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
