Minimizing the sum of many rational functions
Tóm tắt
We consider the problem of globally minimizing the sum of many rational functions over a given compact semialgebraic set. The number of terms can be large (10 to 100), the degree of each term should be small (up to 10), and the number of variables can be relatively large (10 to 100) provided some kind of sparsity is present. We describe a formulation of the rational optimization problem as a generalized moment problem and its hierarchy of convex semidefinite relaxations. Under some conditions we prove that the sequence of optimal values converges to the globally optimal value. We show how public-domain software can be used to model and solve such problems. Finally, we also compare with the epigraph approach and the BARON software.
Tài liệu tham khảo
Ali, M.M., Khompatraporn, C., Zabinsky, Z.B.: A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems. J. Global Optim. 31(4), 635–672 (2005)
Benson, H.P.: Global optimization algorithm for the nonlinear sum of ratios problem. J. Optim. Theory Appl. 112(1), 1–29 (2002)
Benson, H.P.: Using concave envelopes to globally solve the nonlinear sum of ratios problems. J. Global Optim. 22, 343–364 (2002)
Benson, S.J., Ye, Y.: DSDP5 user guide—software for semidefinite programming. Mathematics and Computer Science Division, Argonne National Laboratory (2005)
Bersini, H., Dorigo, M., Langerman, S., Seront, G., Gambardella, L.: Results of the first international contest on evolutionary optimisation. IEEE Intl. Conf. Evolutionary Computation, Nagoya (1996)
Borchers, B.: CSDP, a C library for semidefinite programming. Optim. Methods Softw. 11, 613–623 (1999)
Curto, R.E., Fialkow, L.A.: Recursiveness, positivity, and truncated moment problems. Houston J. Math. 17, 603–635 (1991)
Czyzyk, J., Mesnier, M., Moré, J.: The NEOS server. IEEE J. Comput. Sci. Eng. 5(3), 68–75 (1998)
Freund, R.W., Jarre, F.: Solving the sum-of-ratios problem by an interior-point method. J. Global Optim. 19(1), 83–102 (2001)
Hartley, R., Kahl, F., Olsson, C., Seo, Y.: Verifying global minima for L2 minimization problems in multiple view geometry. Int. J. Comput. Vis. 101(2), 288–304 (2013)
Henrion, D., Lasserre, J.B.: GloptiPoly: global optimization over polynomials with Matlab and SeDuMi. ACM Trans. Math. Softw. 29, 165–194 (2003)
Henrion, D., Lasserre, J.B., Löfberg, J.: GloptiPoly 3: moments, optimization and semidefinite programming. Optim. Methods Softw. 24, 761–779 (2009)
Jibetean, D., de Klerk, E.: Global optimization of rational functions: a semidefinite programming approach. Math. Program. 106, 93–109 (2006)
Kahl, F., Agarwal, S., Chandraker, M., Kriegman, D., Belongie, S.: Practical global optimization for multiview geometry. Int. J. Comput. Vis. 79(3), 271–284 (2008)
Kahl, F., Henrion, D.: Globally optimal estimates for geometric reconstruction problems. IEEE Intl. Conf. Computer Vision, Beijing (2005)
Kuno, T.: A branch-and-bound algorithm for maximizing the sum of several linear ratios. J. Global Optim. 22(1), 155–174 (2002)
Lasserre, J.B.: Convergent SDP relaxations in polynomial optimization with sparsity. SIAM J. Optim. 17, 822–843 (2006)
Lasserre, J.B.: A semidefinite programming approach to the generalized problem of moments. Math. Program. 112, 65–92 (2008)
Lasserre, J.B.: Moments, Positive Polynomials and their Applications. Imperial College Press, London (2010)
Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. Emerg. Appl. Algebr. Geom. 149, 157–270 (2009)
Löfberg, J.: Yalmip : A toolbox for modeling and optimization in MATLAB. In: Proceedings of the CACSD Conference, Taipei (2004)
Pujol, J.C.F., Poli, R.: A highly efficient function optimization with genetic programming. Genetic and Evolutionary Computation Conference, Seattle (2004)
Putinar, M.: Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42, 969–984 (1993)
Schaible, S., Shi, J.: Fractional programming: the sum-of-ratios case. Optim. Methods Softw. 18(2), 219–229 (2003)
Schweighofer, M.: Optimization of polynomials on compact semialgebraic sets. SIAM J. Optim. 17(3), 805–825 (2005)
Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 12, 625–653 (1999)
Tawarmalani, M., Sahinidis, N.V.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103(2), 225–249 (2005)
Toh, K.C., Todd, M.J., Tutuncu, R.H.: Solving semidefinite-quadratic-linear programs using SDPT3. Math. Program. Ser. B 95, 189–217 (2003)
Waki, S., Kim, S., Kojima, M., Muramatsu, M.: Sums of squares and semidefinite programming relaxations for polynomial optimization problemswith structured sparsity. SIAM J. Optim. 17, 218–242 (2006)
Waki, H., Kim, S., Kojima, M., Muramatsu, M., Sugimoto, H.: SparsePOP: a sparse semidefinite programming relaxation of polynomial optimization problems. ACM Trans. Math. Softw. 35, 1–13 (2008)
Wang, C.F., Liu, S.Y., Shen, P.P.: Global optimization for sum of geometric fractional functions. Appl. Math. Comput. 216, 2263–2270 (2010)
Wu, W.-Y., Sheu, R.-L., Ilker, S.: Birbil. Solving the sum-of-ratios problem by a stochastic search algorithm. J. Global Optim. 42(1), 91–109 (2008)
Yamashita, M., Fujisawa, K., Nakata, K., Nakata, M., Fukuda, M., Kobayashi, K., Goto, K.: A high-performance software package for semidefinite programs: SDPA 7. Research Report B-460 Dept. of Mathematical and Computing Science, Tokyo Institute of Technology (2010)