Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
fractional optimization; indefinite quadratic optimization; semidefinite relaxation; diagonalization; generalized Newton method
fractional optimization; indefinite quadratic optimization; semidefinite relaxation; diagonalization; generalized Newton method
Summary:
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.
References:
[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 10.1016/j.cor.2006.08.007 | MR 2578321 | Zbl 1278.90371
[2] Bazaraa, M. S., Sherali, H. D., Shetty, C. M.: Nonlinear Programming. Wiley, New York 1993. DOI 10.1002/0471787779 | MR 2218478 | Zbl 1140.90040
[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 10.1137/050624418 | MR 2219146
[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 10.1137/040616851 | MR 2255337 | Zbl 1115.65065
[5] Beck, A., Teboulle, M.: On minimizing quadratically constrained ratio of two quadratic functions. J. Convex Anal. 17 (2010), 789-804. MR 2731279 | Zbl 1213.90239
[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 10.1007/s10107-007-0181-x | MR 2470883 | Zbl 1176.90451
[7] Benson, H. P.: Fractional programming with convex quadratic forms and functions. Eur. J. Oper. Res. 173 (2006), 351-369. DOI 10.1016/j.ejor.2005.02.069 | MR 2230179 | Zbl 1113.90122
[8] Benson, H. P.: Solving sum of ratios fractional programs via concave minimization. J. Optim. Theory Appl. 135 (2007), 1-17. DOI 10.1007/s10957-007-9199-8 | MR 2342650 | Zbl 1145.90089
[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 10.1016/j.ejor.2006.08.036 | MR 2324550 | Zbl 1121.90102
[10] Dinkelbach, W.: On Nonlinear Fractional Programming. Manage Sci. 13 (1967), 492-498. DOI 10.1287/mnsc.13.7.492 | MR 0242488 | Zbl 0152.18402
[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 10.1137/1.9780898717907 | MR 2128817 | Zbl 1077.15001
[13] Lo, A. W., MacKinlay, A. C.: Maximizing predictability in the stock and bond markets. Macroecon. Dyn. 1 (1997), 102-134. DOI 10.1017/s1365100597002046 | Zbl 0915.90025
[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 10.2307/2330229
[15] Pong, T. K., Wolkowicz, H.: The generalized trust region subproblem. Comput. Optim. Appl. 58 (2014), 273-322. DOI 10.1007/s10589-013-9635-7 | MR 3201963
[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 10.1007/s00186-006-0130-0 | MR 2314288 | Zbl 1180.90331
[17] Sturm, J. F., Zhang, S.: On cones of nonnegative quadratic functions. Math. Oper. Res. 28 (2003), 246-267. DOI 10.1287/moor.28.2.246.14485 | MR 1980662 | Zbl 1082.90086
[18] Tuy, H., Trach, P. T., Konno, H.: Optimization of polynomial fractional functions. J. Glob. Optim. 29 (2004), 19-44. DOI 10.1023/b:jogo.0000035016.74398.e6 | MR 2077884
[19] Yamamoto, R., Konno, H.: 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 | MR 2335266 | Zbl 1151.90560
[20] Ye, Y., Zhang, Sh.: New results on quadratic minimization. SIAM J. Optim. 14 (2003), 245-267. DOI 10.1137/s105262340139001x | MR 2005943 | Zbl 1043.90064
[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 10.3934/naco.2011.1.83 | MR 2806295 | Zbl 1219.90169
[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 10.1007/s10898-011-9660-y | MR 2886307 | Zbl 1266.90151
Search
Partner of
