×

Linear and parabolic relaxations for quadratic constraints. (English) Zbl 1351.90131

Summary: This paper presents new techniques for filtering boxes in the presence of an additional quadratic constraint, a problem relevant for branch and bound methods for global optimization and constraint satisfaction. This is done by generating powerful linear and parabolic relaxations from a quadratic constraint and bound constraints, which are then subject to standard constraint propagation techniques. The techniques are often applicable even if the original box is unbounded in some but not all variables. As an auxiliary tool – needed to make our theoretical results implementable in floating-point arithmetic without sacrificing mathematical rigor – we extend the directed Cholesky factorization from F. Domes and A. Neumaier [SIAM J. Matrix Anal. Appl. 32, No. 1, 262–285 (2011; Zbl 1242.90152)] to a partial directed Cholesky factorization with pivoting. If the quadratic constraint is convex and the initial bounds are sufficiently wide, the final relaxation and the enclosure are optimal up to rounding errors. Numerical tests show the usefulness of the new factorization methods in the context of filtering.

MSC:

90C26 Nonconvex programming, global optimization
90C20 Quadratic programming
65F30 Other matrix algorithms (MSC2010)
65G20 Algorithms with automatic result verification

Citations:

Zbl 1242.90152
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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
[2] Domes, F., Neumaier, A.: Constraint propagation on quadratic constraints. Constraints 15, 404-429 (2010). http://www.mat.univie.ac.at/ dferi/research/Propag.pdf · Zbl 1208.68200
[3] Domes, F., Neumaier, A.: Rigorous enclosures of ellipsoids and directed Cholesky factorizations. SIAM J. Matrix Anal. Appl. 32, 262-285 (2011). http://www.mat.univie.ac.at/ dferi/research/Cholesky.pdf · Zbl 1242.90152
[4] Domes, F., Neumaier, A.: Constraint aggregation in global optimization. In: Mathematical Programming pp. 1-27, (2014). Online First. http://www.mat.univie.ac.at/ dferi/research/Aggregate.pdf · Zbl 1342.90142
[5] Domes, F., Neumaier, A.: Directed modified Cholesky factorization and ellipsoid relaxations. Technical report, University of Vienna, (2014). http://www.mat.univie.ac.at/ dferi/research/Modchol.pdf · Zbl 1301.90063
[6] Domes, F., Neumaier, A.: JGloptLab: a rigorous global optimization software (in preparation) (2014). http://www.mat.univie.ac.at/ dferi/publications.html · Zbl 1342.90142
[7] Domes, F., Neumaier, A.: Rigorous verification of feasibility. J. Glob. Optim. pp. 1-24, (2014). http://www.mat.univie.ac.at/ dferi/research/Feas_csp.pdf · Zbl 1318.90065
[8] Frommer, A., Hashemi, B.: Verified stability analysis using the lyapunov matrix equation. Electron. Trans. Numer. Anal. 40, 187-203 (2013) · Zbl 1288.65058
[9] Hansen, E.R.: Global Optimization Using Interval Analysis. Marcel Dekker Inc., New York (1992) · Zbl 0762.90069
[10] 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
[11] 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”, Vol 4, pp. 106-113. Irkutsk: Institute of Energy Systems, Baikal (2005) · Zbl 1196.65088
[12] Misener, R., Floudas, C.A.: GloMIQO: global mixed-integer quadratic optimizer. J. Glob. Optim. 57(1), 3-50 (2013). doi:10.1007/s10898-012-9874-7 · Zbl 1272.90034 · doi:10.1007/s10898-012-9874-7
[13] Misener, R., Floudas, C.A.: ANTIGONE: algorithms for coNTinuous/integer global optimization of nonlinear equations. J. Glob. Optim. 59(2-3), 503-526 (2014). doi:10.1007/s10898-014-0166-2 · Zbl 1301.90063 · doi:10.1007/s10898-014-0166-2
[14] Neumaier, A., Shcherbina, O., Huyer, W., Vinkó, T.: A comparison of complete global optimization solvers. Math. Program. B 103, 335-356 (2005) · Zbl 1099.90001 · doi:10.1007/s10107-005-0585-4
[15] 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
[16] Schichl, H., Markót, M.C., Neumaier, A., Vu, X.-H., Keil, C.: The COCONUT environment, 2000-2010. Software. http://www.mat.univie.ac.at/coconut-environment · Zbl 0716.65023
[17] Schichl, H., Neumaier, A., Markót, M., Domes, F.: On solving mixed-integer constraint satisfaction problems with unbounded variables. In: Gomes, C., Sellmann, M. (eds) Integration of AI and OR Techniques in constraint programming for combinatorial optimization problems, volume 7874 of lecture notes in computer science, pp. 216-233. Springer, Berlin (2013). http://www.mat.univie.ac.at/ dferi/research/cpaior2013.pdf · Zbl 1382.90067
[18] Schnabel, R.B., Eskow, E.: A new modified Cholesky factorization. SIAM J. Sci. Stat. Comput. 11(6), 1136-1158 (1990) · Zbl 0716.65023 · doi:10.1137/0911064
[19] Schnabel, R.B., Eskow, E.: A revised modified Cholesky factorization algorithm. SIAM J. Optim. 9(4), 1135-1148 (1999) · Zbl 0958.65034 · doi:10.1137/S105262349833266X
[20] 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 (2003). http://www.mat.univie.ac.at/ neum/ms/bench.pdf · Zbl 1296.90004
[21] 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). doi:10.1007/s10107-004-0559-y · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y
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.