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, 2021, 15 (1) : 159-183. 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]

Wei-Chieh Chen, Bogdan Kazmierczak. Traveling waves in quadratic autocatalytic systems with complexing agent. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020364

[4]

Qiang Long, Xue Wu, Changzhi Wu. Non-dominated sorting methods for multi-objective optimization: Review and numerical comparison. Journal of Industrial & Management Optimization, 2021, 17 (2) : 1001-1023. doi: 10.3934/jimo.2020009

[5]

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

[6]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005

[7]

Zaizheng Li, Qidi Zhang. Sub-solutions and a point-wise Hopf's lemma for fractional $ p $-Laplacian. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020293

[8]

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

[9]

Alain Bensoussan, Xinwei Feng, Jianhui Huang. Linear-quadratic-Gaussian mean-field-game with partial observation and common noise. Mathematical Control & Related Fields, 2021, 11 (1) : 23-46. doi: 10.3934/mcrf.2020025

[10]

Lars Grüne, Roberto Guglielmi. On the relation between turnpike properties and dissipativity for continuous time linear quadratic optimal control problems. Mathematical Control & Related Fields, 2021, 11 (1) : 169-188. doi: 10.3934/mcrf.2020032

[11]

Jingrui Sun, Hanxiao Wang. Mean-field stochastic linear-quadratic optimal control problems: Weak closed-loop solvability. Mathematical Control & Related Fields, 2021, 11 (1) : 47-71. doi: 10.3934/mcrf.2020026

[12]

Klemens Fellner, Jeff Morgan, Bao Quoc Tang. Uniform-in-time bounds for quadratic reaction-diffusion systems with mass dissipation in higher dimensions. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 635-651. doi: 10.3934/dcdss.2020334

[13]

Norman Noguera, Ademir Pastor. Scattering of radial solutions for quadratic-type Schrödinger systems in dimension five. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021018

[14]

Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100

[15]

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

[16]

Vadim Azhmyakov, Juan P. Fernández-Gutiérrez, Erik I. Verriest, Stefan W. Pickl. A separation based optimization approach to Dynamic Maximal Covering Location Problems with switched structure. Journal of Industrial & Management Optimization, 2021, 17 (2) : 669-686. doi: 10.3934/jimo.2019128

[17]

Peter Frolkovič, Viera Kleinová. A new numerical method for level set motion in normal direction used in optical flow estimation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 851-863. doi: 10.3934/dcdss.2020347

[18]

Tetsuya Ishiwata, Takeshi Ohtsuka. Numerical analysis of an ODE and a level set methods for evolving spirals by crystalline eikonal-curvature flow. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 893-907. doi: 10.3934/dcdss.2020390

[19]

Magdalena Foryś-Krawiec, Jiří Kupka, Piotr Oprocha, Xueting Tian. On entropy of $ \Phi $-irregular and $ \Phi $-level sets in maps with the shadowing property. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1271-1296. doi: 10.3934/dcds.2020317

[20]

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

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (16)
  • HTML views (92)
  • Cited by (0)

Other articles
by authors

[Back to Top]