January  2022, 18(1): 575-592. 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  January 2022 Early access  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 and Management Optimization, 2022, 18 (1) : 575-592. 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.

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

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

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

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

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.

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

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

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

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

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]

Kamran Jalilian, Kameleh Nasiri Pirbazari. Convex optimization without convexity of constraints on non-necessarily convex sets and its applications in customer satisfaction in automotive industry. Numerical Algebra, Control and Optimization, 2022, 12 (3) : 537-550. doi: 10.3934/naco.2021020

[2]

Meixia Li, Changyu Wang, Biao Qu. Non-convex semi-infinite min-max optimization with noncompact sets. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1859-1881. doi: 10.3934/jimo.2017022

[3]

Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial and Management Optimization, 2019, 15 (4) : 2009-2021. doi: 10.3934/jimo.2018134

[4]

Nurullah Yilmaz, Ahmet Sahiner. On a new smoothing technique for non-smooth, non-convex optimization. Numerical Algebra, Control and Optimization, 2020, 10 (3) : 317-330. doi: 10.3934/naco.2020004

[5]

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 and Imaging, 2021, 15 (1) : 159-183. doi: 10.3934/ipi.2020076

[6]

Mourad Nachaoui, Lekbir Afraites, Aissam Hadri, Amine Laghrib. A non-convex non-smooth bi-level parameter learning for impulse and Gaussian noise mixture removing. Communications on Pure and Applied Analysis, 2022, 21 (4) : 1249-1291. doi: 10.3934/cpaa.2022018

[7]

Lekbir Afraites, Aissam Hadri, Amine Laghrib, Mourad Nachaoui. A non-convex denoising model for impulse and Gaussian noise mixture removing using bi-level parameter identification. Inverse Problems and Imaging, 2022, 16 (4) : 827-870. doi: 10.3934/ipi.2022001

[8]

Yuanyi Zhao, Wenxun Xing. Global optimization for non-convex programs via convex proximal point method. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022142

[9]

Lipu Zhang, Yinghong Xu, Zhengjing Jin. An efficient algorithm for convex quadratic semi-definite optimization. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 129-144. doi: 10.3934/naco.2012.2.129

[10]

Qilin Wang, Liu He, Shengjie Li. Higher-order weak radial epiderivatives and non-convex set-valued optimization problems. Journal of Industrial and Management Optimization, 2019, 15 (2) : 465-480. doi: 10.3934/jimo.2018051

[11]

Arezu Zare, Mohammad Keyanpour, Maziar Salahi. On fractional quadratic optimization problem with two quadratic constraints. Numerical Algebra, Control and Optimization, 2020, 10 (3) : 301-315. doi: 10.3934/naco.2020003

[12]

Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211

[13]

Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial and Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891

[14]

Yuan Shen, Chang Liu, Yannian Zuo, Xingying Zhang. A modified self-adaptive dual ascent method with relaxed stepsize condition for linearly constrained quadratic convex optimization. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022101

[15]

Saeid Ansary Karbasy, Maziar Salahi. Quadratic optimization with two ball constraints. Numerical Algebra, Control and Optimization, 2020, 10 (2) : 165-175. doi: 10.3934/naco.2019046

[16]

Ye Tian, Qingwei Jin, Zhibin Deng. Quadratic optimization over a polyhedral cone. Journal of Industrial and Management Optimization, 2016, 12 (1) : 269-283. doi: 10.3934/jimo.2016.12.269

[17]

Yoon Mo Jung, Taeuk Jeong, Sangwoon Yun. Non-convex TV denoising corrupted by impulse noise. Inverse Problems and Imaging, 2017, 11 (4) : 689-702. doi: 10.3934/ipi.2017032

[18]

Tong Li, Jeungeun Park. Stability of traveling waves of models for image processing with non-convex nonlinearity. Communications on Pure and Applied Analysis, 2018, 17 (3) : 959-985. doi: 10.3934/cpaa.2018047

[19]

Pavel Krejčí, Giselle Antunes Monteiro, Vincenzo Recupero. Non-convex sweeping processes in the space of regulated functions. Communications on Pure and Applied Analysis, 2022, 21 (9) : 2999-3029. doi: 10.3934/cpaa.2022087

[20]

Tarik Aougab, Stella Chuyue Dong, Robert S. Strichartz. Laplacians on a family of quadratic Julia sets II. Communications on Pure and Applied Analysis, 2013, 12 (1) : 1-58. doi: 10.3934/cpaa.2013.12.1

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (265)
  • HTML views (599)
  • Cited by (0)

Other articles
by authors

[Back to Top]