American Institute of Mathematical Sciences

Advanced
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

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 & 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.  doi: 10.1137/040616851.  Google Scholar

[2]

A. Beck and Y. C. Eldar, Strong duality in nonconvex quadratic optimization with two quadratic constraints,, SIAM Journal on Optimization, 17 (2006), 844.  doi: 10.1137/050644471.  Google Scholar

[3]

H. P. Benson, Fractional programming with convex quadratic forms and functions,, European Journal of Operational Research, 173 (2006), 351.  doi: 10.1016/j.ejor.2005.02.069.  Google Scholar

[4]

G. R. Bitran and T. L. Magnanti, Duality and sensitivity analysis for fractional programs,, Operations Research, 24 (1976), 675.  doi: 10.1287/opre.24.4.675.  Google Scholar

[5]

M. R. Celis, J. E. Dennis and R. A. Tapia, A trust region strategy for nonlinear equality constrained optimization,, in, (1985), 71.   Google Scholar

[6]

A. Charnes and W. W. Cooper, Programming with linear fractional functionals,, Naval Research Logistics Quarterly, 9 (1962), 181.  doi: 10.1002/nav.3800090303.  Google Scholar

[7]

X. Chen and Y. Yuan, On local solutions of the Celis-Dennis-Tapia subproblem,, SIAM Journal on Optimization, 10 (2000), 359.  doi: 10.1137/S1052623498335018.  Google Scholar

[8]

X. Chen and Y. Yuan, On maxima of dual function of the CDT subproblem,, Journal of Computational Mathematics, 19 (2001), 113.   Google Scholar

[9]

X. Chen and Y. Yuan, Optimality conditions for CDT subproblem,, in, (1999), 111.   Google Scholar

[10]

A. R. Conn, N. I. M. Gould and Ph. L. Toint, "Trust-Region Methods,", SIAM, (2000).  doi: 10.1137/1.9780898719857.  Google Scholar

[11]

J. P. Crouzeix and J. A. Ferland, Algorithms for generalized fractional programming,, Mathematical Programming, 52 (1991), 191.  doi: 10.1007/BF01582887.  Google Scholar

[12]

W. Dinkelbach, On nonlinear fractional programming,, Management Science, 13 (1967), 492.  doi: 10.1287/mnsc.13.7.492.  Google Scholar

[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.  doi: 10.1023/A:1011219422283.  Google Scholar

[14]

T. Ibaraki, Parametric approaches to fractional programs,, Mathematical Programming, 26 (1983), 345.  doi: 10.1007/BF02591871.  Google Scholar

[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.   Google Scholar

[16]

R. Jagannathan, On some properties of programming problems in parametric form pertaining to fractional programming,, Management Science, 12 (1966), 609.  doi: 10.1287/mnsc.12.7.609.  Google Scholar

[17]

G. Li and Y. Yuan, Compute a Celis-Dennis-Tapia step,, Journal of Computational Mathematics, 23 (2005), 463.   Google Scholar

[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.  doi: 10.1137/S1052623494261520.  Google Scholar

[19]

M. J. D. Powell and Y. Yuan, A trust region algorithm for equality constrained optimization,, Mathematical Programming, 49 (1991), 189.  doi: 10.1007/BF01588787.  Google Scholar

[20]

J. Von Neumann, Über ein es Gleichungssystem und eine Verallgemeinerung des Brouwerschen Fixpuntsatzes,, in, (1937), 73.   Google Scholar

[21]

Y. Ye and S. Zhang, New results on quadratic minimization,, SIAM Journal on Optimization, 14 (2003), 245.  doi: 10.1137/S105262340139001X.  Google Scholar

[22]

Y. Yuan, On a subproblem of trust region algorithms for constrained optimization,, Mathematical Programming, 47 (1990), 53.  doi: 10.1007/BF01580852.  Google Scholar

[23]

Y. Yuan, A dual algorithm for minimizing a quadratic function with two quadratic constraints,, Journal of Computational Mathematics, 9 (1991), 348.   Google Scholar

[24]

Y. Zhang, Computing a Celis-Dennis-Tapia trust-region step for equality constrained optimization,, Mathematical Programming, 55 (1992), 109.  doi: 10.1007/BF01581194.  Google Scholar

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.  doi: 10.1137/040616851.  Google Scholar

[2]

A. Beck and Y. C. Eldar, Strong duality in nonconvex quadratic optimization with two quadratic constraints,, SIAM Journal on Optimization, 17 (2006), 844.  doi: 10.1137/050644471.  Google Scholar

[3]

H. P. Benson, Fractional programming with convex quadratic forms and functions,, European Journal of Operational Research, 173 (2006), 351.  doi: 10.1016/j.ejor.2005.02.069.  Google Scholar

[4]

G. R. Bitran and T. L. Magnanti, Duality and sensitivity analysis for fractional programs,, Operations Research, 24 (1976), 675.  doi: 10.1287/opre.24.4.675.  Google Scholar

[5]

M. R. Celis, J. E. Dennis and R. A. Tapia, A trust region strategy for nonlinear equality constrained optimization,, in, (1985), 71.   Google Scholar

[6]

A. Charnes and W. W. Cooper, Programming with linear fractional functionals,, Naval Research Logistics Quarterly, 9 (1962), 181.  doi: 10.1002/nav.3800090303.  Google Scholar

[7]

X. Chen and Y. Yuan, On local solutions of the Celis-Dennis-Tapia subproblem,, SIAM Journal on Optimization, 10 (2000), 359.  doi: 10.1137/S1052623498335018.  Google Scholar

[8]

X. Chen and Y. Yuan, On maxima of dual function of the CDT subproblem,, Journal of Computational Mathematics, 19 (2001), 113.   Google Scholar

[9]

X. Chen and Y. Yuan, Optimality conditions for CDT subproblem,, in, (1999), 111.   Google Scholar

[10]

A. R. Conn, N. I. M. Gould and Ph. L. Toint, "Trust-Region Methods,", SIAM, (2000).  doi: 10.1137/1.9780898719857.  Google Scholar

[11]

J. P. Crouzeix and J. A. Ferland, Algorithms for generalized fractional programming,, Mathematical Programming, 52 (1991), 191.  doi: 10.1007/BF01582887.  Google Scholar

[12]

W. Dinkelbach, On nonlinear fractional programming,, Management Science, 13 (1967), 492.  doi: 10.1287/mnsc.13.7.492.  Google Scholar

[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.  doi: 10.1023/A:1011219422283.  Google Scholar

[14]

T. Ibaraki, Parametric approaches to fractional programs,, Mathematical Programming, 26 (1983), 345.  doi: 10.1007/BF02591871.  Google Scholar

[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.   Google Scholar

[16]

R. Jagannathan, On some properties of programming problems in parametric form pertaining to fractional programming,, Management Science, 12 (1966), 609.  doi: 10.1287/mnsc.12.7.609.  Google Scholar

[17]

G. Li and Y. Yuan, Compute a Celis-Dennis-Tapia step,, Journal of Computational Mathematics, 23 (2005), 463.   Google Scholar

[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.  doi: 10.1137/S1052623494261520.  Google Scholar

[19]

M. J. D. Powell and Y. Yuan, A trust region algorithm for equality constrained optimization,, Mathematical Programming, 49 (1991), 189.  doi: 10.1007/BF01588787.  Google Scholar

[20]

J. Von Neumann, Über ein es Gleichungssystem und eine Verallgemeinerung des Brouwerschen Fixpuntsatzes,, in, (1937), 73.   Google Scholar

[21]

Y. Ye and S. Zhang, New results on quadratic minimization,, SIAM Journal on Optimization, 14 (2003), 245.  doi: 10.1137/S105262340139001X.  Google Scholar

[22]

Y. Yuan, On a subproblem of trust region algorithms for constrained optimization,, Mathematical Programming, 47 (1990), 53.  doi: 10.1007/BF01580852.  Google Scholar

[23]

Y. Yuan, A dual algorithm for minimizing a quadratic function with two quadratic constraints,, Journal of Computational Mathematics, 9 (1991), 348.   Google Scholar

[24]

Y. Zhang, Computing a Celis-Dennis-Tapia trust-region step for equality constrained optimization,, Mathematical Programming, 55 (1992), 109.  doi: 10.1007/BF01581194.  Google Scholar

[1]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054
[2]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319
[3]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013
[4]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019
[5]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076
[6]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078
[7]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462
[8]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250
[9]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120
[10]

Lihong Zhang, Wenwen Hou, Bashir Ahmad, Guotao Wang. Radial symmetry for logarithmic Choquard equation involving a generalized tempered fractional $ p $-Laplacian. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020445
[11]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[12]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351
[13]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077
[14]

Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020374
[15]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169
[16]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015
[17]

Anna Abbatiello, Eduard Feireisl, Antoní Novotný. Generalized solutions to models of compressible viscous fluids. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 1-28. doi: 10.3934/dcds.2020345
[18]

Qianqian Han, Xiao-Song Yang. Qualitative analysis of a generalized Nosé-Hoover oscillator. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020346
[19]

Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020171
[20]

Aihua Fan, Jörg Schmeling, Weixiao Shen. $ L^\infty $-estimation of generalized Thue-Morse trigonometric polynomials and ergodic maximization. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 297-327. doi: 10.3934/dcds.2020363

 Impact Factor: 

Tools

Metrics

  • PDF downloads (51)
  • HTML views (0)
  • Cited by (11)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences