On the convexity for the range set of two quadratic functions

Huu-Quang Nguyen; Ya-Chi Chu; Ruey-Lin Sheu

doi:10.3934/jimo.2020169

Article Contents

2022, Volume 18, Issue 1: 575-592. Doi: 10.3934/jimo.2020169

This issue Previous Article Simultaneous optimal predictions under two seemingly unrelated linear random-effects models Next Article Cooperation in traffic network problems via evolutionary split variational inequalities

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
^* 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

Early access: November 2020

Published: January 2022

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.

Abstract / Introduction Full Text(HTML) Figure(8) / Table(1) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 90C20; Secondary: 90C22, 90C26.

Citation:

Full Text(HTML)

Figure 1. The graph corresponds to Example 1

Download: Full-size image PowerPoint slide

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

Download: Full-size image 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\}$

Download: Full-size image 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\}.$

Download: Full-size image 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 $

Download: Full-size image PowerPoint slide

Figure 6. Graph for Proof of Theorem 3.1

Download: Full-size image 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 $

Download: Full-size image PowerPoint slide

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

Download: Full-size image 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 $.
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 $ 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 $.
1998 (Polyak [10])	$ \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) $.

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[9]	I. Pólik and T. Terlaky, A survey of the S-lemma, SIAM Review, 49 (2007), 371-418. doi: 10.1137/S003614450444614X.
[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.
[11]	M. Ramana and A. J. Goldman, Quadratic maps with convex images, Submitted to Math of OR.
[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.
[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.
[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.
[15]	V. A. Yakubovich, The S-procedure in nolinear control theory, Vestnik Leninggradskogo Universiteta, Ser. Matematika, (1971), 62–77.
[16]	Y. Ye and S. Zhang, New results on quadratic minimization, SIAM Journal on Optimization, 14 (2003), 245-267. doi: 10.1137/S105262340139001X.