doi: 10.3934/jimo.2020169

On the convexity for the range set of two quadratic functions

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.

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. FangD. Y. GaoG.-X. LinR.-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. XiaS. 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. XiaR.-L. SheuS.-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. FangD. Y. GaoG.-X. LinR.-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. XiaS. 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. XiaR.-L. SheuS.-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 2.  Let $ f(x, y, z) = x^2+y^2 $ and $ g(x, y, z) = -x^2+y^2+z $
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 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 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 6.  Graph for Proof of Theorem 3.1
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 8.  The joint numerical range $ \mathbf{R}(f, g) $ in Example 3
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) $.
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]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076

[2]

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

[3]

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

[4]

Héctor Barge. Čech cohomology, homoclinic trajectories and robustness of non-saddle sets. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020381

[5]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

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

Vieri Benci, Marco Cococcioni. The algorithmic numbers in non-archimedean numerical computing environments. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020449

[8]

Yi-Hsuan Lin, Gen Nakamura, Roland Potthast, Haibing Wang. Duality between range and no-response tests and its application for inverse problems. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020072

[9]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[10]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073

[11]

Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

[12]

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

[13]

Ying Lin, Qi Ye. Support vector machine classifiers by non-Euclidean margins. Mathematical Foundations of Computing, 2020, 3 (4) : 279-300. doi: 10.3934/mfc.2020018

[14]

M. S. Lee, H. G. Harno, B. S. Goh, K. H. Lim. On the bang-bang control approach via a component-wise line search strategy for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 45-61. doi: 10.3934/naco.2020014

[15]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

[16]

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

[17]

Christopher S. Goodrich, Benjamin Lyons, Mihaela T. Velcsov. Analytical and numerical monotonicity results for discrete fractional sequential differences with negative lower bound. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020269

[18]

Omid Nikan, Seyedeh Mahboubeh Molavi-Arabshai, Hossein Jafari. Numerical simulation of the nonlinear fractional regularized long-wave model arising in ion acoustic plasma waves. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020466

[19]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378

[20]

Yangrong Li, Shuang Yang, Qiangheng Zhang. Odd random attractors for stochastic non-autonomous Kuramoto-Sivashinsky equations without dissipation. Electronic Research Archive, 2020, 28 (4) : 1529-1544. doi: 10.3934/era.2020080

2019 Impact Factor: 1.366

Article outline

Figures and Tables

[Back to Top]