×

zbMATH — the first resource for mathematics

Efficient local search procedures for quadratic fractional programming problems. (English) Zbl 1433.90167
Summary: The problem of minimizing the sum of a convex quadratic function and the ratio of two quadratic functions can be reformulated as a Celis-Dennis-Tapia (CDT) problem and, thus, according to some recent results, can be polynomially solved. However, the degree of the known polynomial approaches for these problems is fairly large and that justifies the search for efficient local search procedures. In this paper the CDT reformulation of the problem is exploited to define a local search algorithm. On the theoretical side, its convergence to a stationary point is proved. On the practical side it is shown, through different numerical experiments, that the main cost of the algorithm is a single Schur decomposition to be performed during the initialization phase. The theoretical and practical results for this algorithm are further strengthened in a special case.
MSC:
90C32 Fractional programming
65K05 Numerical mathematical programming methods
90C20 Quadratic programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Beck, A.; Ben-Tal, A., On the solution of the Tikhonov regularization of the total least squares problem, SIAM J. Optim., 17, 1, 98-118 (2006) · Zbl 1112.65034
[2] Beck, A.; Ben-Tal, A.; Teboulle, M., Finding a global optimal solution for a quadratically constrained fractional quadratic problem with applications to the regularized total least squares, SIAM J. Matrix Anal. Appl., 28, 2, 425-445 (2006) · Zbl 1115.65065
[3] Beck, A.; Teboulle, M., A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid, Math. Program., 118, 13-35 (2009) · Zbl 1176.90451
[4] Beck, A.; Teboulle, M., On minimizing quadratically constrained ratio of two quadratic functions, J. Convex Anal., 17, 789-804 (2010) · Zbl 1213.90239
[5] Benson, HP, Global optimization of nonlinear sums of ratios, J. Math. Anal. Appl., 263, 301-315 (2001) · Zbl 1006.90064
[6] Benson, HP, Global optimization algorithm for the nonlinear sum of ratios problem, J. Optim. Theory Appl., 112, 1-29 (2002) · Zbl 1049.90062
[7] Benson, HP, Using concave envelopes to globally solve the nonlinear sum of ratios problems, J. Glob. Optim., 22, 343-364 (2002) · Zbl 1045.90069
[8] Benson, HP, Solving sum of ratios fractional programs via concave minimization, J. Optim. Theory Appl., 135, 1-17 (2007) · Zbl 1145.90089
[9] Ben-Tal, A.; den Hertog, D., Hidden conic quadratic representation of some nonconvex quadratic optimization problems, Math. Program., 143, 1-29 (2014) · Zbl 1295.90036
[10] Bienstock, D., A note on polynomial solvability of the CDT problem, SIAM J. Optim., 26, 1, 488-498 (2016) · Zbl 1382.90083
[11] Celis, MR; Dennis, JE; Tapia, RA; Boggs, PT; Byrd, RH; Schnabel, RB, A trust region strategy for nonlinear equality constrained optimization, Numerical Optimization, 71-82 (1985), Philadelphia: SIAM, Philadelphia
[12] Consolini, L.; Locatelli, M., On the complexity of quadratic programming with two quadratic constraints, Math. Program., 164, 1-2, 91-128 (2017) · Zbl 1396.90055
[13] Depetrini, D.; Locatelli, M., Approximation of linear fractional/multiplicative problems, Math. Program., 128, 437-443 (2011) · Zbl 1218.90160
[14] Dinkelbach, W., On nonlinear fractional programming, Manag. Sci., 13, 492-498 (1967) · Zbl 0152.18402
[15] Fierro, RD; Golub, GH; Hansen, PC; O’Leary, DP, Regularization by truncated total least squares, SIAM J. Sci. Comput., 18, 4, 1223-1241 (1997) · Zbl 0891.65040
[16] Freund, RW; Jarre, F., Solving the sum-of-ratios problem by an interior-point method, J. Glob. Optim., 19, 83-102 (2001) · Zbl 1168.90644
[17] Golub, GH; Hansen, PC; O’Leary, DP, Tikhonov regularization and total least squares, SIAM J. Numer. Anal., 21, 185-194 (1999) · Zbl 0945.65042
[18] Hansen, PC; O’Leary, DP, The use of the L-curve in the regularization of discrete ill-posed problems, SIAM J. Sci. Comput., 14, 6, 1487-1503 (1993) · Zbl 0789.65030
[19] Hansen, PC, Regularization tools: a Matlab package for analysis and solution of discrete ill-posed problems, Numer. Algorithms, 6, 1, 1-35 (1994) · Zbl 0789.65029
[20] Hansen, PC, Deconvolution and regularization with Toeplitz matrices, Numer. Algorithms, 29, 323-378 (2002) · Zbl 1002.65145
[21] Konno, H.; Fukaishi, K., A branch and bound algorithm for solving low rank linear multiplicative and fractional programming problems, J. Glob. Optim., 18, 283-299 (2000) · Zbl 0971.90065
[22] Kuno, T., A branch-and-bound algorithm for maximizing the sum of several linear ratios, J. Glob. Optim., 22, 155-174 (2002) · Zbl 1045.90071
[23] Lampe, J.; Voss, H., Large-scale Tikhonov regularization of total least squares, J. Comput. Appl. Math., 238, 95-108 (2013) · Zbl 1254.65052
[24] Locatelli, M., Alternative branching rules for some nonconvex problems, Optim. Methods Softw., 30, 2, 365-378 (2015) · Zbl 1326.90066
[25] Lu, S.; Pereverzev, SV; Tautenhahn, U., Regularized total least squares: computational aspects and error bounds, SIAM J. Matrix Anal. Appl., 31, 3, 918-941 (2009) · Zbl 1198.65094
[26] Matsui, T., NP-hardness of linear multiplicative programming and related problems, J. Glob. Optim., 9, 113-119 (2006) · Zbl 0868.90111
[27] Mittal, S.; Schulz, AS, An FPTAS for optimizing a class of low-rank functions over a polytope, Math. Program., 141, 103-120 (2013) · Zbl 1280.90096
[28] Nguyen, V-B; Sheu, R-L; Xia, Y., An SDP approach for quadratic fractional problems with a two-sided quadratic constraint, Optim. Methods Softw., 31, 4, 701-719 (2016) · Zbl 1385.90027
[29] Sakaue, S.; Nakatsukasa, Y.; Takeda, A.; Iwata, S., Solving generalized CDT problems via two-parameter eigenvalues, SIAM J. Optim., 26, 3, 1669-1694 (2016) · Zbl 1346.49050
[30] Schaible, S.; Horst, R.; Pardalos, P., Fractional programming, Handbook of Global Optimization (1995), Berlin: Kluwer Academic Publishers, Berlin
[31] Schaible, S.; Shi, J., Fractional programming: the sum-of-ratios case, Optim. Methods Softw., 18, 219-229 (2003) · Zbl 1070.90115
[32] Sima, DM; Van Huffel, S.; Golub, GH, Regularied total least squares based on quadratic eigenvalue problem solvers, BIT Numer. Math., 44, 793-812 (2004) · Zbl 1079.65048
[33] Uhlig, F., Definite and semidefinite matrices in a real symmetric matrix pencil, Pac. J. Math., 49, 561-568 (1973) · Zbl 0291.15013
[34] Wang, Y-J; Zhang, K-C, Global optimization of nonlinear sum of ratios problem, Appl. Math. Comput., 158, 2, 319-330 (2004) · Zbl 1065.65081
[35] Yang, M.; Xia, Y.; Wang, J.; Peng, J., Efficiently solving total least squares with Tikhonov identical regularization, Comput. Optim. Appl., 70, 571-592 (2018) · Zbl 1391.90498
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.