On fractional quadratic optimization problem with two quadratic constraints

Arezu Zare; Mohammad Keyanpour; Maziar Salahi

doi:10.3934/naco.2020003

Article Contents

2020, Volume 10, Issue 3: 301-315. Doi: 10.3934/naco.2020003

This issue Previous Article Numerical solution of bilateral obstacle optimal control problem, where the controls and the obstacles coincide Next Article On a new smoothing technique for non-smooth, non-convex optimization

On fractional quadratic optimization problem with two quadratic constraints

1.
Faculty of Mathematics Statistics and Computer Science, Semnan University, Semnan, Iran
2.
Faculty of Mathematical Sciences and, Center of Excellence for Mathematical Modeling, Optimization and Combinatorial Computing (MMOCC), University of Guilan, Rasht, Iran

^* Corresponding author: Mohammad Keyanpour
^* Corresponding author: Mohammad Keyanpour

Received: March 2019

Revised: August 2019

Published: June 2020

Abstract Full Text(HTML) Figure(1) / Table(4) Related Papers Cited by

Abstract

In this paper, we study the problem of minimizing the ratio of two quadratic functions subject to two quadratic constraints in the complex space. Using the classical Dinkelbach method, we transform the problem into a parametric nonlinear equation. We show that an optimal parameter can be found by employing the S-procedure and semidefinite relaxation technique. A key element to solve the original problem is to use the rank-one decomposition procedure. Finally, within the new algorithm, semidefinite relaxation is compared with the bisection method for finding the root on several examples. For further comparison, the solution of fmincon command of MATLAB also is reported.

Keywords:

Mathematics Subject Classification: 90C32, 90C20, 90C26, 90C22.

Citation:

Full Text(HTML)

Figure 1. Multi-relays cooperative cognitive communication model [7]

Download: Full-size image PowerPoint slide

Table 1. Numerical Results for Example 1

			SDO Method		Bisection Method			fmincon
n	density	λ^*	fvalue	time(s)	λ^*	fvalue	time(s)	fvalue	time(s)
50	1	1.201032e-01	1.201036e-01	0.2703	1.201032e-01	1.201036e-01	5.0101	1.397555e-01	0.0117
100	1	1.881241e-01	1.881249e-01	1.086:3	1.881241e-01	1.881249e-01	20.5448	1.987974e-01	0.0139
150	1	1.643814e-01	1.643875e-01	2.5524	1.643814e-01	1.643875e-01	50.1663	1.698622e-01	0.0174
200	1	1.558427e-01	1.558441e-01	5.9194	1.558427e-01	1.558441e-01	153.8498	1.755857e-01	0.0194
250	1	2.366953e-01	2.366986e-01	8.1471	2.366953e-01	2.366986e-01	226.1209	2.841313e-01	0.0269
50	0.5	1.193231e-02	1.193236e-02	0.2473	1.193231e-02	1.193236e-02	4.7561	1.958082e-02	0.0109
100	0.5	1.446475e-01	1.446483e-01	0.9903	1.446475e-01	1.446483e-01	18.3720	1.596917e-01	0.0128
150	0.5	1.024333e-01	1.024354e-01	2.4031	1.024333e-01	1.024354e-01	43.7765	1.129475e-01	0.0167
200	0.5	2.134589e-01	2.134593e-01	5.3849				2.371164e-01	0.0173
250	0.5	2.103671e-01	2.103684e-01	7.9862				2.278996e-01	0.0238
300	0.5	1.507763e-01	1.507789e-01	14.7993				1.631893e-01	0.0237
50	0.25	1.097243e-01	1.097248e-01	0.2444	1.097243e-01	1.097248e-01	4.4489	2.862603e-01	0.0098
100	0.25	3.690304e-01	3.690309e-01	0.9323	3.690304e-01	3.690309e-01	12.7842	3.791923e-01	0.0121
150	0.25	1.816562e-01	1.816565e-01	2.7160	1.816562^01	1.816565e-01	64.4395	1.944783e-01	0.0161
200	0.25	2.123675e-01	2.123678e-01	5.0127				2.897431e-01	0.0159
250	0.25	2.325119e-01	2.325124e-01	7.5622				2.666913e-01	0.0198
300	0.25	1.394089e-01	1.394093e-01	14.3163				1.534687e-01	0.0219
50	0.1	2.029650e-01	2.029654e-01	0.2021	2.029650e-01	2.029654e-01	3.8651	2.273829e-01	0.0086
100	0.1	4.695384e-01	4.695387e-01	0.8796	4.695384e-01	4.695387e-01	12.1470	4.812845e-01	0.0117
150	0.1	1.325870e-01	1.325874e-01	2.5595	1.325870e-01	1.325874e-01	49.9254	1.470531e-01	0.0144
200	0.1	1.442915e-01	1.442918e-01	4.8677				1.700139e-01	0.0151
250	0.1	4.210943e-01	4.210946e-01	7.1247				4.512736e-01	0.0179
300	0.1	1.547663e-01	1.547C71e-01	13.9812				1.673333e-01	0.0204
350	0.1	3.037856e-01	3.037861e-01	19.2776				3.293677e-01	0.0245
100	0.01	3.132863e-02	3.132868e-02	0.6293	3.132863e-02	3.132868e-02	11.4868	3.693282e-02	0.0117
150	0.01	1.423572e-02	1.423577e-02	1.5306	1.423572e-02	1.423577e-02	37.9483	3.092266e-02	0.0128
200	0.01	3.145664e-01	3.145669e-01	4.2319				3.364780e-01	0.0139
250	0.01	2.597103e-02	2.597105e-02	6.8963				2.777693e-02	0.0167
300	0.01	1.201043e-01	1.201049e-01	13.4639				1.537038e-01	0.0192
350	0.01	2.167836e-02	2.167842e-02	18.6749				2.478134e-02	0.0235
400	0.01	4.531146^01	4.531156e-01	24.1313				4.972134e-01	0.0263

| Show Table

DownLoad: CSV

Table 2. Numerical Results for Example 1

			SDO Method		Bisection Method		fmincon
n	density	λ^*	fvalue	time(s)	λ^*	fvalue	time(s)	fvalue time(s)
50	1	9.963074e-02	9.963075e-02	0.2313	9.963074-02	9.963075e-02	3.8289	—
100	1	2.954031e-02	2.954037e-02	1.0432	2.954031e-02	2.954037e-02	18.6609	—
150	1	1.079322e-01	L079326e-01	2.7307	1.079322e-01	1.079326e-01	47.8104	—
200	1	1.594683e-01	1.594686e-01	5.8439				—
250	1	2.374876e-01	2.374887e-01	8.5416				—
50	0.5	2.644901e-02	2.644909e-02	0.2574	2.644901e-02	2.644909e-02	4.2066	—
100	0.5	2.299581e-01	2.299585e-01	1.0217	2.299581e-01	2.299585e-01	19.3125
150	0.5	1.444501e-01	1.444506e-01	2.2918	1.444501e-01	1.444506e-01	44.9254	—
200	0.5	3.724168e-01	3.724173e-01	5.4688				—
250	0.5	2.552464e-01	2.552473e-01	8.2069				—
300	0.5	2.941125e-01	2.941131e-01	16.0230
50	0.25	1.076935e-02	1.076939e-02	0.2603	1.076935e-02	1.076939e-02	5.0748	—
100	0.25	1.768924e-02	1.768927e-02	0.9174	1.768924e-02	1.768927e-02	12.5113	—
150	0.25	2.993642e-01	2.993644e-01	2.0326	2.993642e-01	2.993644e-01	41.9702	—
200	0.25	3.366870e-01	3.366874e-01	4.9010				—
250	0.25	1.883748e-01	1.883755e-02	7.2461				—
300	0.25	1.649437e-01	1.649446e-01	15.3795
50	0.1	1.692921e-01	1.692924e-01	0.2097	1.692921e-01	1.692924e-01	3.9190	—
100	0.1	1.942553e-01	1.942554e-01	0.9273	1.942553e-01	1.942554e-01	11.9908	—
150	0.1	2.121414e-02	2.121419e-02	1.9469	2.121414e-02	2.121419e-02	40.4315	—
200	0.1	2.737760e-01	2.737764e-01	4.8436				—
250	0.1	1.803547e-01	1803554e-01	7.3638				—
300	0.1	3.003607e-01	3.003612e-01	14.2789				—
350	0.1	2.941177e-01	2.941187e-01	20.2413				—
100	0.01	1.462551e-02	1.462558e-02	0.6089	1.462558e-02	1.462558e-02	11.6858	—
150	0.01	1.371044e-01	1.371049e-01	1.4294	1.371044e-01	1.371049e-01	38.2468	—
200	0.01	2.910353e-01	2.910355e-01	4.4201				—
250	0.01	1.110103e-01	1.110109e-01	6.5731				—
300	0.01	3.831475e-01	3.831484e-01	13.8774				—
350	0.01	1.301978e-01	1.301985e-01	19.2763
400	0.01	2.705236e-01	2.705243e-01	23.9422				—

| Show Table

DownLoad: CSV

Table 3. Numerical Results for Example 2

			SDO Method		Bisection Method			fmincon
n	density	λ^*	fvalue	time(s)	λ^*	fvalue	time(s)	fvalue	time(s)
50	1	1.073815e-01	1.073819e-01	0.2603	1.073815e-01	1.073819e-01	5.6108	1.331134e-01	0.0097
100	1	8.052910e-02	8.052916e-02	1.0407	8.052910e-02	8.052916e-02	23.5367	8.699541e-02	0.0117
150	1	3.159523e-01	3.159529e-01	2.6979	3.159523e-01	3.159529e-01	57.1506	3.692334e-02	0.0131
200	1	9.654340e-01	9.654352e-01	5.7237	9.654340e-01	9.654352e-01	120.0627	9.845699e-01	0.U192
250	1	5.314459e-01	5.314467e-01	7.9846	5.314459e-01	5.314467e-01	146.7938	5.983331e-01	0.0247
50	0.5	6.030734e-02	6.030738e-02	0.2465	6.030734e-02	6.030738e-02	5.2755	6.404861e-02	0.0114
100	0.5	7.375045e-02	7.375047e-02	0.9825	7.375045e-02	7.375047e-02	21.3846	7.915205e-02	0.0102
150	0.5	2.523155e-01	2.523164e-01	2.8862	2.523155e-01	2.523164e-01	50.9374	2.689658e-01	0.0133
2U0	0.5	1.997833e-01	1.997841e-01	5.3377				2.321445e-01	0.0158
250	0.5	4.256789e-01	4.256796e-01	7.7639				4.433670e-01	0.0239
300	0.5	6.730019e-01	6.730022e-01	12.2279				6.846389e-01	0.0268
50	0.25	1.119725e-01	1.119727e-01	0.2428	1.119725e-01	1.119727e-01	5.0119	1.289442e-01	0.0090
100	0.25	4.884773e-02	4.884778e-02	0.9657	4.884773e-02	4.884778e-02	14.003-1	5.102978e-01	0.0109
150	0.25	2.374415e-01	2.374418e-01	2.7611	2.374415e-01	2.374418e-01	47.1437	2.531947e-01	0.0124
200	0.25	3.264711e-02	3.264719e-02	5.1312				3.803010e-02	0.0144
250	0.25	5.412756e-01	5.412759e-01	7.3988				5.732258e-01	0.0216
300	0.25	1.222439e-01	1.222445e-01	12.0333				1.986063e-01	0.0253
50	0.1	1.833330e-01	1.833334e-01	0.2236	1.833330e-01	1.833334e-01	4.9949	1.970122e-01	0.0094
100	0.1	3.380843e-01	3.380847e-01	0.8375	3.380843e-01	3.380847e-01	17.1359	3.426797e-01	0.0112
150	0.1	3.348966e-01	3.348969e-01	2.4617	3.348966e-01	3.348969e-01	46.9201	3.532487e-01	0.0135
200	0.1	1.355464e-01	1.355466e-01	4.8699				1.836288e-01	0.0137
250	0.1	2.002679e-01	2.002685e-01	7.1009				2.321444e-01	0.0205
300	0.1	3.191755e-01	3.191761e-01	11.8233				3.274615e-01	0.0242
350	0.1	8.630814e-02	8.630823e-02	18.7753				8.949326e-01	0.0276
100	0.01	2.322450e-02	2.322456e-02	0.7865	2.322450e-02	2.322456e-02	16.7437	2.481309e-02	0.0104
150	0.01	5.444251e-02	5.444253e-02	2.1999	5.444251e-02	5.444253e-02	43.2585	5.613323e-02	0.0126
200	0.01	2.510731e-01	2.510735e-01	4.5176				2.713509e-01	0.0128
250	0.01	3.722411e-01	3.722423e-01	6.9452				3.830029e-01	0.0132
300	0.01	1.676625e-01	1.676632e-01	11.3290				1.821748e-01	0.0229
350	0.01	1.853554e-01	1.853560e-01	19.5423				1.962172e-01	0.0238
400	0.01	4.531146e-01	4.531156e-01	24.1313				4.972134e-01	0.0263

| Show Table

DownLoad: CSV

Table 4. Numerical Results for Example 2

			SDO Method		Bisection Method		fmincon
n	density	λ^*	fvalue	time(s)	λ^*	fvalue	time(s)	fvalue time(s)
50	1	1.579354e-01	1.579359e-01	0.2742	1.579354e-01	1.579359e-01	5.1885	—
100	1	5.214084e-02	5.214087e-02	0.9871	5.214084e-02	5.214087e-02	23.9418	—
150	1	2.951871e-02	2.951876e-02	2.5428	2.951871e-02	2.951876e-02	56.8249	—
200	1	4.437936e-01	4.437943e-01	5.2411
250	1	1.302289e-01	1.302295e-01	7.5028				—
50	0.5	2.984366e-02	2.984369e-02	0.2527	2.984366e-02	2.984369e-02	5.0748	—
100	0.5	2.547812e-02	2.547816e-02	0.7961	2.547812e-02	2.547816e-02	19.8679	—
150	0.5	1.330274e-01	1.330278e-01	2.2318	1.330274e-01	1.330278e-01	55.3997	—
200	0.5	4.219078e-01	4.219083e-01	5.2065				—
250	0.5	2.903107e-01	2.903111e-01	7.1589
300	0.5	3.600279e-02	3.600286e-01	13.2012				—
50	0.25	1.742665e-02	1.742669e-02	0.2375	1.742665e-02	1.742669e-02	4.9128	—
100	0.25	6.999637e-02	6.999639e-02	0.7539	6.999637e-02	6.999639e-02	19.2247	—
150	0.25	2.181804e-02	2.181807e-02	2.1246	2.181804e-02	2.181807e-02	54.8697	—
200	0.25	1.898546e-01	1.898552e-01	4.9963				- -
250	0.25	4.199379e-01	4.199380e-01	6.8883				—
300	0.25	2.342168e-01	2.342173e-01	12.9771				—
50	0.1	2.254114e-02	2.254117e-02	0.2162	2.254114e-02	2.254117e-02	4.3246	—
100	0.1	1.947362e-02	1.947365e-02	0.6987	1.947362e-02	1.947365e-02	18.9781	—
150	0.1	1.596201e-01	1.596206e-01	1.9342	1.596201e-01	1.596206e-01	52.7639	—
200	0.1	2.603211e-01	2.603213e-01	4.5136				—
250	0.1	2.274938e-01	2.274946e-01	6.2734				—
300	0.1	1.757963e-01	1.757970e-01	12.4938				—
100	0.01	1.977456e-02	1.977458e-02	0.7276	1.977456e-02	1.977458e-02	4.1807	—
150	0.01	6.123555e-02	6.123557e-02	1.5383	6.123555e-02	6.123557e-02	50.9088	—
200	0.01	9.402653e-02	9.402659e-02	4.2944				—
250	0.01	2.351025e-01	2.351028e-01	5.8472				—
300	0.01	1.639947e-01	1.639959e-01	11.8967				—
350	0.01	2.486289e-01	2.486296e-01	20.1709				—
400	0.01	2.519726e-01	2.519735e-01	25.0546				—

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	R. A. Abrams, Nonlinear programming in complex space: sufficient conditions and duality, Journal of Mathematical Analysis and Applications, 38 (1972), 619-632. doi: 10.1016/0022-247X(72)90073-X.
[2]	R. A. Abrams and A. Ben-Israel, Nonlinear programming in complex space: necessary conditions, SIAM Journal on Control, 9 (1971), 606-620.
[3]	A. Aubry, V. Carotenuto and A. De Maio, New results on generalized fractional programming problems with toeplitz quadratics, IEEE Signal Processing Letters, 23 (2016), 848-852.
[4]	A. Aubry, A. De Maio, Y. Huang and M. Piezzo, Robust design of radar doppler filters, IEEE Transactions on Signal Processing, 64 (2016), 5848-5860. doi: 10.1109/TSP.2016.2576423.
[5]	T. Baleshan, A. Jayalath and J. Coetzee, On power minimisation and snr maximisation of distributed beamforming in cooperative communication systems, Electronics Letters, 50 (2014), 712-713.
[6]	O. Besson, Adaptive detection with bounded steering vectors mismatch angle, IEEE Transactions on Signal Processing, 55 (2007), 1560-1564. doi: 10.1109/TSP.2006.890820.
[7]	H. Cai, Y. Wang and T. Yi, An approach for minimizing a quadratically constrained fractional quadratic problem with application to the communications over wireless channels, Optimization Methods and Software, 29 (2014), 310-320.
[8]	H. Chen, S. Shahbazpanahi and A. B. Gershman, Filter-and-forward distributed beamforming for two-way relay networks with frequency selective channels, IEEE Transactions on Signal Processing, 60 (2011), 1927-1941. doi: 10.1109/TSP.2011.2178842.
[9]	J. Chen, H. Lai and S. Schaible, Complex fractional programming and the charnes-cooper transformation, Journal of Optimization Theory and Applications, 126 (2005), 203-213. doi: 10.1007/s10957-005-2669-y.
[10]	A. De Maio, Y. Huang, D. P. Palomar, S. Zhang and A. Farina, Fractional qcqp with applications in ml steering direction estimation for radar detection, IEEE Transactions on Signal Processing, 59 (2010), 172-185. doi: 10.1109/TSP.2010.2087327.
[11]	W. Dinkelbach, On nonlinear fractional programming, Management Science, 13 (1967), 492-498. doi: 10.1287/mnsc.13.7.492.
[12]	S. Fallahi and M. Salahi, On the complex fractional quadratic optimization with a quadratic constraint, Opsearch, 54 (2017), 94-106. doi: 10.1007/s12597-016-0263-8.
[13]	M. Grant and S. Boyd, CVX: Matlab Software for Disciplined Convex Programming, Version 2.1, 2014. doi: 10.1145/2700586.
[14]	J. Hsiao, On the optimization of mti clutter rejection, IEEE Transactions on Aerospace and Electronic Systems, AES-10 (1974), 622-629.
[15]	Y. Huang and S. Zhang, Complex matrix decomposition and quadratic programming, Mathematics of Operations Research, 32 (2007), 758-768. doi: 10.1287/moor.1070.0268.
[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]	V. Jeyakumar, N. Q. Huy and G. Li, Necessary and sufficient conditions for s-lemma and nonconvex quadratic optimization, Optimization and Engineering, 10 (2009), 491. doi: 10.1007/s11081-008-9076-9.
[18]	U. T. Jönsson, A lecture on the s-procedure, Lecture Note at the Royal Institute of Technology, Sweden, 23 (2001), 34-36.
[19]	N. Levinson, Linear programming in complex space, Journal of Mathematical Analysis and Applications, 14 (1966), 44-62. doi: 10.1016/0022-247X(66)90061-8.
[20]	V.-B. Nguyen, R.-L. Sheu and Y. Xia, An SDP approach for quadratic fractional problems with a two-sided quadratic constraint, Optimization Methods and Software, 31 (2016), 701-719. doi: 10.1080/10556788.2015.1029575.
[21]	I. Pólik and T. Terlaky, A survey of the s-lemma, SIAM Review, 49 (2007), 371-418. doi: 10.1137/S003614450444614X.
[22]	M. Salahi and A. Zare, SDO relaxation approach to fractional quadratic minimization with one quadratic constraint, Journal of Mathematical Modeling, 3 (2015), 1-13.
[23]	R. L. Sheu, An SDP approach for some quadratic fractional problems (nonlinear analysis and convex analysis).
[24]	J. F. Sturm and S. Zhang, On cones of nonnegative quadratic functions, Mathematics of Operations Research, 28 (2003), 246-267. doi: 10.1287/moor.28.2.246.14485.
[25]	K. Swarup and J. Sharma, Programming with linear fractional functionals in complex spaces, Cahiers du centre Études et de Recherche Opérationelle, 12 (1970), 103–109.
[26]	T. Yi, L. Guo, K. Niu, H. Cai, J. Lin and W. Ai, Cooperative beamforming in cognitive radio network with hybrid relay, in 2012 19th International Conference on Telecommunications (ICT), IEEE, (2012), 1–5.
[27]	A. Zhang and S. Hayashi, Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints, Numer. Algebra, Control and Optim., 1 (2011), 83-98. doi: 10.3934/naco.2011.1.83.
[28]	X. Zhang, Z. He, X. Zhang and W. Peng, High-performance beampattern synthesis via linear fractional semidefinite relaxation and quasi-convex optimization, IEEE Transactions on Antennas and Propagation, 66 (2018), 3421-3431.