| Title:
|
On the quadratic fractional optimization with a strictly convex quadratic constraint (English) |
| Author:
|
Salahi, Maziar |
| Author:
|
Fallahi, Saeed |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
51 |
| Issue:
|
2 |
| Year:
|
2015 |
| Pages:
|
293-308 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
fractional optimization |
| Keyword:
|
indefinite quadratic optimization |
| Keyword:
|
semidefinite relaxation |
| Keyword:
|
diagonalization |
| Keyword:
|
generalized Newton method |
| MSC:
|
90C20 |
| MSC:
|
90C22 |
| MSC:
|
90C26 |
| MSC:
|
90C32 |
| idZBL:
|
Zbl 06487080 |
| idMR:
|
MR3350563 |
| DOI:
|
10.14736/kyb-2015-2-0293 |
| . |
| Date available:
|
2015-06-19T15:23:52Z |
| Last updated:
|
2016-01-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/144299 |
| . |
| Reference:
|
[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. Zbl 1278.90371, MR 2578321, 10.1016/j.cor.2006.08.007 |
| Reference:
|
[2] Bazaraa, M. S., Sherali, H. D., Shetty, C. M.: Nonlinear Programming..Wiley, New York 1993. Zbl 1140.90040, MR 2218478, 10.1002/0471787779 |
| Reference:
|
[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. MR 2219146, 10.1137/050624418 |
| Reference:
|
[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. Zbl 1115.65065, MR 2255337, 10.1137/040616851 |
| Reference:
|
[5] Beck, A., Teboulle, M.: On minimizing quadratically constrained ratio of two quadratic functions..J. Convex Anal. 17 (2010), 789-804. Zbl 1213.90239, MR 2731279 |
| Reference:
|
[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. Zbl 1176.90451, MR 2470883, 10.1007/s10107-007-0181-x |
| Reference:
|
[7] Benson, H. P.: Fractional programming with convex quadratic forms and functions..Eur. J. Oper. Res. 173 (2006), 351-369. Zbl 1113.90122, MR 2230179, 10.1016/j.ejor.2005.02.069 |
| Reference:
|
[8] Benson, H. P.: Solving sum of ratios fractional programs via concave minimization..J. Optim. Theory Appl. 135 (2007), 1-17. Zbl 1145.90089, MR 2342650, 10.1007/s10957-007-9199-8 |
| Reference:
|
[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. Zbl 1121.90102, MR 2324550, 10.1016/j.ejor.2006.08.036 |
| Reference:
|
[10] Dinkelbach, W.: On Nonlinear Fractional Programming..Manage Sci. 13 (1967), 492-498. Zbl 0152.18402, MR 0242488, 10.1287/mnsc.13.7.492 |
| Reference:
|
[11] Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 2.0 beta..2013. |
| Reference:
|
[12] Laub, A. J.: Matrix Analysis for Scientists and Engineers..SIAM 2005. Zbl 1077.15001, MR 2128817, 10.1137/1.9780898717907 |
| Reference:
|
[13] Lo, A. W., MacKinlay, A. C.: Maximizing predictability in the stock and bond markets..Macroecon. Dyn. 1 (1997), 102-134. Zbl 0915.90025, 10.1017/s1365100597002046 |
| Reference:
|
[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. 10.2307/2330229 |
| Reference:
|
[15] Pong, T. K., Wolkowicz, H.: The generalized trust region subproblem..Comput. Optim. Appl. 58 (2014), 273-322. MR 3201963, 10.1007/s10589-013-9635-7 |
| Reference:
|
[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. Zbl 1180.90331, MR 2314288, 10.1007/s00186-006-0130-0 |
| Reference:
|
[17] Sturm, J. F., Zhang, S.: On cones of nonnegative quadratic functions..Math. Oper. Res. 28 (2003), 246-267. Zbl 1082.90086, MR 1980662, 10.1287/moor.28.2.246.14485 |
| Reference:
|
[18] Tuy, H., Trach, P. T., Konno, H.: Optimization of polynomial fractional functions..J. Glob. Optim. 29 (2004), 19-44. MR 2077884, 10.1023/b:jogo.0000035016.74398.e6 |
| Reference:
|
[19] Yamamoto, R., Konno, H.: An efficient algorithm for solving convex-convex quadratic fractional programs..J. Optim. Theory Appl. 133 (2007), 241-255. Zbl 1151.90560, MR 2335266, 10.1007/s10957-007-9188-y |
| Reference:
|
[20] Ye, Y., Zhang, Sh.: New results on quadratic minimization..SIAM J. Optim. 14 (2003), 245-267. Zbl 1043.90064, MR 2005943, 10.1137/s105262340139001x |
| Reference:
|
[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. Zbl 1219.90169, MR 2806295, 10.3934/naco.2011.1.83 |
| Reference:
|
[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. Zbl 1266.90151, MR 2886307, 10.1007/s10898-011-9660-y |
| . |
