Geodesic
On the quadratic fractional optimization with a strictly convex quadratic constraint
Kybernetika, Tome 51 (2015) no. 2, pp. 293-308 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

In this paper, we have studied the problem of minimizing the ratio of two indefinite quadratic functions subject to a strictly convex quadratic constraint. First utilizing the relationship between fractional and parametric programming problems due to Dinkelbach, we reformulate the fractional problem as a univariate equation. To find the root of the univariate equation, the generalized Newton method is utilized that requires solving a nonconvex quadratic optimization problem at each iteration. A key difficulty with this problem is its nonconvexity. Using Lagrange duality, we show that this problem can be solved by solving a convex univariate minimization problem. Attainment of the global optimality conditions is discussed. Our preliminary numerical experiments on several randomly generated test problems show that, the new approach is much faster in finding the global optimal solution than the known semidefinite relaxation approach, especially when solving large scale problems.
In this paper, we have studied the problem of minimizing the ratio of two indefinite quadratic functions subject to a strictly convex quadratic constraint. First utilizing the relationship between fractional and parametric programming problems due to Dinkelbach, we reformulate the fractional problem as a univariate equation. To find the root of the univariate equation, the generalized Newton method is utilized that requires solving a nonconvex quadratic optimization problem at each iteration. A key difficulty with this problem is its nonconvexity. Using Lagrange duality, we show that this problem can be solved by solving a convex univariate minimization problem. Attainment of the global optimality conditions is discussed. Our preliminary numerical experiments on several randomly generated test problems show that, the new approach is much faster in finding the global optimal solution than the known semidefinite relaxation approach, especially when solving large scale problems.
DOI : 10.14736/kyb-2015-2-0293
Classification : 90C20, 90C22, 90C26, 90C32
Keywords: fractional optimization; indefinite quadratic optimization; semidefinite relaxation; diagonalization; generalized Newton method 
@article{10_14736_kyb_2015_2_0293,
     author = {Salahi, Maziar and Fallahi, Saeed},
     title = {On the quadratic fractional optimization with a strictly convex quadratic constraint},
     journal = {Kybernetika},
     pages = {293--308},
     year = {2015},
     volume = {51},
     number = {2},
     doi = {10.14736/kyb-2015-2-0293},
     mrnumber = {3350563},
     zbl = {06487080},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2015-2-0293/}
}
TY  - JOUR
AU  - Salahi, Maziar
AU  - Fallahi, Saeed
TI  - On the quadratic fractional optimization with a strictly convex quadratic constraint
JO  - Kybernetika
PY  - 2015
SP  - 293
EP  - 308
VL  - 51
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2015-2-0293/
DO  - 10.14736/kyb-2015-2-0293
LA  - en
ID  - 10_14736_kyb_2015_2_0293
ER  - 
%0 Journal Article
%A Salahi, Maziar
%A Fallahi, Saeed
%T On the quadratic fractional optimization with a strictly convex quadratic constraint
%J Kybernetika
%D 2015
%P 293-308
%V 51
%N 2
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2015-2-0293/
%R 10.14736/kyb-2015-2-0293
%G en
%F 10_14736_kyb_2015_2_0293
Salahi, Maziar; Fallahi, Saeed. On the quadratic fractional optimization with a strictly convex quadratic constraint. Kybernetika, Tome 51 (2015) no. 2, pp. 293-308. doi: 10.14736/kyb-2015-2-0293

[1] Amaral, P., Judice, J., Sherali, H. D.: A reformulation-linearization-convexification algorithm for optimal correction of an inconsistent system of linear constraints. Comput. Oper. Res 35 (2008), 1494-1509. | DOI | MR | Zbl

[2] Bazaraa, M. S., Sherali, H. D., Shetty, C. M.: Nonlinear Programming. Wiley, New York 1993. | DOI | MR | Zbl

[3] Beck, A., Ben-Tal, A.: On the solution of the Tikhonov regularization of the regularized total least squares problem. SIAM J. Optim. 17 (2006), 98-118. | DOI | MR

[4] 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 (2006), 425-445. | DOI | MR | Zbl

[5] Beck, A., Teboulle, M.: On minimizing quadratically constrained ratio of two quadratic functions. J. Convex Anal. 17 (2010), 789-804. | MR | Zbl

[6] Beck, A., Teboulle, M.: A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid. Math. Program. 118 (2009), 13-35. | DOI | MR | Zbl

[7] Benson, H. P.: Fractional programming with convex quadratic forms and functions. Eur. J. Oper. Res. 173 (2006), 351-369. | DOI | MR | Zbl

[8] Benson, H. P.: Solving sum of ratios fractional programs via concave minimization. J. Optim. Theory Appl. 135 (2007), 1-17. | DOI | MR | Zbl

[9] Benson, H. P.: A simplicial branch and bound duality-bounds algorithm for the linear sum-of-ratios problem. Eur. J. Oper. Res. 182 (2007), 597-611. | DOI | MR | Zbl

[10] Dinkelbach, W.: On Nonlinear Fractional Programming. Manage Sci. 13 (1967), 492-498. | DOI | MR | Zbl

[11] Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 2.0 beta. 2013. DOI 

[12] Laub, A. J.: Matrix Analysis for Scientists and Engineers. SIAM 2005. | DOI | MR | Zbl

[13] Lo, A. W., MacKinlay, A. C.: Maximizing predictability in the stock and bond markets. Macroecon. Dyn. 1 (1997), 102-134. | DOI | Zbl

[14] Ohlson, J. A., Ziemba, W. T.: Optimal portfolio policies for an investor with a power utility function facing a log normal securities market. J. Financ. Quant. Anal. 11 (1976), 57-71. | DOI

[15] Pong, T. K., Wolkowicz, H.: The generalized trust region subproblem. Comput. Optim. Appl. 58 (2014), 273-322. | DOI | MR

[16] Shen, P. P., Yuan, G. X.: Global optimization for the sum of generalized polynomial fractional functions. Math. Methods Oper. Res. 65 (2007), 445-459. | DOI | MR | Zbl

[17] Sturm, J. F., Zhang, S.: On cones of nonnegative quadratic functions. Math. Oper. Res. 28 (2003), 246-267. | DOI | MR | Zbl

[18] Tuy, H., Trach, P. T., Konno, H.: Optimization of polynomial fractional functions. J. Glob. Optim. 29 (2004), 19-44. | DOI | MR

[19] Yamamoto, R., Konno, H.: An efficient algorithm for solving convex-convex quadratic fractional programs. J. Optim. Theory Appl. 133 (2007), 241-255. | DOI | MR | Zbl

[20] Ye, Y., Zhang, Sh.: New results on quadratic minimization. SIAM J. Optim. 14 (2003), 245-267. | DOI | MR | Zbl

[21] Zhang, A., Hayashi, Sh.: Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints. Numer. Algebra Control. Optim. 1 (2011), 83-98. | DOI | MR | Zbl

[22] Zheng, X. J., Sun, X. L., Li, D., Xu, Y. F.: On zero duality gap in nonconvex quadratic programming problems. J. Glob. Optim. 52 (2012), 229-242. | DOI | MR | Zbl

Cité par Sources :