Abstract
In this paper we propose AbsTaylor, a simple and quick method for extracting inner polytopes, i.e., entirely feasible convex regions in which all points satisfy the constraints. The method performs an inner linearization of the nonlinear constraints by using a Taylor form. Unlike a previous proposal, the expansion point of the Taylor form is not limited to the bounds of the domains, thus producing, in general, a tighter approximation. For testing the approach, AbsTaylor was introduced as an upper bounding method in a state-of-the-art global branch & bound optimizer. Furthermore, we implemented a local search method which extracts feasible inner polytopes for iteratively finding better solutions inside them. In the studied instances, the new method finds in average four times more inner regions and significantly improves the optimizer performance.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
An interval \({\varvec{x}}_i=[\underline{x_i},\overline{x_i}]\) defines the set of reals \(x_i\), such that \(\underline{x_i} \le x_i \le \overline{x_i}\). A box \({\varvec{x}}\) is a Cartesian product of intervals \({\varvec{x}}_1 \times \cdots \times {\varvec{x}}_i \times \cdots \times {\varvec{x}}_n\)
Karush–Kuhn–Tucker (KKT) conditions are necessary conditions for a solution to be optimal [17].
Providing that an initial feasible solution is given. Otherwise the same method may find an initial feasible solution.
E.g., similarly to XTaylor, XNewton generates linear relaxations of the constraints by choosing random corners of the box as expansion points.
The other tested values of \(\alpha \) were 0.1, 0.2, 0.7, 0.8, 0.9 and 0.99.
They were run on a computer with an Intel Xeon X5650 2.67 GHz processor with 24 GB RAM on a 64 bit Linux version.
References
Trombettoni, G., Araya, I., Neveu, B., Chabert, G.: Inner regions and interval linearizations for global optimization. In: AAAI Conference on Artificial Intelligence, (2011)
Sahinidis, N.V.: Baron: a general purpose global optimization software package. J. Glob. Optim. 8(2), 201–205 (1996)
Misener, R., Floudas, C.A.: Antigone: algorithms for continuous/integer global optimization of nonlinear equations. J. Glob. Optim. 59, 1–24 (2013)
Schrage, L.: Linear, Integer and Quadratic Programming with LINDO. The Scientific Press, Singapore (1986)
Belotti, P.: Couenne: a user’s manual. Technical report, Lehigh University, Tech. Rep. (2009)
Lebbah, Y.: ICOS: a branch and bound based solver for rigorous global optimization. Optim. Methods Softw. 24(4–5), 709–726 (2009)
Kearfott, R.B.: Rigorous Global Search Continuous Problems. Springer, Berlin (1996)
Araya, I., Reyes, V.: Interval branch-and-bound algorithms for optimization and constraint satisfaction: a survey and prospects. J. Glob. Optim. 65(4), 837–866 (2016)
Araya, I., Trombettoni, G., Neveu, B., Chabert, G.: Upper bounding in inner regions for global optimization under inequality constraints. J. Glob. Optim. 60(2), 145–164 (2014)
Ninin, J., Messine, F., Hansen, P.: A reliable affine relaxation method for global optimization. 4OR 13(3), 247–277 (2015)
Goldsztejn, A., Lebbah, Y., Michel, C., Rueher, M.: Revisiting the upper bounding process in a safe branch and bound algorithm. In: Beck, J.C. (ed.) Principles and Practice of Constraint Programming, pp. 598–602. Springer, Berlin (2008)
Drud, A.S.: CONOPT—a large-scale GRG code. ORSA J. Comput. 6(2), 207–216 (1994)
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(1), 25–57 (2006)
Khajavirad, A., Sahinidis, N.V.: A hybrid LP/NLP paradigm for global optimization relaxations. Math. Program. Comput. 10(3), 383–421 (2018)
Lasdon, L.S., Waren, A.D., Jain, A., Ratner, M.: Design and testing of a generalized reduced gradient code for nonlinear programming. Stanford University CA Systems Optimization Lab, Technical Report (1976)
Wright, S.J.: Primal-Dual Interior-Point Methods, vol. 54. SIAM, Philadelphia (1997)
Kuhn, H., Tucker, A.: Nonlinear programming. In: Second Berkeley Symposium on Mathematical Statistics and Probability, pp. 481–492 (1951)
Nocedal, J., Wächter, A., Waltz, R.A.: Adaptive barrier update strategies for nonlinear interior methods. SIAM J. Optim. 19(4), 1674–1693 (2009)
Yuan, Y.-X.: Recent advances in trust region algorithms. Math. Program. 151(1), 249–281 (2015)
Coleman, T.F., Li, Y.: An interior trust region approach for nonlinear minimization subject to bounds. SIAM J. Optim. 6(2), 418–445 (1996)
Omojokun, E.O.: Trust region algorithms for optimization with nonlinear equality and inequality constraints. Ph.D Dissertation, University of Colorado (1989)
Araya, I., Neveu, B.: lsmear: a variable selection strategy for interval branch and bound solvers. J. Glob. Optim. 71, 1–18 (2017)
Benhamou, F., Goualard, F., Granvilliers, L., Puget, J.-F.: Revising hull and box consistency. In: International Conference on Logic Programming. Citeseer (1999)
Trombettoni, G., Chabert, G.: Constructive interval disjunction. In: Bessiere, C. (ed.) Principles and Practice of Constraint Programming-CP 2007, pp. 635–650. Springer, Berlin (2007)
Araya, I., Trombettoni, G., Neveu, B.: A contractor based on convex interval taylor, In: Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems, pp. 1–16. Springer (2012)
Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201–213 (2002)
Acknowledgements
This work is supported by the Fondecyt Project 1160224. Victor Reyes is supported by the Grant Postgrado PUCV 2018.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Reyes, V., Araya, I. AbsTaylor: upper bounding with inner regions in nonlinear continuous global optimization problems. J Glob Optim 79, 413–429 (2021). https://doi.org/10.1007/s10898-020-00878-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-020-00878-z