September  2020, 10(3): 301-315. doi: 10.3934/naco.2020003

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

Received  March 2019 Revised  August 2019 Published  February 2020

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.

Citation: Arezu Zare, Mohammad Keyanpour, Maziar Salahi. On fractional quadratic optimization problem with two quadratic constraints. Numerical Algebra, Control & Optimization, 2020, 10 (3) : 301-315. doi: 10.3934/naco.2020003
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.  Google Scholar

[2]

R. A. Abrams and A. Ben-Israel, Nonlinear programming in complex space: necessary conditions, SIAM Journal on Control, 9 (1971), 606-620.   Google Scholar

[3]

A. AubryV. Carotenuto and A. De Maio, New results on generalized fractional programming problems with toeplitz quadratics, IEEE Signal Processing Letters, 23 (2016), 848-852.   Google Scholar

[4]

A. AubryA. De MaioY. 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.  Google Scholar

[5]

T. BaleshanA. Jayalath and J. Coetzee, On power minimisation and snr maximisation of distributed beamforming in cooperative communication systems, Electronics Letters, 50 (2014), 712-713.   Google Scholar

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

[7]

H. CaiY. 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.   Google Scholar

[8]

H. ChenS. 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.  Google Scholar

[9]

J. ChenH. 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.  Google Scholar

[10]

A. De MaioY. HuangD. P. PalomarS. 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.  Google Scholar

[11]

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

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

[13]

M. Grant and S. Boyd, CVX: Matlab Software for Disciplined Convex Programming, Version 2.1, 2014. doi: 10.1145/2700586.  Google Scholar

[14]

J. Hsiao, On the optimization of mti clutter rejection, IEEE Transactions on Aerospace and Electronic Systems, AES-10 (1974), 622-629.   Google Scholar

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

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

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

[18]

U. T. Jönsson, A lecture on the s-procedure, Lecture Note at the Royal Institute of Technology, Sweden, 23 (2001), 34-36.   Google Scholar

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

[20]

V.-B. NguyenR.-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.  Google Scholar

[21]

I. Pólik and T. Terlaky, A survey of the s-lemma, SIAM Review, 49 (2007), 371-418.  doi: 10.1137/S003614450444614X.  Google Scholar

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

[23]

R. L. Sheu, An SDP approach for some quadratic fractional problems (nonlinear analysis and convex analysis). Google Scholar

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

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

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

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

[28]

X. ZhangZ. HeX. 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.   Google Scholar

show all references

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

[2]

R. A. Abrams and A. Ben-Israel, Nonlinear programming in complex space: necessary conditions, SIAM Journal on Control, 9 (1971), 606-620.   Google Scholar

[3]

A. AubryV. Carotenuto and A. De Maio, New results on generalized fractional programming problems with toeplitz quadratics, IEEE Signal Processing Letters, 23 (2016), 848-852.   Google Scholar

[4]

A. AubryA. De MaioY. 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.  Google Scholar

[5]

T. BaleshanA. Jayalath and J. Coetzee, On power minimisation and snr maximisation of distributed beamforming in cooperative communication systems, Electronics Letters, 50 (2014), 712-713.   Google Scholar

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

[7]

H. CaiY. 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.   Google Scholar

[8]

H. ChenS. 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.  Google Scholar

[9]

J. ChenH. 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.  Google Scholar

[10]

A. De MaioY. HuangD. P. PalomarS. 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.  Google Scholar

[11]

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

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

[13]

M. Grant and S. Boyd, CVX: Matlab Software for Disciplined Convex Programming, Version 2.1, 2014. doi: 10.1145/2700586.  Google Scholar

[14]

J. Hsiao, On the optimization of mti clutter rejection, IEEE Transactions on Aerospace and Electronic Systems, AES-10 (1974), 622-629.   Google Scholar

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

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

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

[18]

U. T. Jönsson, A lecture on the s-procedure, Lecture Note at the Royal Institute of Technology, Sweden, 23 (2001), 34-36.   Google Scholar

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

[20]

V.-B. NguyenR.-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.  Google Scholar

[21]

I. Pólik and T. Terlaky, A survey of the s-lemma, SIAM Review, 49 (2007), 371-418.  doi: 10.1137/S003614450444614X.  Google Scholar

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

[23]

R. L. Sheu, An SDP approach for some quadratic fractional problems (nonlinear analysis and convex analysis). Google Scholar

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

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

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

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

[28]

X. ZhangZ. HeX. 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.   Google Scholar

Figure 1.  Multi-relays cooperative cognitive communication model [7]
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
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
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
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
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
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
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
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
[1]

Yong Xia, Yu-Jun Gong, Sheng-Nan Han. A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 185-195. doi: 10.3934/naco.2015.5.185

[2]

Jie Sun. On methods for solving nonlinear semidefinite optimization problems. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 1-14. doi: 10.3934/naco.2011.1.1

[3]

Jinling Zhao, Wei Chen, Su Zhang. Immediate schedule adjustment and semidefinite relaxation. Journal of Industrial & Management Optimization, 2019, 15 (2) : 633-645. doi: 10.3934/jimo.2018062

[4]

Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015

[5]

Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial & Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117

[6]

Anwa Zhou, Jinyan Fan. A semidefinite relaxation algorithm for checking completely positive separable matrices. Journal of Industrial & Management Optimization, 2019, 15 (2) : 893-908. doi: 10.3934/jimo.2018076

[7]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101

[8]

Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial & Management Optimization, 2019  doi: 10.3934/jimo.2019135

[9]

Rentsen Enkhbat, Evgeniya A. Finkelstein, Anton S. Anikin, Alexandr Yu. Gornov. Global optimization reduction of generalized Malfatti's problem. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 211-221. doi: 10.3934/naco.2017015

[10]

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 & Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65

[11]

Yang Li, Liwei Zhang. A nonlinear Lagrangian method based on Log-Sigmoid function for nonconvex semidefinite programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 651-669. doi: 10.3934/jimo.2009.5.651

[12]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881

[13]

Daniel Morales-Silva, David Yang Gao. Complete solutions and triality theory to a nonconvex optimization problem with double-well potential in $\mathbb{R}^n $. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 271-282. doi: 10.3934/naco.2013.3.271

[14]

Zhong Wan, Chaoming Hu, Zhanlu Yang. A spectral PRP conjugate gradient methods for nonconvex optimization problem based on modified line search. Discrete & Continuous Dynamical Systems - B, 2011, 16 (4) : 1157-1169. doi: 10.3934/dcdsb.2011.16.1157

[15]

Chunrong Chen, T. C. Edwin Cheng, Shengji Li, Xiaoqi Yang. Nonlinear augmented Lagrangian for nonconvex multiobjective optimization. Journal of Industrial & Management Optimization, 2011, 7 (1) : 157-174. doi: 10.3934/jimo.2011.7.157

[16]

Rentsen Enkhbat, M. V. Barkova, A. S. Strekalovsky. Solving Malfatti's high dimensional problem by global optimization. Numerical Algebra, Control & Optimization, 2016, 6 (2) : 153-160. doi: 10.3934/naco.2016005

[17]

Saeid Ansary Karbasy, Maziar Salahi. Quadratic optimization with two ball constraints. Numerical Algebra, Control & Optimization, 2020, 10 (2) : 165-175. doi: 10.3934/naco.2019046

[18]

Ye Tian, Qingwei Jin, Zhibin Deng. Quadratic optimization over a polyhedral cone. Journal of Industrial & Management Optimization, 2016, 12 (1) : 269-283. doi: 10.3934/jimo.2016.12.269

[19]

Zehui Jia, Xue Gao, Xingju Cai, Deren Han. The convergence rate analysis of the symmetric ADMM for the nonconvex separable optimization problems. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020053

[20]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020117

 Impact Factor: 

Metrics

  • PDF downloads (200)
  • HTML views (413)
  • Cited by (0)

Other articles
by authors

[Back to Top]