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.
Efficient local search procedures for quadratic fractional programming problems / Consolini, L.; Locatelli, M.; Wang, J.; Xia, Y.. - In: COMPUTATIONAL OPTIMIZATION AND APPLICATIONS. - ISSN 0926-6003. - 76:1(2020), pp. 201-232. [10.1007/s10589-020-00175-1]
Efficient local search procedures for quadratic fractional programming problems
Consolini L.;Locatelli M.
;
2020-01-01
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.