Assessing the reliability of general-purpose inexact restoration methods. (English) Zbl 1310.90088
Summary: Inexact Restoration methods have been proved to be effective to solve constrained optimization problems in which some structure of the feasible set induces a natural way of recovering feasibility from arbitrary infeasible points. Sometimes natural ways of dealing with minimization over tangent approximations of the feasible set are also employed. A recent paper [N. Banihashemi and C. Y. Kaya [J. Optim. Theory Appl. 156, No. 3, 726–760 (2013; Zbl 1263.49029)] suggests that the Inexact Restoration approach can be competitive with well-established nonlinear programming solvers when applied to certain control problems without any problem-oriented procedure for restoring feasibility. This result motivated us to revisit the idea of designing general-purpose Inexact Restoration methods, especially for large-scale problems. In this paper we introduce affordable algorithms of Inexact Restoration type for solving arbitrary nonlinear programming problems and we perform the first experiments that aim to assess their reliability. Initially, we define a purely local Inexact Restoration algorithm with quadratic convergence. Then, we modify the local algorithm in order to increase the chances of success of both the restoration and the optimization phase. This hybrid algorithm is intermediate between the local algorithm and a globally convergent one for which, under suitable assumptions, convergence to KKT points can be proved.
MSC:
| 90C26 | Nonconvex programming, global optimization |
| 90C06 | Large-scale problems in mathematical programming |
| 65K05 | Numerical mathematical programming methods |
Citations:
Zbl 1263.49029References:
| [1] | Andreani, R.; Castro, S. L.C.; Chela, J. L.; Friedlander, A.; Santos, S. A., An inexact-restoration method for nonlinear bilevel programming problems, Comput. Optim. Appl., 43, 307-328 (2009) · Zbl 1170.90484 |
| [2] | Birgin, E. G.; Martínez, J. M., Local convergence of an inexact-restoration method and numerical experiments, J. Optim. Theory Appl., 127, 229-247 (2005) · Zbl 1116.90094 |
| [3] | Bueno, L. F.; Friedlander, A.; Martínez, J. M.; Sobral, F. N.C., Inexact restoration method for derivative-free optimization with smooth constraints, SIAM J. Optim., 23, 1189-1213 (2013) · Zbl 1280.65050 |
| [4] | Gomes-Ruggiero, M. A.; Martínez, J. M.; Santos, S. A., Spectral projected gradient method with inexact restoration for minimization with nonconvex constraints, SIAM J. Sci. Comput., 31, 1628-1652 (2009) · Zbl 1220.90123 |
| [5] | Gonzaga, C. C.; Karas, E. W.; Vanti, M., A globally convergent filter method for nonlinear programming, SIAM J. Optim., 14, 646-669 (2004) · Zbl 1079.90129 |
| [6] | Francisco, J. B.; Martínez, J. M.; Martínez, L.; Pisnitchenko, F., Inexact restoration method for minimization problems arising in electronic structure calculations, Comput. Optim. Appl., 50, 555-590 (2011) · Zbl 1263.90090 |
| [7] | Karas, E. W.; Gonzaga, C. C.; Ribeiro, A. A., Local convergence of filter methods for equality constrained non-linear programming, Optimization, 59, 1153-1171 (2010) · Zbl 1221.49058 |
| [8] | Karas, E. W.; Pilotta, E. A.; Ribeiro, A. A., Numerical comparison of merit function with filter criterion in inexact restoration algorithms using hard-spheres problems, Comput. Optim. Appl., 44, 427-441 (2009) · Zbl 1181.90245 |
| [9] | Kaya, C. Y., Inexact restoration for Runge-Kutta discretization of optimal control problems, SIAM J. Numer. Anal., 48, 1492-1517 (2010) · Zbl 1230.49029 |
| [10] | Kaya, C. Y.; Martínez, J. M., Euler discretization and inexact restoration for optimal control, J. Optim. Theory Appl., 134, 191-206 (2007) · Zbl 1135.49019 |
| [11] | Martínez, J. M., Inexact-restoration method with Lagrangian tangent decrease and new merit function for nonlinear programming, J. Optim. Theory Appl., 111, 39-58 (2001) · Zbl 1052.90089 |
| [12] | Martínez, J. M.; Pilotta, E. A., Inexact-restoration algorithms for constrained optimization, J. Optim. Theory Appl., 104, 135-163 (2000) · Zbl 0969.90094 |
| [13] | Banihashemi, N.; Kaya, C. Y., Inexact restoration for Euler discretization of box-constrained optimal control problems, J. Optim. Theory Appl., 156, 726-760 (2013) · Zbl 1263.49029 |
| [14] | Fischer, A.; Friedlander, A., A new line search inexact restoration approach for nonlinear programming, Comput. Optim. Appl., 46, 333-346 (2010) · Zbl 1220.90122 |
| [15] | Bueno, L. F.; Haeser, G.; Martínez, J. M., A flexible inexact restoration method for constrained optimization, J. Optim. Theory Appl. (2014), in press · Zbl 1322.90093 |
| [16] | Izmailov, A. F.; Kurennoy, A. S.; Solodov, M. V., Some composite-step constrained optimization methods interpreted via the perturbed sequential quadratic programming framework, Optim. Methods Softw. (2014), in press · Zbl 1327.90313 |
| [17] | Fiacco, A. V., Introduction to Sensitivity and Stability Analysis in Nonlinear Programming (1983), Academic Press · Zbl 0543.90075 |
| [18] | Jittorntrum, K., Sequential algorithms in nonlinear programming, Bull. Aust. Math. Soc., 19, 151-153 (1978) |
| [19] | Jittorntrum, K., Solution point differentiability without strict complementarity in nonlinear programming, Math. Program., 21, 127-138 (1984) · Zbl 0571.90080 |
| [20] | Lanczos, C., An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Res. Natl. Bur. Stand., 45, 255-282 (1950) |
| [21] | Qi, L., Convergence analysis of some algorithms for solving nonsmooth equations, Math. Oper. Res., 18, 227-244 (1993) · Zbl 0776.65037 |
| [22] | Mifflin, R., Semismooth and semiconvex functions in constrained optimization, SIAM J. Control Optim., 15, 959-972 (1977) · Zbl 0376.90081 |
| [23] | Qi, L.; Sun, J., A nonsmooth version of Newton’s method, Math. Program., 58, 353-367 (1993) · Zbl 0780.90090 |
| [24] | Martínez, J. M., Generalization of the methods of Brent and Brown for solving nonlinear simultaneous equations, SIAM J. Numer. Anal., 16, 434-448 (1979) · Zbl 0424.65019 |
| [25] | Andreani, R.; Haeser, G.; Martínez, J. M., On sequential optimality conditions for smooth constrained optimization, Optimization, 60, 627-641 (2011) · Zbl 1225.90123 |
| [26] | Andreani, R.; Haeser, G.; Schuverdt, M. L.; Silva, P. J.S., Two new weak constraint qualifications and applications, SIAM J. Optim., 22, 1109-1135 (2012) · Zbl 1302.90244 |
| [27] | Nocedal, J.; Wright, S. J., Numerical Optimization (2006), Springer: Springer New York · Zbl 1104.65059 |
| [29] | Andreani, R.; Birgin, E. G.; Martínez, J. M.; Schuverdt, M. L., On augmented Lagrangian methods with general lower-level constraints, SIAM J. Optim., 18, 1286-1309 (2007) · Zbl 1151.49027 |
| [30] | Birgin, E. G.; Castelani, E. V.; Martinez, A. L.M.; Martínez, J. M., Outer trust-region method for constrained optimization, J. Optim. Theory Appl., 150, 142-155 (2011) · Zbl 1222.90059 |
| [31] | Andreani, R.; Birgin, E. G.; Martínez, J. M.; Schuverdt, M. L., Augmented Lagrangian methods under the constant positive linear dependence constraint qualification, Math. Program., 111, 5-32 (2008) · Zbl 1163.90041 |
| [32] | Wächter, A.; Biegler, L. T., On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 25-57 (2006) · Zbl 1134.90542 |
| [33] | Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213 (2002) · Zbl 1049.90004 |
| [34] | Gould, N. I.M.; Orban, D.; Toint, Ph. L., CUTEst and SifDec, a constrained and unconstrained testing environment with safe threads, Technical Report RAL-TR-2013-005 (2013), Rutherford Appleton Laboratory: Rutherford Appleton Laboratory Chilton, Oxfordshire, England |
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.
