Constrained optimization with integer and continuous variables using inexact restoration and projected gradients. (English) Zbl 1392.90104
Summary: Inexact restoration (IR) is a well established technique for continuous minimization problems with constraints that can be applied to constrained optimization problems with specific structures. When some variables are restricted to be integer, an IR strategy seems to be appropriate. The IR strategy employs a restoration procedure in which one solves a standard nonlinear programming problem and an optimization procedure in which the constraints are linearized and techniques for mixed-integer (linear or quadratic) programming can be employed.
References:
| [1] | Fletcher, R.; Leyffer, S., Solving mixed integer nonlinear programs by outer approximation, Mathematical Programming, 66(1):327-349, 327-349, (1994) · Zbl 0833.90088 · doi:10.1007/BF01581153 |
| [2] | Floudas, C. A., Nonlinear and Mixed-Integer Optimization: Fundamentals and Applications, Topics in Chemical Engineering. Oxford University Press, London, (1995) · Zbl 0886.90106 |
| [3] | Grossmann, I. E., Review of nonlinear mixed-integer and disjunctive programming techniques, Optimization and Engineering, 3(3):227-252, 227-252, (2002) · Zbl 1035.90050 · doi:10.1023/A:1021039126272 |
| [4] | Birgin, E. G.; Martínez, J. M., Practical Augmented Lagrangian Methods for Constrained Optimization, Society for Industrial and Applied Mathematics, Philadelphia, PA, (2016) · Zbl 1339.90312 · doi:10.1137/1.9781611973365 |
| [5] | Birgin, E. G.; Bueno, L. F.; Martínez, J. M., Assessing the reliability of general-purpose Inexact Restoration methods, Journal of Computational and Applied Mathematics, 282:1-16, 1-16, (2015) · Zbl 1310.90088 · doi:10.1016/j.cam.2014.12.031 |
| [6] | Andreani, R.; Castro, S. L.C.; Chela, J. L.; Friedlander, A.; Santos, S. A., An inexact-restoration method for nonlinear bilevel programming problems, Computational Optimization and Applications, 43(3):307-328, 307-328, (2009) · Zbl 1170.90484 · doi:10.1007/s10589-007-9147-4 |
| [7] | Banihashemi, N.; Kaya, C. Y., Inexact Restoration for Euler Discretization of Box-Constrained Optimal Control Problems, Journal of Optimization Theory and Applications, 156(3):726-760, 727-760, (2013) · Zbl 1263.49029 · doi:10.1007/s10957-012-0140-4 |
| [8] | Birgin, E. G.; Martínez, J. M., Local Convergence of an Inexact-Restoration Method and Numerical Experiments, Journal of Optimization Theory and Applications, 127(2):229-247, 229-247, (2005) · Zbl 1116.90094 · doi:10.1007/s10957-005-6537-6 |
| [9] | Birgin, E. G.; Martínez, J. M.; Raydan, M., Inexact Spectral Projected Gradient methods on convex sets, IMA Journal of Numerical Analysis, 23(4):539-559, 539-559, (2003) · Zbl 1047.65042 · doi:10.1093/imanum/23.4.539 |
| [10] | Bueno, L. F.; Friedlander, A.; Martínez, J. M.; Sobral, F. N.C., Inexact Restoration Method for Derivative-Free Optimization with Smooth Constraints, SIAM Journal on Optimization, 23(2):1189-1213, 1189-1213, (2013) · Zbl 1280.65050 · doi:10.1137/110856253 |
| [11] | Fischer, A.; Friedlander, A., A new line search Inexact Restoration approach for nonlinear programming, Computational Optimization and Applications, 46(2):333-346, 333-346, (2010) · Zbl 1220.90122 · doi:10.1007/s10589-009-9267-0 |
| [12] | Gomes-Ruggiero, M. A.; Martínez, J. M.; Santos, S. A., Spectral Projected Gradient Method with Inexact Restoration for Minimization with Nonconvex Constraints, SIAM Journal on Scientific Computing, 31(3):1628-1652, 1628-1652, (2009) · Zbl 1220.90123 · doi:10.1137/070707828 |
| [13] | Kaya, C. Y.; Martínez, J. M., Euler Discretization and Inexact Restoration for Optimal Control, Journal of Optimization Theory and Applications, 134(2):191-206, 191-206, (2007) · Zbl 1135.49019 · doi:10.1007/s10957-007-9217-x |
| [14] | Krejić, N.; Martínez, J. M., Inexact Restoration approach for minimization with inexact evaluation of the objective function, Mathematics of Computation, 85:1775-1791, http://www.ams.org/journals/mcom/2016-85-300/S0025-5718-2015-03025-7, 1775-1791, (2016) · Zbl 1335.65053 |
| [15] | Martínez, J. M., Inexact-Restoration Method with Lagrangian Tangent Decrease and New Merit Function for Nonlinear Programming, Journal of Optimization Theory and Applications, 111(1):39-58, 39-58, (2001) · Zbl 1052.90089 · doi:10.1023/A:1017567113614 |
| [16] | Martínez, J. M.; Pilotta, E. A., Inexact-restoration algorithm for constrained optimization, Journal of Optimization Theory and Applications, 104(1):135-163, 135-163, (2000) · Zbl 0969.90094 · doi:10.1023/A:1004632923654 |
| [17] | Andreani, R.; Birgin, E. G.; Martínez, J. M.; Yuan, J., Spectral projected gradient and variable metric methods for optimization with linear inequalities, IMA Journal of Numerical Analysis, 25(2):221-252, 221-252, (1997) · Zbl 1072.90051 · doi:10.1093/imanum/drh020 |
| [18] | Andretta, M.; Birgin, E. G.; Martínez, J. M., Practical active-set Euclidian trust-region method with spectral projected gradients for bound-constrained minimization, Optimization, 54(3):305-325, 305-325, (2005) · Zbl 1079.65070 · doi:10.1080/02331930500100270 |
| [19] | Barzilai, J.; Borwein, J. M., Two-point step size gradient methods, IMA Journal of Numerical Analysis, 8(1):141-148, 141-148, (1988) · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141 |
| [20] | Birgin, E. G.; Martínez, J. M.; Raydan, M., Algorithm 813: SPG–Software for Convex-Constrained Optimization, ACM Transactions on Mathematical Software, 27(3):340-349, 340-349, (2001) · Zbl 1070.65547 · doi:10.1145/502800.502803 |
| [21] | Friedlander, A.; Martínez, J. M.; Raydan, M., A new method for large-scale box constrained convex quadratic minimization problems, Optimization Methods and Software, 5(1):57-74, 57-74, (1995) · doi:10.1080/10556789508805602 |
| [22] | Raydan, M., On the Barzilai and Borwein choice of steplength for the gradient method, IMA Journal of Numerical Analysis, 13(3):321-326, 321-326, (1993) · Zbl 0778.65045 · doi:10.1093/imanum/13.3.321 |
| [23] | Raydan, M., The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM Journal on Optimization, 7(1):26-33, 26-33, (1997) · Zbl 0898.90119 · doi:10.1137/S1052623494266365 |
| [24] | IBM, IBM ILOG CPLEX Optimizer, High-performance mathematical programming solver for linear programming, mixed integer programming, and quadratic programming, http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/, (2011) |
| [25] | Fourer, R.; Gay, D. M.; Kernighan, B. W., AMPL - A Modeling Language for Mathematical Programming, Duxbury Press, 2nd edition, (2002) |
| [26] | Andreani, R.; Birgin, E. G.; Martínez, J. M.; Schuverdt, M. L., On augmented Lagrangian methods with general lower-level constraints, SIAM Journal on Optimization, 18(4):1286-1309, 1286-1309, (2008) · Zbl 1151.49027 · doi:10.1137/060654797 |
| [27] | Arkin, E. M.; Hassin, R., Approximation algorithms for the geometric covering salesman problem, Discrete Applied Mathematics, 55(3):197-218, 197-218, (1994) · Zbl 0819.90115 · doi:10.1016/0166-218X(94)90008-6 |
| [28] | Gentilini, I.; Margot, F.; Shimada, K., The Travelling Salesman Problem with Neighbourhoods: MINLP Solution, Optimization Methods Software, 28(2):364-378, 364-378, (2013) · Zbl 1270.90055 · doi:10.1080/10556788.2011.648932 |
| [29] | Gentilini, I.; Margot, F.; Shimada, K., STSPN Instances, http://wpweb2.tepper.cmu.edu/fmargot/ampl.html, (1998) |
| [30] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman & Co., New York, NY, USA, (1979) · Zbl 0411.68039 |
| [31] | Murty, K. G.; Kabadi, S. N., Some NP-complete problems in quadratic and nonlinear programming, Mathematical Programming, 39(2):117-129, 117-129, (1987) · Zbl 0637.90078 · doi:10.1007/BF02592948 |
| [32] | Sherali, H. D.; Adams, W. P., A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, Nonconvex Optimization and Its Applications. Springer US, (1999) · Zbl 0926.90078 |
| [33] | Tawarmalani, M.; Sahinidis, N. V., Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications, Nonconvex Optimization and Its Applications. Springer US, (2002) · Zbl 1031.90022 |
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.
