×

Supporting global numerical optimization of rational functions by generic symbolic convexity tests. (English) Zbl 1290.65053

Gerdt, Vladimir P. (ed.) et al., Computer algebra in scientific computing. 12th international workshop, CASC 2010, Tsakhkadzor, Armenia, September 6–12, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15273-3/pbk). Lecture Notes in Computer Science 6244, 205-219 (2010).
Summary: Convexity is an important property in nonlinear optimization since it allows to apply efficient local methods for finding global solutions. We propose to apply symbolic methods to prove or disprove convexity of rational functions over a polyhedral domain. Our algorithms reduce convexity questions to real quantifier elimination problems. Our methods are implemented and publicly available in the open source computer algebra system Reduce. Our long term goal is to integrate Reduce as a “workhorse” for symbolic computations into a numerical solver.
For the entire collection see [Zbl 1195.68004].

MSC:

65K10 Numerical optimization and variational techniques
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ballerstein, M., Michaels, D., Seidel-Morgenstern, A., Weismantel, R.: A theoretical study of continuous counter-current chromatography for adsorption isotherms with inflection points. Computers & Chemical Engineering 34(4), 447–459 (2010) · doi:10.1016/j.compchemeng.2009.10.001
[2] Grossmann, I.E. (ed.): Global Optimization in Engineering Design. Kluwer Academic Publishers, Dordrecht (1996) · Zbl 0869.00021
[3] Grossmann, I.E., Kravanja, Z.: Mixed-integer nonlinear programming: A survey of algorithms and applications. In: Conn, A., Biegler, L., Coleman, T., Santosa, F. (eds.) Large-Scale Optimization with Applications, Part II: Optimal Design and Control. Springer, Heidelberg (1997) · Zbl 0884.65058
[4] Jüdes, M., Tsatsaronis, G., Vigerske, S.: Optimization of the design and partial-load operation of power plants using mixed-integer nonlinear programming. In: Kallrath, J., Pardalos, P., Rebennack, S., Scheidt, M. (eds.) Optimization in the Energy Industry. Springer, Heidelberg (2009) · Zbl 1160.90601
[5] Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming: Theory, Algorithms, Software, and Applications. Kluwer Academic Publishers, Dordrecht (2002) · Zbl 1031.90022 · doi:10.1007/978-1-4757-3532-1
[6] Nocedal, J., Wright, S.: Numerical Optimization. Springer, Heidelberg (2000) · Zbl 0930.65067
[7] Adjiman, C.S., Floudas, C.A.: Rigorous convex underestimators for general twice-differentiable problems. Journal of Global Optimization 9, 23–40 (1997) · Zbl 0862.90114 · doi:10.1007/BF00121749
[8] Fourer, R., Maheshwari, C., Neumaier, A., Orban, D., Schichl, H.: Convexity and concavity detection in computational graphs: Tree walks for convexity assessment. INFORMS Journal on Computing 22(1), 26–43 (2009) · Zbl 1243.90004 · doi:10.1287/ijoc.1090.0321
[9] Mönnigmann, M.: Efficient calculation of bounds on spectra of Hessian matrices. SIAM Journal on Scientific Computing 30(5), 2340–2357 (2008) · Zbl 1181.65055 · doi:10.1137/070704186
[10] Nenov, I.P., Fylstra, D.H., Kolev, L.V.: Convexity determination in the Microsoft Excel solver using automatic differentiation techniques. Technical report, Frontline Systems Inc. (2004)
[11] Sturm, T., Weber, A.: Investigating generic methods to solve Hopf bifurcation problems in algebraic biology. In: Horimoto, K., Regensburger, G., Rosenkranz, M., Yoshida, H. (eds.) AB 2008. LNCS, vol. 5147, pp. 200–215. Springer, Heidelberg (2008) · Zbl 1171.92301 · doi:10.1007/978-3-540-85101-1_15
[12] Sturm, T., Weber, A., Abdel-Rahman, E.O., El Kahoui, M.: Investigating algebraic and logical algorithms to solve Hopf bifurcation problems in algebraic biology. Mathematics in Computer Science 2(3), 493–515 (2009) · Zbl 1205.37062 · doi:10.1007/s11786-008-0067-1
[13] Tarski, A.: A decision method for elementary algebra and geometry. Prepared for publication by J.C.C. McKinsey. RAND Report R109, August 1 (1948) (revised May 1951); Second Edition, RAND, Santa Monica, CA (1957) · Zbl 0035.00602
[14] Basu, S., Pollack, R., Roy, M.F.: On the combinatorial and algebraic complexity of quantifier elimination. Journal of the ACM 43(6), 1002–1045 (1996) · Zbl 0885.68070 · doi:10.1145/235809.235813
[15] Weispfenning, V.: The complexity of linear problems in fields. Journal of Symbolic Computation 5(1&2), 3–27 (1988) · Zbl 0646.03005 · doi:10.1016/S0747-7171(88)80003-8
[16] Weispfenning, V.: Quantifier elimination for real algebra–the quadratic case and beyond. Applicable Algebra in Engineering Communication and Computing 8(2), 85–101 (1997) · Zbl 0867.03003 · doi:10.1007/s002000050055
[17] Collins, G.E., Hong, H.: Partial cylindrical algebraic decomposition for quantifier elimination. Journal of Symbolic Computation 12(3), 299–328 (1991) · Zbl 0754.68063 · doi:10.1016/S0747-7171(08)80152-6
[18] Dolzmann, A., Sturm, T.: Redlog: Computer algebra meets computer logic. ACM SIGSAM Bulletin 31(2), 2–9 (1997) · doi:10.1145/261320.261324
[19] Davenport, J.H., Heintz, J.: Real quantifier elimination is doubly exponential. Journal of Symbolic Computation 5(1-2), 29–35 (1988) · Zbl 0663.03015 · doi:10.1016/S0747-7171(88)80004-X
[20] Dolan, E.D., Moré, J.J., Munson, T.S.: Benchmarking optimization software with COPS 3.0. Technical Report ANL/MCS-273, Mathematics and Computer Science Division, Argonne National Laboratory (2004), http://www.mcs.anl.gov/ more/cops
[21] Bonami, P., Kilinç, M., Linderoth, J.: Algorithms and software for convex mixed integer nonlinear programs (2009), Optimization Online, http://www.optimization-online.org/DB_HTML/2009/10/2429.html · Zbl 1242.90121
[22] Bussieck, M.R., Drud, A.S., Meeraus, A.: MINLPLib–A Collection of Test Models for Mixed-Integer Nonlinear Programming. INFORMS Journal on Computing 15(1), 114–119 (2003), http://www.gamsworld.org/minlp/minlplib.htm · Zbl 1238.90104 · doi:10.1287/ijoc.15.1.114.15159
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.