Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints

Previous Article
Filter-based genetic algorithm for mixed variable programming
NACO Home
This Issue
Next Article
A modified Fletcher-Reeves-Type derivative-free method for symmetric nonlinear equations

2011, 1(1): 83-98. doi: 10.3934/naco.2011.1.83

Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints

Ailing Zhang ^1, and Shunsuke Hayashi ^2,

1.	Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Yoshida-Honmachi, Sakyo-Ku, Kyoto 606-8501, Japan
2.	Department of Applied Mathematics and Physics,, Graduate School of Informatics, Kyoto University, Yoshida-Honmachi, Sakyo-Ku, Kyoto 606-8501, Japan

Received August 2010 Revised October 2010 Published February 2011

Abstract
Related Papers

In this paper, we focus on fractional programming problems that minimize the ratio of two indefinite quadratic functions subject to two quadratic constraints. Utilizing the relationship between fractional programming and parametric programming, we transform the original problem into a univariate nonlinear equation. To evaluate the function in the equation, we need to solve a problem of minimizing a nonconvex quadratic function subject to two quadratic constraints. This problem is commonly called a Celis-Dennis-Tapia (CDT) subproblem, which arises in some trust region algorithms for equality constrained optimization. In the outer iterations of the algorithm, we employ the bisection method and/or the generalized Newton method. In the inner iterations, we utilize Yuan's theorem to obtain the global optima of the CDT subproblems. We also show some numerical results to examine the efficiency of the algorithm. Particularly, we will observe that the generalized Newton method is more robust to the erroneous evaluation for the univariate functions than the bisection method.

Keywords: nonconvex quadratic programming, Fractional programming, generalized Newton method., Celis-Dennis-Tapia subproblems, bisection method.

Mathematics Subject Classification: Primary: 90C32, 90C20; Secondary: 90C2.

Citation: Ailing Zhang, Shunsuke Hayashi. Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 83-98. doi: 10.3934/naco.2011.1.83

References:

[1]	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 Journal on Matrix Analysis and Applications, 28 (2006), 425-445. doi: 10.1137/040616851.
[2]	A. Beck and Y. C. Eldar, Strong duality in nonconvex quadratic optimization with two quadratic constraints, SIAM Journal on Optimization, 17 (2006), 844-860. doi: 10.1137/050644471.
[3]	H. P. Benson, Fractional programming with convex quadratic forms and functions, European Journal of Operational Research, 173 (2006), 351-369. doi: 10.1016/j.ejor.2005.02.069.
[4]	G. R. Bitran and T. L. Magnanti, Duality and sensitivity analysis for fractional programs, Operations Research, 24 (1976), 675-699. doi: 10.1287/opre.24.4.675.
[5]	M. R. Celis, J. E. Dennis and R. A. Tapia, A trust region strategy for nonlinear equality constrained optimization, in "Numerical Optimization" (eds. P. T. Boggs, R. H. Byrd, R. B. Schnabel), SIAM, Philadelphia, (1985), 71-82.
[6]	A. Charnes and W. W. Cooper, Programming with linear fractional functionals, Naval Research Logistics Quarterly, 9 (1962), 181-186. doi: 10.1002/nav.3800090303.
[7]	X. Chen and Y. Yuan, On local solutions of the Celis-Dennis-Tapia subproblem, SIAM Journal on Optimization, 10 (2000), 359-383. doi: 10.1137/S1052623498335018.
[8]	X. Chen and Y. Yuan, On maxima of dual function of the CDT subproblem, Journal of Computational Mathematics, 19 (2001), 113-124.
[9]	X. Chen and Y. Yuan, Optimality conditions for CDT subproblem, in "Numerical Linear Algebra and Optimization" (eds. Y. Yuan), Science Press, Beijing, New York, (1999), 111-121.
[10]	A. R. Conn, N. I. M. Gould and Ph. L. Toint, "Trust-Region Methods," SIAM, Philadelphia, 2000. doi: 10.1137/1.9780898719857.
[11]	J. P. Crouzeix and J. A. Ferland, Algorithms for generalized fractional programming, Mathematical Programming, 52 (1991), 191-207. doi: 10.1007/BF01582887.
[12]	W. Dinkelbach, On nonlinear fractional programming, Management Science, 13 (1967), 492-498. doi: 10.1287/mnsc.13.7.492.
[13]	J. Gotoh and H. Konno, Maximization of the ratio of two convex quadratic functions over a polytope, Computational Optimization and Applications, 20 (2001), 43-60. doi: 10.1023/A:1011219422283.
[14]	T. Ibaraki, Parametric approaches to fractional programs, Mathematical Programming, 26 (1983), 345-362. doi: 10.1007/BF02591871.
[15]	T. Ibaraki, H. Ishii, J. Iwase, T. Hasegawa and H. Mine, Algorithms for quadratic fractional programming problems, Journal of Operational Research Society of Japan, 19 (1976), 174-191.
[16]	R. Jagannathan, On some properties of programming problems in parametric form pertaining to fractional programming, Management Science, 12 (1966), 609-615. doi: 10.1287/mnsc.12.7.609.
[17]	G. Li and Y. Yuan, Compute a Celis-Dennis-Tapia step, Journal of Computational Mathematics, 23 (2005), 463-478.
[18]	J. Peng and Y. Yuan, Optimality conditions for the minimization of a quadratic with two quadratic constraints, SIAM Journal on Optimization, 7 (1997), 579-594. doi: 10.1137/S1052623494261520.
[19]	M. J. D. Powell and Y. Yuan, A trust region algorithm for equality constrained optimization, Mathematical Programming, 49 (1991), 189-211. doi: 10.1007/BF01588787.
[20]	J. Von Neumann, Über ein es Gleichungssystem und eine Verallgemeinerung des Brouwerschen Fixpuntsatzes, in "Ergebnisse eines mathematicschen Kolloquiums (8)" (eds. K. Menger), Leipzig und Wien, (1937), 73-83.
[21]	Y. Ye and S. Zhang, New results on quadratic minimization, SIAM Journal on Optimization, 14 (2003), 245-267. doi: 10.1137/S105262340139001X.
[22]	Y. Yuan, On a subproblem of trust region algorithms for constrained optimization, Mathematical Programming, 47 (1990), 53-63. doi: 10.1007/BF01580852.
[23]	Y. Yuan, A dual algorithm for minimizing a quadratic function with two quadratic constraints, Journal of Computational Mathematics, 9 (1991), 348-359.
[24]	Y. Zhang, Computing a Celis-Dennis-Tapia trust-region step for equality constrained optimization, Mathematical Programming, 55 (1992), 109-124. doi: 10.1007/BF01581194.

show all references

References:

[1]	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 Journal on Matrix Analysis and Applications, 28 (2006), 425-445. doi: 10.1137/040616851.
[2]	A. Beck and Y. C. Eldar, Strong duality in nonconvex quadratic optimization with two quadratic constraints, SIAM Journal on Optimization, 17 (2006), 844-860. doi: 10.1137/050644471.
[3]	H. P. Benson, Fractional programming with convex quadratic forms and functions, European Journal of Operational Research, 173 (2006), 351-369. doi: 10.1016/j.ejor.2005.02.069.
[4]	G. R. Bitran and T. L. Magnanti, Duality and sensitivity analysis for fractional programs, Operations Research, 24 (1976), 675-699. doi: 10.1287/opre.24.4.675.
[5]	M. R. Celis, J. E. Dennis and R. A. Tapia, A trust region strategy for nonlinear equality constrained optimization, in "Numerical Optimization" (eds. P. T. Boggs, R. H. Byrd, R. B. Schnabel), SIAM, Philadelphia, (1985), 71-82.
[6]	A. Charnes and W. W. Cooper, Programming with linear fractional functionals, Naval Research Logistics Quarterly, 9 (1962), 181-186. doi: 10.1002/nav.3800090303.
[7]	X. Chen and Y. Yuan, On local solutions of the Celis-Dennis-Tapia subproblem, SIAM Journal on Optimization, 10 (2000), 359-383. doi: 10.1137/S1052623498335018.
[8]	X. Chen and Y. Yuan, On maxima of dual function of the CDT subproblem, Journal of Computational Mathematics, 19 (2001), 113-124.
[9]	X. Chen and Y. Yuan, Optimality conditions for CDT subproblem, in "Numerical Linear Algebra and Optimization" (eds. Y. Yuan), Science Press, Beijing, New York, (1999), 111-121.
[10]	A. R. Conn, N. I. M. Gould and Ph. L. Toint, "Trust-Region Methods," SIAM, Philadelphia, 2000. doi: 10.1137/1.9780898719857.
[11]	J. P. Crouzeix and J. A. Ferland, Algorithms for generalized fractional programming, Mathematical Programming, 52 (1991), 191-207. doi: 10.1007/BF01582887.
[12]	W. Dinkelbach, On nonlinear fractional programming, Management Science, 13 (1967), 492-498. doi: 10.1287/mnsc.13.7.492.
[13]	J. Gotoh and H. Konno, Maximization of the ratio of two convex quadratic functions over a polytope, Computational Optimization and Applications, 20 (2001), 43-60. doi: 10.1023/A:1011219422283.
[14]	T. Ibaraki, Parametric approaches to fractional programs, Mathematical Programming, 26 (1983), 345-362. doi: 10.1007/BF02591871.
[15]	T. Ibaraki, H. Ishii, J. Iwase, T. Hasegawa and H. Mine, Algorithms for quadratic fractional programming problems, Journal of Operational Research Society of Japan, 19 (1976), 174-191.
[16]	R. Jagannathan, On some properties of programming problems in parametric form pertaining to fractional programming, Management Science, 12 (1966), 609-615. doi: 10.1287/mnsc.12.7.609.
[17]	G. Li and Y. Yuan, Compute a Celis-Dennis-Tapia step, Journal of Computational Mathematics, 23 (2005), 463-478.
[18]	J. Peng and Y. Yuan, Optimality conditions for the minimization of a quadratic with two quadratic constraints, SIAM Journal on Optimization, 7 (1997), 579-594. doi: 10.1137/S1052623494261520.
[19]	M. J. D. Powell and Y. Yuan, A trust region algorithm for equality constrained optimization, Mathematical Programming, 49 (1991), 189-211. doi: 10.1007/BF01588787.
[20]	J. Von Neumann, Über ein es Gleichungssystem und eine Verallgemeinerung des Brouwerschen Fixpuntsatzes, in "Ergebnisse eines mathematicschen Kolloquiums (8)" (eds. K. Menger), Leipzig und Wien, (1937), 73-83.
[21]	Y. Ye and S. Zhang, New results on quadratic minimization, SIAM Journal on Optimization, 14 (2003), 245-267. doi: 10.1137/S105262340139001X.
[22]	Y. Yuan, On a subproblem of trust region algorithms for constrained optimization, Mathematical Programming, 47 (1990), 53-63. doi: 10.1007/BF01580852.
[23]	Y. Yuan, A dual algorithm for minimizing a quadratic function with two quadratic constraints, Journal of Computational Mathematics, 9 (1991), 348-359.
[24]	Y. Zhang, Computing a Celis-Dennis-Tapia trust-region step for equality constrained optimization, Mathematical Programming, 55 (1992), 109-124. doi: 10.1007/BF01581194.

[1]	Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283
[2]	Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2675-2701. doi: 10.3934/jimo.2019075
[3]	Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial and Management Optimization, 2014, 10 (2) : 543-556. doi: 10.3934/jimo.2014.10.543
[4]	Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027
[5]	Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial and Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65
[6]	Yang Li, Liwei Zhang. A nonlinear Lagrangian method based on Log-Sigmoid function for nonconvex semidefinite programming. Journal of Industrial and Management Optimization, 2009, 5 (3) : 651-669. doi: 10.3934/jimo.2009.5.651
[7]	Yue Lu, Ying-En Ge, Li-Wei Zhang. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems. Journal of Industrial and Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317
[8]	Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial and Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319
[9]	Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193
[10]	Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397
[11]	Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353
[12]	Ziye Shi, Qingwei Jin. Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 871-882. doi: 10.3934/jimo.2014.10.871
[13]	Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial and Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723
[14]	Xian-Jun Long, Jing Quan. Optimality conditions and duality for minimax fractional programming involving nonsmooth generalized univexity. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 361-370. doi: 10.3934/naco.2011.1.361
[15]	Saeed Ketabchi, Hossein Moosaei, M. Parandegan, Hamidreza Navidi. Computing minimum norm solution of linear systems of equations by the generalized Newton method. Numerical Algebra, Control and Optimization, 2017, 7 (2) : 113-119. doi: 10.3934/naco.2017008
[16]	Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial and Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529
[17]	Jinzhi Wang, Yuduo Zhang. Solving the seepage problems with free surface by mathematical programming method. Numerical Algebra, Control and Optimization, 2015, 5 (4) : 351-357. doi: 10.3934/naco.2015.5.351
[18]	Cheng Ma, Xun Li, Ka-Fai Cedric Yiu, Yongjian Yang, Liansheng Zhang. On an exact penalty function method for semi-infinite programming problems. Journal of Industrial and Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705
[19]	Yanqun Liu. An exterior point linear programming method based on inclusive normal cones. Journal of Industrial and Management Optimization, 2010, 6 (4) : 825-846. doi: 10.3934/jimo.2010.6.825
[20]	Li Jin, Hongying Huang. Differential equation method based on approximate augmented Lagrangian for nonlinear programming. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2267-2281. doi: 10.3934/jimo.2019053

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Ailing Zhang Shunsuke Hayashi
on Google Scholar
Ailing Zhang Shunsuke Hayashi

[Back to Top]