×

zbMATH — the first resource for mathematics

Minimizing the sum of many rational functions. (English) Zbl 1364.90268
Summary: 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.
Reviewer: Reviewer (Berlin)

MSC:
90C26 Nonconvex programming, global optimization
90C22 Semidefinite programming
46N10 Applications of functional analysis in optimization, convex analysis, mathematical programming, economics
65K05 Numerical mathematical programming methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ali, MM; Khompatraporn, C; Zabinsky, ZB, A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems, J. Global Optim., 31, 635-672, (2005) · Zbl 1093.90028
[2] Benson, HP, Global optimization algorithm for the nonlinear sum of ratios problem, J. Optim. Theory Appl., 112, 1-29, (2002) · Zbl 1049.90062
[3] Benson, HP, Using concave envelopes to globally solve the nonlinear sum of ratios problems, J. Global Optim., 22, 343-364, (2002) · Zbl 1045.90069
[4] Benson, S.J., Ye, Y.: DSDP5 user guide—software for semidefinite programming. Mathematics and Computer Science Division, Argonne National Laboratory (2005) · Zbl 1070.90115
[5] 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) · Zbl 1114.90098
[6] Borchers, B, CSDP, a C library for semidefinite programming, Optim. Methods Softw., 11, 613-623, (1999) · Zbl 0973.90524
[7] Curto, RE; Fialkow, LA, Recursiveness, positivity, and truncated moment problems, Houston J. Math., 17, 603-635, (1991) · Zbl 0757.44006
[8] Czyzyk, J; Mesnier, M; Moré, J, The NEOS server, IEEE J. Comput. Sci. Eng., 5, 68-75, (1998)
[9] Freund, RW; Jarre, F, Solving the sum-of-ratios problem by an interior-point method, J. Global Optim., 19, 83-102, (2001) · Zbl 1168.90644
[10] Hartley, R; Kahl, F; Olsson, C; Seo, Y, Verifying global minima for L2 minimization problems in multiple view geometry, Int. J. Comput. Vis., 101, 288-304, (2013) · Zbl 1259.68197
[11] Henrion, D; Lasserre, JB, Gloptipoly: global optimization over polynomials with Matlab and sedumi, ACM Trans. Math. Softw., 29, 165-194, (2003) · Zbl 1070.65549
[12] Henrion, D; Lasserre, JB; Löfberg, J, Gloptipoly 3: moments, optimization and semidefinite programming, Optim. Methods Softw., 24, 761-779, (2009) · Zbl 1178.90277
[13] Jibetean, D; Klerk, E, Global optimization of rational functions: a semidefinite programming approach, Math. Program., 106, 93-109, (2006) · Zbl 1134.90460
[14] Kahl, F; Agarwal, S; Chandraker, M; Kriegman, D; Belongie, S, Practical global optimization for multiview geometry, Int. J. Comput. Vis., 79, 271-284, (2008)
[15] Kahl, F., Henrion, D.: Globally optimal estimates for geometric reconstruction problems. IEEE Intl. Conf. Computer Vision, Beijing (2005)
[16] Kuno, T, A branch-and-bound algorithm for maximizing the sum of several linear ratios, J. Global Optim., 22, 155-174, (2002) · Zbl 1045.90071
[17] Lasserre, JB, Convergent SDP relaxations in polynomial optimization with sparsity, SIAM J. Optim., 17, 822-843, (2006) · Zbl 1119.90036
[18] Lasserre, JB, A semidefinite programming approach to the generalized problem of moments, Math. Program., 112, 65-92, (2008) · Zbl 1145.90049
[19] Lasserre, J.B.: Moments, Positive Polynomials and their Applications. Imperial College Press, London (2010) · Zbl 1211.90007
[20] Laurent, M, Sums of squares, moment matrices and optimization over polynomials, Emerg. Appl. Algebr. Geom., 149, 157-270, (2009) · Zbl 1163.13021
[21] Löfberg, J.: Yalmip : A toolbox for modeling and optimization in MATLAB. In: Proceedings of the CACSD Conference, Taipei (2004) · Zbl 1045.90069
[22] Pujol, J.C.F., Poli, R.: A highly efficient function optimization with genetic programming. Genetic and Evolutionary Computation Conference, Seattle (2004)
[23] Putinar, M, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., 42, 969-984, (1993) · Zbl 0796.12002
[24] Schaible, S; Shi, J, Fractional programming: the sum-of-ratios case, Optim. Methods Softw., 18, 219-229, (2003) · Zbl 1070.90115
[25] Schweighofer, M, Optimization of polynomials on compact semialgebraic sets, SIAM J. Optim., 17, 805-825, (2005) · Zbl 1114.90098
[26] Sturm, JF, Using sedumi 1.02, a MATLAB toolbox for optimization over symmetric cones, Optim. Methods Softw., 12, 625-653, (1999) · Zbl 0973.90526
[27] Tawarmalani, M; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047
[28] Toh, KC; Todd, MJ; Tutuncu, RH, Solving semidefinite-quadratic-linear programs using SDPT3, Math. Program. Ser. B, 95, 189-217, (2003) · Zbl 1030.90082
[29] 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) · Zbl 1109.65058
[30] 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)
[31] Wang, CF; Liu, SY; Shen, PP, Global optimization for sum of geometric fractional functions, Appl. Math. Comput., 216, 2263-2270, (2010) · Zbl 1195.65076
[32] Wu, W-Y; Sheu, R-L; Ilker, S, Birbil. solving the sum-of-ratios problem by a stochastic search algorithm, J. Global Optim., 42, 91-109, (2008) · Zbl 1193.90201
[33] 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) · Zbl 0973.90526
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.