zbMATH — the first resource for mathematics

Constraint aggregation for rigorous global optimization. (English) Zbl 1342.90142
Authors’ abstract: In rigorous constrained global optimization, upper bounds on the objective function help to reduce the search space. Obtaining a rigorous upper bound on the objective requires finding a narrow box around an approximately feasible solution, which then must be verified to contain a feasible point. Approximations are easily found by local optimization, but the verification often fails. In this paper we show that even when the verification of an approximate feasible point fails, the information extracted from the results of the local optimization can still be used in many cases to reduce the search space. This is done by a rigorous filtering technique called constraint aggregation. It forms an aggregated redundant constraint, based on approximate Lagrange multipliers or on a vector valued measure of constraint violation. Using the optimality conditions, two-sided linear relaxations, the Gauss-Jordan algorithm and a directed modified Cholesky factorization, the information in the redundant constraint is turned into powerful bounds on the feasible set. Constraint aggregation is especially useful since it also works in a tiny neighborhood of the global optimizer, thereby reducing the cluster effect. A simple introductory example demonstrates how our new method works. Extensive tests show the performance on a large benchmark.

90C26 Nonconvex programming, global optimization
90C20 Quadratic programming
90C46 Optimality conditions and duality in mathematical programming
65K05 Numerical mathematical programming methods
Full Text: DOI
[1] Benhamou, F., McAllister, D., Van Hentenryck, P.: CLP (intervals) revisited. In: Proceedings of International Symposium on Logic Programming, pp. 124-138. MIT Press, Cambridge (1994) · Zbl 1113.90124
[2] Benhamou, F., Goualard, F., Granvilliers, L., Puget, J.F.: Revising hull and box consistency. In: International Conference on Logic Programming, pp. 230-244, (1999). http://citeseer.ist.psu.edu/benhamou99revising.html · Zbl 0856.90104
[3] Chabert, G., Jaulin, L.: Hull consistency under monotonicity. In: Principle and Practices of Constraint Programming—CP2009, pp. 188-195 (2009)
[4] Collavizza, H; Delobel, F; Rueher, M, Comparing partial consistencies, Reliab. Comput., 5, 213-228, (1999) · Zbl 0947.65069
[5] Domes, F.: GloptLab—a configurable framework for the rigorous global solution of quadratic constraint satisfaction problems. Optim. Methods Softw., 24, 727-747 (2009). http://www.mat.univie.ac.at/ dferi/publ/Gloptlab.pdf · Zbl 1180.90217
[6] Domes, F., Neumaier, A.: Constraint propagation on quadratic constraints. Constraints 15, 404-429 (2010). http://www.mat.univie.ac.at/ dferi/publ/Propag.pdf · Zbl 1208.68200
[7] Domes, F., Neumaier, A.: Rigorous filtering using linear relaxations. J. Glob. Optim. 53, 441-473, (2012). http://www.mat.univie.ac.at/ dferi/publ/Linear.pdf · Zbl 1275.90051
[8] Domes, F., Neumaier, A.: Rigorous verification of feasibility. J. Glob. Optim. pp. 1-24 (2014a). http://www.mat.univie.ac.at/ dferi/publ/Feas_csp.pdf. Online first · Zbl 0349.90100
[9] Domes, F., Neumaier, A.: JGloptLab—a rigorous global optimization software. in preparation (2014b). http://www.mat.univie.ac.at/ dferi/publ/
[10] Domes, F., Neumaier, A.: Directed modified Cholesky factorization and ellipsoid relaxations. SIAM J. Matrix Anal. Appl. (2014c). http://www.mat.univie.ac.at/ dferi/publ/. Submitted
[11] Domes, F., Fuchs, M., Schichl, H., Neumaier, A.: The optimization test environment. Optim. Eng. 15, 443-468 (2014). http://www.mat.univie.ac.at/ dferi/testenv.html · Zbl 1364.90006
[12] Garloff, J., Jansson, C., Smith, A.: Lower bound functions for polynomials. J. Comput. Appl. Math. 157, 207-225 (2003). http://citeseer.ist.psu.edu/534450.html · Zbl 1032.65055
[13] Goldsztejn, A., Domes, F., Chevalier, B.: First order rejection tests for multiple-objective optimization. J. Glob. Optim., pp. 1-20 (2013). http://www.mat.univie.ac.at/ dferi/research/FirstOrder.pdf · Zbl 1301.90082
[14] Hansen, E.R.: Global Optimization Using Interval Analysis. Marcel Dekker Inc., New York (1992) · Zbl 0762.90069
[15] Hongthong, S., Kearfott, R.B.: Rigorous linear overestimators and underestimators. Technical report, University of Louisiana, (2004). http://interval.louisiana.edu/preprints/estimates_of_powers.pdf
[16] Kaisheng, D., Kearfott, R.B.: The cluster problem in multivariate global optimization. J. Glob. Optim. 5(3), 253-265 (1994). http://interval.louisiana.edu/preprints/multcluster.pdf · Zbl 0824.90121
[17] Kearfott, R.B.: On proving existence of feasible points in equality constrained optimization problems. Math. Program. 83(1-3), 89-100 (1995). http://interval.louisiana.edu/preprints/constrai.pdf · Zbl 0949.90089
[18] Kearfott, R.B.: On verifying feasibility in equality constrained optimization problems. Technical report, University of Louisiana (1996). http://interval.louisiana.edu/preprints/big_constrai.pdf
[19] Kearfott, R.B.: Improved and simplified validation of feasible points: inequality and equality constrained problems. (2005) http://interval.louisiana.edu/preprints/2005_simplified_feasible_point_verification.pdf
[20] Kearfott, R.B., Nakao, M.T., Neumaier, A., Rump, S.M., Shary, S.P., van Hentenryck, P.: Standardized notation in interval analysis. In: Proceedings of XIII Baikal International School-Seminar “Optimization Methods and their Applications”, Volume 4, pp. 106-113, Institute of Energy Systems, Baikal, Irkutsk (2005)
[21] Kolev, LV, Automatic computation of a linear interval enclosure, Reliab. Comput., 7, 17-28, (2001) · Zbl 0979.65041
[22] Lebbah, Y., Michel, C., Rueher, M.: A rigorous global filtering algorithm for quadratic constraints. Constraints 10, 47-65 (2005). http://ylebbah.googlepages.com/research · Zbl 1066.90090
[23] Lhomme, O.: Consistency techniques for numeric csps. In: IJCAI vol. 1, pp. 232-238 (1993) · Zbl 1080.65041
[24] McCormick, G, Computability of global solutions to factorable non-convex programs: part I—convex underestimating problems, Math. Program., 10, 147-175, (1976) · Zbl 0349.90100
[25] Neumaier, A.: Interval Methods for Systems of Equations, volume 37 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (1990)
[26] Neumaier, A.: An optimality criterion for global quadratic optimization. J. Glob. Optim. 2, 201-208 (1992). http://www.mat.univie.ac.at/ neum/scan/66.pdf · Zbl 0783.90095
[27] Neumaier, A, Complete search in continuous global optimization and constraint satisfaction, Acta Numer., 1004, 271-369, (2004) · Zbl 1113.90124
[28] Sahinidis, NV, BARON: a general purpose global optimization software package, J. Glob. Optim., 8, 201-205, (1996) · Zbl 0856.90104
[29] Sahinidis, N.V.: BARON 12.1.0: Global Optimization of Mixed-Integer Nonlinear Programs, User’s Manual (2013). http://www.gams.com/dd/docs/solvers/baron.pdf
[30] Schichl, H., Markót, M.C.: Algorithmic differentiation techniques for global optimization in the COCONUT environment. Optim. Methods Softw. 27(2), 359-372 (2012). http://www.mat.univie.ac.at/ herman/papers/griewank.pdf · Zbl 1242.65047
[31] Schichl, H; Neumaier, A, Exclusion regions for systems of equations, SIAM J. Numer. Anal., 42, 383-408, (2004) · Zbl 1080.65041
[32] Schichl, H., Neumaier, A.: Transposition theorems and qualification-free optimality conditions. SIAM J. Optim. 17, 1035-1055 (2006). http://www.mat.univie.ac.at/ neum/ms/trans.pdf · Zbl 1136.90043
[33] Shcherbina, O., Neumaier, A., Sam-Haroud, D., Vu, X.-H., Nguyen, T.-V.: Benchmarking global optimization and constraint satisfaction codes. In: Bliek, Ch., Jermann, Ch., Neumaier, A. (eds.) Global Optimization and Constraint Satisfaction, pp. 211-222. Springer, Berlin (2003). http://www.mat.univie.ac.at/ neum/ms/bench.pdf · Zbl 1296.90004
[34] Sherali, H., Adams, W.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer, Dordrecht (1999) · Zbl 0926.90078
[35] Vu, X.-H., Schichl, H., Sam-Haroud, D.: Using directed acyclic graphs to coordinate propagation and search for numerical constraint satisfaction problems. In: Proceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2004), pp. 72-81 (2004). http://www.mat.univie.ac.at/ herman/papers/ICTAI2004.pdf
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.