Maximizing the sum of a generalized Rayleigh quotient and another Rayleigh quotient on the unit sphere via semidefinite programming

详细信息    查看全文

• 作者：Van-Bong Nguyen ; Ruey-Lin Sheu ; Yong Xia
• 关键词：Fractional programming ; (Generalized) Rayleigh quotient ; Quadratically constrained quadratic programming ; S ; Lemma ; Semidefinite programming ; Quadratic fit line search ; 90C22 ; 90C25
• 刊名：Journal of Global Optimization
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：64
• 期：2
• 页码：399-416
• 全文大小：595 KB
• 参考文献：1.Ai, W., Zhang, S.Z.: Strong duality for the CDT subproblem: a necessary and sufficient condition. SIAM J. Optim. 19(4), 1735–1756 (2009)CrossRef MathSciNet
  2.Antoniou, A., Lu, W.S.: Practical Optimization: Algorithms and Engineering Applications. Springer, Berlin (2007)
  3.Bazaraa, M.S., Sherali, H.D., Shetty, C.M.: Nonliear Programming: Theory and Algorithms, 3rd edn. Wiley, Hoboken (2006)CrossRef
  4.Benson, H.P.: Global optimization algorithm for the nonlinear sum of ratios problem. J. Optim. Theor. Appl. 112, 1–29 (2002)CrossRef MathSciNet
  5.Benson, H.P.: Using concave envelopes to globally solve the nonlinear sum of ratios problems. J. Glob. Optim. 22, 343–364 (2002)CrossRef MathSciNet
  6.Benson, H.P.: On the global optimization of sum of linear fractional functions over a convex set. J. Optim. Theory Appl. 121, 19–39 (2004)CrossRef MathSciNet
  7.Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization. MPS-SIAM Series on Optimization (2001)
  8.Ben-Tal, A., Teboulle, M.: Hidden convexity in some nonconvex quadratically constrained quadratic programming. Math. Program. 72, 51–63 (1996)MathSciNet
  9.Brickman, L.: On the field of values of a matrix. Proc. Am. Math. Soc. 12, 61–66 (1961)CrossRef MathSciNet
  10.Craven, B.D.: Fractional Programming. Sigma Series in Applied Mathematics, vol. 4. Heldermann Verlag, Berlin (1988)
  11.Dundar, M.M., Fung, G., Bi, J., Sandilya, S. Rao, B.: Sparse Fisher discriminant analysis for computer aided detection. In Proceedings of SIAM International Conference on Data Mining (2005)
  12.Eberhard, A., Hadjisavvas, N., Dinh, L.T.: Generalized Convexity, Generalized Monotonicity and Application: Proceedings of the 7th International Symposium On Generalized Convexity and Generalized Monotonicity, Nonconvex Optimization and its Applications, vol. 77. Springer (2005)
  13.Fang, S.C., Gao, D.Y., Sheu, R.L., Xing, W.: Global optimization for a class of fractional programming problems. J. Glob. Optim. 45(3), 337–353 (2009)CrossRef MathSciNet
  14.Freund, R.W., Jarre, F.: Solving the sum-of-ratios problem by an interior-point method. J. Glob. Optim. 19, 83–102 (2001)CrossRef MathSciNet
  15.Fung, E., Ng, M.K.: On sparse Fisher discriminant method for microarray data analysis. Bioinformation 2, 230–234 (2007)CrossRef
  16.Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 1. 21 Web. http://​cvxr.​com/​cvx (2010)
  17.Hsia, Y., Lin, G.X., Sheu, R.L.: A revisit to quadratic programming with one inequality quadratic constraint via matrix pencil. Pac. J. Optim. 10, 461–481 (2014)MathSciNet
  18.Konno, H., Fukaishi, K.: A branch and bound algorithm for solving low rank linear multiplicative and fractional programming problems. J. Glob. Optim. 18, 283–299 (2000)CrossRef MathSciNet
  19.Kuno, T.: A branch-and-bound algorithm for maximizing the sum of several linear ratios. J. Glob. Optim. 22, 155–174 (2002)CrossRef MathSciNet
  20.Luenberger, D.G., Ye, Y.: Linear and Nonlinear Programming, 3rd edn. Springer, Berlin (2008)
  21.Pólik, I., Terlaky, T.: A survey of S-lemma. SIAM Rev. 49(3), 371–418 (2007)CrossRef MathSciNet
  22.Primolevo, G., Simeone, O., Spagnolini, U.: Towards a joint optimization of scheduling and beamforming for MIMO downlink. In: IEEE Ninth International Symposium on Spread Spectrum Techniques and Applications, pp. 493–497 (2006)
  23.Rendl, F., Wolkowicz, H.: A semidefinite framework for trust region subproblems with applications to large scale minimization. Math. Program. 77, 273–299 (1997)MathSciNet
  24.Sturm, J.F., Zhang, S.: On cones of nonnegative quadratic functions. Math. Oper. Res. 28, 246–267 (2003)CrossRef MathSciNet
  25.Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.): Handbook on Semidefinite Programming: Theory, Algorithms and Applications. Kluwer Academic Publishers, Dordrecht (2000)
  26.Wu, M.C., Zhang, L.S., Wang, Z.X., Christiani, D.C., Lin, X.H.: Sparse linear discriminant analysis for simultaneous testing for the significance of a gene set/pathway and gene selection. Bioinformatics 25, 1145–1151 (2009)CrossRef
  27.Wu, W.Y., Sheu, R.L., Birbil, I.: Solving the sum-of-ratios problem by a stochastic search algorithm. J. Glob. Optim. 42(1), 91–109 (2008)CrossRef MathSciNet
  28.Ye, Y., Zhang, S.Z.: New results on quadratic minimization. SIAM J. Optim. 14(1), 245–267 (2003)CrossRef MathSciNet
  29.Zhang, L.H.: On optimizing the sum of the Rayleigh quotient and the generalized Rayleigh quotient on the unit sphere. Comput. Optim. Appl. 54, 111–139 (2013)CrossRef MathSciNet
  30.Zhang, L.H.: On a self-consistent-field-like iteration for maximizing the sum of the Rayleigh quotients. J. Comput. Appl. Math. 257, 14–28 (2014)CrossRef MathSciNet
  
• 作者单位：Van-Bong Nguyen (1)
  Ruey-Lin Sheu (1)
  Yong Xia (2)
  
  1. Department of Mathematics, National Cheng Kung University, Tainan, Taiwan
  2. State Key Laboratory of Software Development Environment, LMIB of the Ministry of Education, School of Mathematics and System Sciences, Beihang University, Beijing, 100191, People’s Republic of China
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Operation Research and Decision Theory
  Computer Science, general
  Real Functions
  Optimization
  
• 出版者：Springer Netherlands
• ISSN：1573-2916

文摘

The problem is a type of “sum-of-ratios” fractional programming and is known to be NP-hard. Due to many local maxima, finding the global maximizer is in general difficult. The best attempt so far is a critical point approach based on a necessary optimality condition. The problem therefore has not been completely solved. Our novel idea is to replace the generalized Rayleigh quotient by a parameter \(\mu \) and generate a family of quadratic subproblems \((\hbox {P}_{\mu })'s\) subject to two quadratic constraints. Each \((\hbox {P}_{\mu })\), if the problem dimension \(n\ge 3\), can be solved in polynomial time by incorporating a version of S-lemma; a tight SDP relaxation; and a matrix rank-one decomposition procedure. Then, the difficulty of the problem is largely reduced to become a one-dimensional maximization problem over an interval of parameters \([\underline{\mu },\bar{\mu }]\). We propose a two-stage scheme incorporating the quadratic fit line search algorithm to find \(\mu ^*\) numerically. Computational experiments show that our method solves the problem correctly and efficiently. Keywords Fractional programming (Generalized) Rayleigh quotient Quadratically constrained quadratic programming S-Lemma Semidefinite programming Quadratic fit line search