American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Formal analysis of the Schulz matrix inversion algorithm: A paradigm towards computer aided verification of general matrix flow solvers
  • NACO Home
  • This Issue
  • Next Article
    Generalized nash equilibrium problem based on malfatti's problem
doi: 10.3934/naco.2020003

On fractional quadratic optimization problem with two quadratic constraints

Arezu Zare 1, , Mohammad Keyanpour 2,, and  Maziar Salahi 2,

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.

Keywords: Fractional quadratic optimization, Nonconvex problem, S-procedure, Semidefinite optimization, Semidefinite relaxation.
Mathematics Subject Classification: 90C32, 90C20, 90C26, 90C22.
Citation: Arezu Zare, Mohammad Keyanpour, Maziar Salahi. On fractional quadratic optimization problem with two quadratic constraints. Numerical Algebra, Control & Optimization, 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. 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.   Google Scholar

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

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

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

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

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

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

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

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

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

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

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

Download full-size image

Download as 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
Table Options

Download as excel

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 —
Table Options

Download as excel

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
Table Options

Download as excel

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 —
Table Options

Download as excel

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, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019135
[9]

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
[10]

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
[11]

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
[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]

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
[18]

Saeid Ansary Karbasy, Maziar Salahi. Quadratic optimization with two ball constraints. Numerical Algebra, Control & Optimization, 2019, 0 (0) : 0-0. doi: 10.3934/naco.2019046
[19]

Jing Zhou, Zhibin Deng. A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2019044
[20]

Chunrong Chen. A unified nonlinear augmented Lagrangian approach for nonconvex vector optimization. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 495-508. doi: 10.3934/naco.2011.1.495

 Impact Factor: 

Tools

Metrics

  • PDF downloads (79)
  • HTML views (167)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences