On the quadratic fractional optimization with a strictly convex quadratic constraint

Maziar Salahi; Saeed Fallahi

Kybernetika (2015)

  • Volume: 51, Issue: 2, page 293-308
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Salahi, Maziar, and Fallahi, Saeed. "On the quadratic fractional optimization with a strictly convex quadratic constraint." Kybernetika 51.2 (2015): 293-308. <http://eudml.org/doc/270116>.

@article{Salahi2015,
abstract = {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.},
author = {Salahi, Maziar, Fallahi, Saeed},
journal = {Kybernetika},
keywords = {fractional optimization; indefinite quadratic optimization; semidefinite relaxation; diagonalization; generalized Newton method; fractional optimization; indefinite quadratic optimization; semidefinite relaxation; diagonalization; generalized Newton method},
language = {eng},
number = {2},
pages = {293-308},
publisher = {Institute of Information Theory and Automation AS CR},
title = {On the quadratic fractional optimization with a strictly convex quadratic constraint},
url = {http://eudml.org/doc/270116},
volume = {51},
year = {2015},
}

TY - JOUR
AU - Salahi, Maziar
AU - Fallahi, Saeed
TI - On the quadratic fractional optimization with a strictly convex quadratic constraint
JO - Kybernetika
PY - 2015
PB - Institute of Information Theory and Automation AS CR
VL - 51
IS - 2
SP - 293
EP - 308
AB - 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.
LA - eng
KW - fractional optimization; indefinite quadratic optimization; semidefinite relaxation; diagonalization; generalized Newton method; fractional optimization; indefinite quadratic optimization; semidefinite relaxation; diagonalization; generalized Newton method
UR - http://eudml.org/doc/270116
ER -

References

top
  1. Amaral, P., Judice, J., Sherali, H. D., 10.1016/j.cor.2006.08.007, Comput. Oper. Res 35 (2008), 1494-1509. Zbl1278.90371MR2578321DOI10.1016/j.cor.2006.08.007
  2. Bazaraa, M. S., Sherali, H. D., Shetty, C. M., 10.1002/0471787779, Wiley, New York 1993. Zbl1140.90040MR2218478DOI10.1002/0471787779
  3. Beck, A., Ben-Tal, A., 10.1137/050624418, SIAM J. Optim. 17 (2006), 98-118. MR2219146DOI10.1137/050624418
  4. Beck, A., Ben-Tal, A., Teboulle, M., 10.1137/040616851, SIAM J. Matrix Anal. Appl. 28 (2006), 425-445. Zbl1115.65065MR2255337DOI10.1137/040616851
  5. Beck, A., Teboulle, M., On minimizing quadratically constrained ratio of two quadratic functions., J. Convex Anal. 17 (2010), 789-804. Zbl1213.90239MR2731279
  6. Beck, A., Teboulle, M., 10.1007/s10107-007-0181-x, Math. Program. 118 (2009), 13-35. Zbl1176.90451MR2470883DOI10.1007/s10107-007-0181-x
  7. Benson, H. P., 10.1016/j.ejor.2005.02.069, Eur. J. Oper. Res. 173 (2006), 351-369. Zbl1113.90122MR2230179DOI10.1016/j.ejor.2005.02.069
  8. Benson, H. P., 10.1007/s10957-007-9199-8, J. Optim. Theory Appl. 135 (2007), 1-17. Zbl1145.90089MR2342650DOI10.1007/s10957-007-9199-8
  9. Benson, H. P., 10.1016/j.ejor.2006.08.036, Eur. J. Oper. Res. 182 (2007), 597-611. Zbl1121.90102MR2324550DOI10.1016/j.ejor.2006.08.036
  10. Dinkelbach, W., 10.1287/mnsc.13.7.492, Manage Sci. 13 (1967), 492-498. Zbl0152.18402MR0242488DOI10.1287/mnsc.13.7.492
  11. Grant, M., Boyd, S., , 2013. DOI
  12. Laub, A. J., 10.1137/1.9780898717907, SIAM 2005. Zbl1077.15001MR2128817DOI10.1137/1.9780898717907
  13. Lo, A. W., MacKinlay, A. C., 10.1017/s1365100597002046, Macroecon. Dyn. 1 (1997), 102-134. Zbl0915.90025DOI10.1017/s1365100597002046
  14. Ohlson, J. A., Ziemba, W. T., 10.2307/2330229, J. Financ. Quant. Anal. 11 (1976), 57-71. DOI10.2307/2330229
  15. Pong, T. K., Wolkowicz, H., 10.1007/s10589-013-9635-7, Comput. Optim. Appl. 58 (2014), 273-322. MR3201963DOI10.1007/s10589-013-9635-7
  16. Shen, P. P., Yuan, G. X., 10.1007/s00186-006-0130-0, Math. Methods Oper. Res. 65 (2007), 445-459. Zbl1180.90331MR2314288DOI10.1007/s00186-006-0130-0
  17. Sturm, J. F., Zhang, S., 10.1287/moor.28.2.246.14485, Math. Oper. Res. 28 (2003), 246-267. Zbl1082.90086MR1980662DOI10.1287/moor.28.2.246.14485
  18. Tuy, H., Trach, P. T., Konno, H., 10.1023/b:jogo.0000035016.74398.e6, J. Glob. Optim. 29 (2004), 19-44. MR2077884DOI10.1023/b:jogo.0000035016.74398.e6
  19. Yamamoto, R., Konno, H., 10.1007/s10957-007-9188-y, J. Optim. Theory Appl. 133 (2007), 241-255. Zbl1151.90560MR2335266DOI10.1007/s10957-007-9188-y
  20. Ye, Y., Zhang, Sh., 10.1137/s105262340139001x, SIAM J. Optim. 14 (2003), 245-267. Zbl1043.90064MR2005943DOI10.1137/s105262340139001x
  21. Zhang, A., Hayashi, Sh., 10.3934/naco.2011.1.83, Numer. Algebra Control. Optim. 1 (2011), 83-98. Zbl1219.90169MR2806295DOI10.3934/naco.2011.1.83
  22. Zheng, X. J., Sun, X. L., Li, D., Xu, Y. F., 10.1007/s10898-011-9660-y, J. Glob. Optim. 52 (2012), 229-242. Zbl1266.90151MR2886307DOI10.1007/s10898-011-9660-y

NotesEmbed ?

top

You must be logged in to post comments.