
-
Previous Article
Cooperation in traffic network problems via evolutionary split variational inequalities
- JIMO Home
- This Issue
-
Next Article
Simultaneous optimal predictions under two seemingly unrelated linear random-effects models
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 |
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.
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. |
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. 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. |






1941 (Dines [3]) |
(Dines Theorem) is convex. Moreover, if |
1961 (Brickmen [1]) |
is convex if |
1995 (Ramana & Goldman [11]) Unpublished |
is convex if and only if |
is convex if |
|
1998 (Polyak [10]) |
is convex if |
is convex if |
|
2016 (Bazán & Opazo [5]) |
is convex if and only if where |
1941 (Dines [3]) |
(Dines Theorem) is convex. Moreover, if |
1961 (Brickmen [1]) |
is convex if |
1995 (Ramana & Goldman [11]) Unpublished |
is convex if and only if |
is convex if |
|
1998 (Polyak [10]) |
is convex if |
is convex if |
|
2016 (Bazán & Opazo [5]) |
is convex if and only if where |
[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
Tools
Metrics
Other articles
by authors
[Back to Top]