American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Stabilization of 2-d Mindlin-Timoshenko plates with localized acoustic boundary feedback
  • JIMO Home
  • This Issue
  • Next Article
    Extension of Littlewood's rule to the multi-period static revenue management model with standby customers
doi: 10.3934/jimo.2020169

On the convexity for the range set of two quadratic functions

Huu-Quang Nguyen 1,2, , Ya-Chi Chu 2, and  Ruey-Lin Sheu 2,,

1. 

Institute of Natural Science Education, Vinh University, Vinh, Nghe An, Vietnam
2. 

Department of Mathematics, National Cheng Kung University, Tainan, Taiwan

* Corresponding author: Ruey-Lin Sheu

In memory of Professor Hang-Chin Lai for his life contribution in Mathematics and Optimization

Received  July 2020 Revised  September 2020 Published  November 2020

Fund Project: Huu-Quang, Nguyen's research work was supported by Taiwan MOST 108-2811-M-006-537 and Ruey-Lin Sheu's research work was sponsored by Taiwan MOST 107-2115-M-006-011-MY2

Given $ n\times n $ symmetric matrices $ A $ and $ B, $ Dines in 1941 proved that the joint range set $ \{(x^TAx, x^TBx)|\; x\in\mathbb{R}^n\} $ is always convex. Our paper is concerned with non-homogeneous extension of the Dines theorem for the range set $ \mathbf{R}(f, g) = \{\left(f(x), g(x)\right)|\; x \in \mathbb{R}^n \}, $ $ f(x) = x^T A x + 2a^T x + a_0 $ and $ g(x) = x^T B x + 2b^T x + b_0. $ We show that $ \mathbf{R}(f, g) $ is convex if, and only if, any pair of level sets, $ \{x\in\mathbb{R}^n|f(x) = \alpha\} $ and $ \{x\in\mathbb{R}^n|g(x) = \beta\} $, do not separate each other. With the novel geometric concept about separation, we provide a polynomial-time procedure to practically check whether a given $ \mathbf{R}(f, g) $ is convex or not.

Keywords: Non-convex quadratic optimization, joint numerical range, hidden convexity, separation of quadratic level sets, S-lemma.
Mathematics Subject Classification: Primary: 90C20; Secondary: 90C22, 90C26.
Citation: 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, doi: 10.3934/jimo.2020169
References:
[1]

L. Brickmen, On the field of values of a matrix, Proceedings of the American Mathematical Society, 12 (1961), 61-66.  doi: 10.1090/S0002-9939-1961-0122827-1.  Google Scholar

[2]

K. Derinkuyu and M. Ç. Plnar, On the S-procedure and some variants, Mathematical Methods of Operations Research, 64 (2006), 55-77.  doi: 10.1007/s00186-006-0070-8.  Google Scholar

[3]

L. L. Dines, On the mapping of quadratic forms, Bulletin of the American Mathematical Society, 47 (1941), 494-498.  doi: 10.1090/S0002-9904-1941-07494-X.  Google Scholar

[4]

S.-C. Fang, D. Y. Gao, G.-X. Lin, R.-L. Sheu and W. Xing, Double well potential function and its optimization in the n-dimensional real space–Part I, J. Ind. Manag. Optim., 13 (2017), 1291-1305.  doi: 10.3934/jimo.2016073.  Google Scholar

[5]

F. Flores-Bazán and F. Opazo, Characterizing the convexity of joint-range for a pair of inhomogeneous quadratic functions and strong duality, Minimax Theory Appl, 1 (2016), 257-290.   Google Scholar

[6]

H. Q. Nguyen, R. L. Sheu and Y. Xia, Solving a new type of quadratic optimization problem having a joint numerical range constraint, 2020. Available from: https://doi.org/10.13140/RG.2.2.23830.98887. Google Scholar

[7]

H.-Q. Nguyen and R.-L. Sheu, Geometric properties for level sets of quadratic functions, Journal of Global Optimization, 73 (2019), 349-369.  doi: 10.1007/s10898-018-0706-2.  Google Scholar

[8]

H.-Q. Nguyen and R.-L. Sheu, Separation properties of quadratic functions, 2020. Available from: https://doi.org/10.13140/RG.2.2.18518.88647. Google Scholar

[9]

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

[10]

B. T. Polyak, Convexity of quadratic transformations and its use in control and optimization, Journal of Optimization Theory and Applications, 99 (1998), 553-583.  doi: 10.1023/A:1021798932766.  Google Scholar

[11]

M. Ramana and A. J. Goldman, Quadratic maps with convex images, Submitted to Math of OR. Google Scholar

[12]

H. Tuy and H. D. Tuan, Generalized S-lemma and strong duality in nonconvex quadratic programming, Journal of Global Optimization, 56 (2013), 1045-1072.  doi: 10.1007/s10898-012-9917-0.  Google Scholar

[13]

Y. Xia, S. Wang and R.-L. Sheu, S-lemma with equality and its applications, Mathematical Programming, 156 (2016), 513-547.  doi: 10.1007/s10107-015-0907-0.  Google Scholar

[14]

Y. Xia, R.-L. Sheu, S.-C. Fang and W. Xing, Double well potential function and its optimization in the n-dimensional real space–Part II, J. Ind. Manag. Optim., 13 (2017), 1307-1328.  doi: 10.3934/jimo.2016074.  Google Scholar

[15]

V. A. Yakubovich, The S-procedure in nolinear control theory, Vestnik Leninggradskogo Universiteta, Ser. Matematika, (1971), 62–77.  Google Scholar

[16]

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

show all references

References:
[1]

L. Brickmen, On the field of values of a matrix, Proceedings of the American Mathematical Society, 12 (1961), 61-66.  doi: 10.1090/S0002-9939-1961-0122827-1.  Google Scholar

[2]

K. Derinkuyu and M. Ç. Plnar, On the S-procedure and some variants, Mathematical Methods of Operations Research, 64 (2006), 55-77.  doi: 10.1007/s00186-006-0070-8.  Google Scholar

[3]

L. L. Dines, On the mapping of quadratic forms, Bulletin of the American Mathematical Society, 47 (1941), 494-498.  doi: 10.1090/S0002-9904-1941-07494-X.  Google Scholar

[4]

S.-C. Fang, D. Y. Gao, G.-X. Lin, R.-L. Sheu and W. Xing, Double well potential function and its optimization in the n-dimensional real space–Part I, J. Ind. Manag. Optim., 13 (2017), 1291-1305.  doi: 10.3934/jimo.2016073.  Google Scholar

[5]

F. Flores-Bazán and F. Opazo, Characterizing the convexity of joint-range for a pair of inhomogeneous quadratic functions and strong duality, Minimax Theory Appl, 1 (2016), 257-290.   Google Scholar

[6]

H. Q. Nguyen, R. L. Sheu and Y. Xia, Solving a new type of quadratic optimization problem having a joint numerical range constraint, 2020. Available from: https://doi.org/10.13140/RG.2.2.23830.98887. Google Scholar

[7]

H.-Q. Nguyen and R.-L. Sheu, Geometric properties for level sets of quadratic functions, Journal of Global Optimization, 73 (2019), 349-369.  doi: 10.1007/s10898-018-0706-2.  Google Scholar

[8]

H.-Q. Nguyen and R.-L. Sheu, Separation properties of quadratic functions, 2020. Available from: https://doi.org/10.13140/RG.2.2.18518.88647. Google Scholar

[9]

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

[10]

B. T. Polyak, Convexity of quadratic transformations and its use in control and optimization, Journal of Optimization Theory and Applications, 99 (1998), 553-583.  doi: 10.1023/A:1021798932766.  Google Scholar

[11]

M. Ramana and A. J. Goldman, Quadratic maps with convex images, Submitted to Math of OR. Google Scholar

[12]

H. Tuy and H. D. Tuan, Generalized S-lemma and strong duality in nonconvex quadratic programming, Journal of Global Optimization, 56 (2013), 1045-1072.  doi: 10.1007/s10898-012-9917-0.  Google Scholar

[13]

Y. Xia, S. Wang and R.-L. Sheu, S-lemma with equality and its applications, Mathematical Programming, 156 (2016), 513-547.  doi: 10.1007/s10107-015-0907-0.  Google Scholar

[14]

Y. Xia, R.-L. Sheu, S.-C. Fang and W. Xing, Double well potential function and its optimization in the n-dimensional real space–Part II, J. Ind. Manag. Optim., 13 (2017), 1307-1328.  doi: 10.3934/jimo.2016074.  Google Scholar

[15]

V. A. Yakubovich, The S-procedure in nolinear control theory, Vestnik Leninggradskogo Universiteta, Ser. Matematika, (1971), 62–77.  Google Scholar

[16]

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

Figure 1.  The graph corresponds to Example 1
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Let $ f(x, y, z) = x^2+y^2 $ and $ g(x, y, z) = -x^2+y^2+z $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  For remark (c) and remark (e). Let $f(x, y) = -x^2 + 4 y^2$ and $g(x, y) = 2x-y$. The level set $\{g = 0\}$ separates $\{f<0\}, $ while $\{g = 0\}$ does not separate $\{f = 0\}$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  For remark (d). Let $f(x, y) = -x^2 + 4 y^2 - 1$ and $g(x, y) = x-5y$. The level set $\{g = 0\}$ separates $\{f = 0\}$ while $\{g = 0\}$ does not separate $\{f<0\}.$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  For remark (f) in which $ f(x, y) = -x^2 + 4 y^2 + 1 $ and $ g(x, y) = -(x-1)^2+4y^2+1 $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  Graph for Proof of Theorem 3.1
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  For Example 2. Let $ f(x, y) = -\frac{\sqrt{3}}{2} x^2 + \frac{\sqrt{3}}{2} y^2 + x - \frac{1}{2} y $ and $ g(x, y) = \frac{1}{2} x^2 - \frac{1}{2} y^2 + \sqrt{3} x - \frac{\sqrt{3}}{2} y $
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 8.  The joint numerical range $ \mathbf{R}(f, g) $ in Example 3
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Chronological list of notable results related to problem (P)
1941
(Dines [3])		 (Dines Theorem)
$ \left\{ \left. \left( x^T A x, x^T B x \right) \; \right|\; x \in \mathbb{R}^n \right\} $
is convex. Moreover, if $ x^T A x $ and $ x^T B x $ has no common zero except for $ x=0 $, then $ \left\{ \left. \left( x^T A x, x^T B x \right) \; \right|\; x \in \mathbb{R}^n \right\} $ is either $ \mathbb{R}^2 $ or an angular sector of angle less than $ \pi $.
1961
(Brickmen [1])		 $ \mathbf{K}_{A, B} = \left\{ \left. \left( x^T A x, x^T B x \right) \; \right|\; x \in \mathbb{R}^n\; , \; \|x\|=1 \right\} $
is convex if $ n \geq 3 $.
1995
(Ramana & Goldman [11])
Unpublished		 $ \mathbf{R}(f, g) = \left\{ \left. \left( f(x), g(x) \right) \; \right|\; x \in \mathbb{R}^n \right\} $
is convex if and only if $ \mathbf{R}(f, g) = \mathbf{R}(f_H, g_H) + \mathbf{R}(f, g) $, where $ f_H(x) = x^T A x $ and $ g_H(x) = x^T B x $.
$ \mathbf{R}(f, g) = \left\{ \left. \left( f(x), g(x) \right) \; \right|\; x \in \mathbb{R}^n \right\} $
is convex if $ n \geq 2 $ and $ \exists\; \alpha, \beta \in \mathbb{R} $ such that $ \alpha A + \beta B \succ 0 $.
1998
(Polyak [10])		 $ \left\{ \left. \left( x^T A x, x^T B x, x^T C x \right) \; \right|\; x \in \mathbb{R}^n \right\} $
is convex if $ n \geq 3 $ and $ \exists\; \alpha, \beta, \gamma \in \mathbb{R} $ such that $ \alpha A + \beta B + \gamma C \succ 0 $.
$ \left\{ \left. \left( x^T A_1 x, \cdots, x^T A_m x \right) \; \right|\; x \in \mathbb{R}^n \right\} $
is convex if $ A_1, \cdots, A_m $ commute.
2016
(Bazán & Opazo [5])		 $ \mathbf{R}(f, g) = \left\{ \left. \left( f(x), g(x) \right) \; \right|\; x \in \mathbb{R}^n \right\} $
is convex if and only if $ \exists\; d=(d_1, d_2) \in \mathbb{R}^2 $, $ d \neq 0 $, such that the following four conditions hold:
$ \bf{(C1):} $ $ F_L \left( \mathcal{N}(A) \cap \mathcal{N}(B) \right) = \{0\} $
$ \bf{(C2):} $ $ d_2 A = d_1 B $
$ \bf{(C3):} $ $ -d \in \mathbf{R}(f_H, g_H) $
$ \bf{(C4):} $ $ F_H(u) = -d \implies \langle F_L(u), d_{\perp}\rangle \neq 0 $
where $ \mathcal{N}(A) $ and $ \mathcal{N}(B) $ denote the null space of $ A $ and $ B $ respectively, $ F_H(x) = \left( f_H(x), g_H(x) \right) = \left( x^T A x , x^T B x \right) $, $ F_L(x) = \left( a^T x , b^T x \right) $, and $ d_{\perp} = (-d_2, d_1) $.
Table Options

Download as excel

1941
(Dines [3])		 (Dines Theorem)
$ \left\{ \left. \left( x^T A x, x^T B x \right) \; \right|\; x \in \mathbb{R}^n \right\} $
is convex. Moreover, if $ x^T A x $ and $ x^T B x $ has no common zero except for $ x=0 $, then $ \left\{ \left. \left( x^T A x, x^T B x \right) \; \right|\; x \in \mathbb{R}^n \right\} $ is either $ \mathbb{R}^2 $ or an angular sector of angle less than $ \pi $.
1961
(Brickmen [1])		 $ \mathbf{K}_{A, B} = \left\{ \left. \left( x^T A x, x^T B x \right) \; \right|\; x \in \mathbb{R}^n\; , \; \|x\|=1 \right\} $
is convex if $ n \geq 3 $.
1995
(Ramana & Goldman [11])
Unpublished		 $ \mathbf{R}(f, g) = \left\{ \left. \left( f(x), g(x) \right) \; \right|\; x \in \mathbb{R}^n \right\} $
is convex if and only if $ \mathbf{R}(f, g) = \mathbf{R}(f_H, g_H) + \mathbf{R}(f, g) $, where $ f_H(x) = x^T A x $ and $ g_H(x) = x^T B x $.
$ \mathbf{R}(f, g) = \left\{ \left. \left( f(x), g(x) \right) \; \right|\; x \in \mathbb{R}^n \right\} $
is convex if $ n \geq 2 $ and $ \exists\; \alpha, \beta \in \mathbb{R} $ such that $ \alpha A + \beta B \succ 0 $.
1998
(Polyak [10])		 $ \left\{ \left. \left( x^T A x, x^T B x, x^T C x \right) \; \right|\; x \in \mathbb{R}^n \right\} $
is convex if $ n \geq 3 $ and $ \exists\; \alpha, \beta, \gamma \in \mathbb{R} $ such that $ \alpha A + \beta B + \gamma C \succ 0 $.
$ \left\{ \left. \left( x^T A_1 x, \cdots, x^T A_m x \right) \; \right|\; x \in \mathbb{R}^n \right\} $
is convex if $ A_1, \cdots, A_m $ commute.
2016
(Bazán & Opazo [5])		 $ \mathbf{R}(f, g) = \left\{ \left. \left( f(x), g(x) \right) \; \right|\; x \in \mathbb{R}^n \right\} $
is convex if and only if $ \exists\; d=(d_1, d_2) \in \mathbb{R}^2 $, $ d \neq 0 $, such that the following four conditions hold:
$ \bf{(C1):} $ $ F_L \left( \mathcal{N}(A) \cap \mathcal{N}(B) \right) = \{0\} $
$ \bf{(C2):} $ $ d_2 A = d_1 B $
$ \bf{(C3):} $ $ -d \in \mathbf{R}(f_H, g_H) $
$ \bf{(C4):} $ $ F_H(u) = -d \implies \langle F_L(u), d_{\perp}\rangle \neq 0 $
where $ \mathcal{N}(A) $ and $ \mathcal{N}(B) $ denote the null space of $ A $ and $ B $ respectively, $ F_H(x) = \left( f_H(x), g_H(x) \right) = \left( x^T A x , x^T B x \right) $, $ F_L(x) = \left( a^T x , b^T x \right) $, and $ d_{\perp} = (-d_2, d_1) $.
[1]

Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141
[2]

Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881
[3]

Z. Reichstein and B. Youssin. Parusinski's "Key Lemma" via algebraic geometry. Electronic Research Announcements, 1999, 5: 136-145.

[4]

Vieri Benci, Marco Cococcioni. The algorithmic numbers in non-archimedean numerical computing environments. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1673-1692. doi: 10.3934/dcdss.2020449
[5]

Emma D'Aniello, Saber Elaydi. The structure of $ \omega $-limit sets of asymptotically non-autonomous discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 903-915. doi: 10.3934/dcdsb.2019195
[6]

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

Johannes Kellendonk, Lorenzo Sadun. Conjugacies of model sets. Discrete & Continuous Dynamical Systems - A, 2017, 37 (7) : 3805-3830. doi: 10.3934/dcds.2017161
[8]

Joel Fotso Tachago, Giuliano Gargiulo, Hubert Nnang, Elvira Zappale. Multiscale homogenization of integral convex functionals in Orlicz Sobolev setting. Evolution Equations & Control Theory, 2021, 10 (2) : 297-320. doi: 10.3934/eect.2020067
[9]

Yahui Niu. A Hopf type lemma and the symmetry of solutions for a class of Kirchhoff equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021027
[10]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119
[11]

Raghda A. M. Attia, Dumitru Baleanu, Dianchen Lu, Mostafa M. A. Khater, El-Sayed Ahmed. Computational and numerical simulations for the deoxyribonucleic acid (DNA) model. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021018
[12]

Eduardo Casas, Christian Clason, Arnd Rösch. Preface special issue on system modeling and optimization. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021008
[13]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[14]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[15]

Hailing Xuan, Xiaoliang Cheng. Numerical analysis and simulation of an adhesive contact problem with damage and long memory. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2781-2804. doi: 10.3934/dcdsb.2020205
[16]

Vakhtang Putkaradze, Stuart Rogers. Numerical simulations of a rolling ball robot actuated by internal point masses. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 143-207. doi: 10.3934/naco.2020021
[17]

Hailing Xuan, Xiaoliang Cheng. Numerical analysis of a thermal frictional contact problem with long memory. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021031
[18]

Elena K. Kostousova. External polyhedral estimates of reachable sets of discrete-time systems with integral bounds on additive terms. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021015
[19]

Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329
[20]

Ronald E. Mickens. Positivity preserving discrete model for the coupled ODE's modeling glycolysis. Conference Publications, 2003, 2003 (Special) : 623-629. doi: 10.3934/proc.2003.2003.623

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (30)
  • HTML views (149)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences