# American Institute of Mathematical Sciences

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 & 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.  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
The graph corresponds to Example 1
Let $f(x, y, z) = x^2+y^2$ and $g(x, y, z) = -x^2+y^2+z$
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\}$
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\}.$
For remark (f) in which $f(x, y) = -x^2 + 4 y^2 + 1$ and $g(x, y) = -(x-1)^2+4y^2+1$
Graph for Proof of Theorem 3.1
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$
The joint numerical range $\mathbf{R}(f, g)$ in Example 3
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 & Optimization, 2021  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 & 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 & 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 & 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 & Imaging, 2021, 15 (1) : 159-183. doi: 10.3934/ipi.2020076 [6] 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 & Imaging, , () : -. doi: 10.3934/ipi.2022001 [7] Lipu Zhang, Yinghong Xu, Zhengjing Jin. An efficient algorithm for convex quadratic semi-definite optimization. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 129-144. doi: 10.3934/naco.2012.2.129 [8] Qilin Wang, Liu He, Shengjie Li. Higher-order weak radial epiderivatives and non-convex set-valued optimization problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 465-480. doi: 10.3934/jimo.2018051 [9] Arezu Zare, Mohammad Keyanpour, Maziar Salahi. On fractional quadratic optimization problem with two quadratic constraints. Numerical Algebra, Control & Optimization, 2020, 10 (3) : 301-315. doi: 10.3934/naco.2020003 [10] Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211 [11] Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891 [12] Saeid Ansary Karbasy, Maziar Salahi. Quadratic optimization with two ball constraints. Numerical Algebra, Control & Optimization, 2020, 10 (2) : 165-175. doi: 10.3934/naco.2019046 [13] Ye Tian, Qingwei Jin, Zhibin Deng. Quadratic optimization over a polyhedral cone. Journal of Industrial & Management Optimization, 2016, 12 (1) : 269-283. doi: 10.3934/jimo.2016.12.269 [14] Yoon Mo Jung, Taeuk Jeong, Sangwoon Yun. Non-convex TV denoising corrupted by impulse noise. Inverse Problems & Imaging, 2017, 11 (4) : 689-702. doi: 10.3934/ipi.2017032 [15] Tong Li, Jeungeun Park. Stability of traveling waves of models for image processing with non-convex nonlinearity. Communications on Pure & Applied Analysis, 2018, 17 (3) : 959-985. doi: 10.3934/cpaa.2018047 [16] Tarik Aougab, Stella Chuyue Dong, Robert S. Strichartz. Laplacians on a family of quadratic Julia sets II. Communications on Pure & Applied Analysis, 2013, 12 (1) : 1-58. doi: 10.3934/cpaa.2013.12.1 [17] Sun-Yung Alice Chang, Xi-Nan Ma, Paul Yang. Principal curvature estimates for the convex level sets of semilinear elliptic equations. Discrete & Continuous Dynamical Systems, 2010, 28 (3) : 1151-1164. doi: 10.3934/dcds.2010.28.1151 [18] C. M. Elliott, B. Gawron, S. Maier-Paape, E. S. Van Vleck. Discrete dynamics for convex and non-convex smoothing functionals in PDE based image restoration. Communications on Pure & Applied Analysis, 2006, 5 (1) : 181-200. doi: 10.3934/cpaa.2006.5.181 [19] Koh Katagata. Quartic Julia sets including any two copies of quadratic Julia sets. Discrete & Continuous Dynamical Systems, 2016, 36 (4) : 2103-2112. doi: 10.3934/dcds.2016.36.2103 [20] Ye Tian, Wei Yang, Gene Lai, Menghan Zhao. Predicting non-life insurer's insolvency using non-kernel fuzzy quadratic surface support vector machines. Journal of Industrial & Management Optimization, 2019, 15 (2) : 985-999. doi: 10.3934/jimo.2018081

2020 Impact Factor: 1.801

## Tools

Article outline

Figures and Tables

[Back to Top]