Kybernetika 51 no. 2, 293-308, 2015

On the quadratic fractional optimization with a strictly convex quadratic constraint

Maziar Salahi and Saeed FallahiDOI: 10.14736/kyb-2015-2-0293

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.

Keywords:

fractional optimization, indefinite quadratic optimization, semidefinite relaxation, diagonalization, generalized Newton method

Classification:

90C32, 90C26, 90C22

paper.pdf

References:

  1. P. Amaral, J. Judice and H. D. Sherali: A reformulation-linearization-convexification algorithm for optimal correction of an inconsistent system of linear constraints. Comput. Oper. Res 35 (2008), 1494-1509.   DOI:10.1016/j.cor.2006.08.007
  2. M. S. Bazaraa, H. D. Sherali and C. M. Shetty: Nonlinear Programming. Wiley, New York 1993.   DOI:10.1002/0471787779
  3. A. Beck and A. Ben-Tal: On the solution of the Tikhonov regularization of the regularized total least squares problem. SIAM J. Optim. 17 (2006), 98-118.   DOI:10.1137/050624418
  4. A. Beck, A. Ben-Tal and M. Teboulle: 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:10.1137/040616851
  5. A. Beck and M. Teboulle: On minimizing quadratically constrained ratio of two quadratic functions. J. Convex Anal. 17 (2010), 789-804.   CrossRef
  6. A. Beck and M. Teboulle: A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid. Math. Program. 118 (2009), 13-35.   DOI:10.1007/s10107-007-0181-x
  7. H. P. Benson: Fractional programming with convex quadratic forms and functions. Eur. J. Oper. Res. 173 (2006), 351-369.   DOI:10.1016/j.ejor.2005.02.069
  8. H. P. Benson: Solving sum of ratios fractional programs via concave minimization. J. Optim. Theory Appl. 135 (2007), 1-17.   DOI:10.1007/s10957-007-9199-8
  9. H. P. Benson: A simplicial branch and bound duality-bounds algorithm for the linear sum-of-ratios problem. Eur. J. Oper. Res. 182 (2007), 597-611.   DOI:10.1016/j.ejor.2006.08.036
  10. W. Dinkelbach: On Nonlinear Fractional Programming. Manage Sci. 13 (1967), 492-498.   DOI:10.1287/mnsc.13.7.492
  11. M. Grant and S. Boyd: CVX: Matlab software for disciplined convex programming, version 2.0 beta. 2013.   http://cvxr.com/cvx
  12. A. J. Laub: Matrix Analysis for Scientists and Engineers. SIAM 2005.   DOI:10.1137/1.9780898717907
  13. A. W. Lo and A. C. MacKinlay: Maximizing predictability in the stock and bond markets. Macroecon. Dyn. 1 (1997), 102-134.   DOI:10.1017/s1365100597002046
  14. J. A. Ohlson and W. T. Ziemba: 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:10.2307/2330229
  15. T. K. Pong and H. Wolkowicz: The generalized trust region subproblem. Comput. Optim. Appl. 58 (2014), 273-322.   DOI:10.1007/s10589-013-9635-7
  16. P. P. Shen and G. X. Yuan: Global optimization for the sum of generalized polynomial fractional functions. Math. Methods Oper. Res. 65 (2007), 445-459.   DOI:10.1007/s00186-006-0130-0
  17. J. F. Sturm and S. Zhang: On cones of nonnegative quadratic functions. Math. Oper. Res. 28 (2003), 246-267.   DOI:10.1287/moor.28.2.246.14485
  18. H. Tuy, P. T. Trach and H. Konno: Optimization of polynomial fractional functions. J. Glob. Optim. 29 (2004), 19-44.   DOI:10.1023/b:jogo.0000035016.74398.e6
  19. R. Yamamoto and H. Konno: An efficient algorithm for solving convex-convex quadratic fractional programs. J. Optim. Theory Appl. 133 (2007), 241-255.   DOI:10.1007/s10957-007-9188-y
  20. Y. Ye and Sh. Zhang: New results on quadratic minimization. SIAM J. Optim. 14 (2003), 245-267.   DOI:10.1137/s105262340139001x
  21. A. Zhang and Sh. Hayashi: Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints. Numer. Algebra Control. Optim. 1 (2011), 83-98.   DOI:10.3934/naco.2011.1.83
  22. X. J. Zheng, X. L. Sun, D. Li and Y. F. Xu: On zero duality gap in nonconvex quadratic programming problems. J. Glob. Optim. 52 (2012), 229-242.   DOI:10.1007/s10898-011-9660-y