Separating disconnected quadratic level sets by other quadratic level sets

Journal of Global Optimization - Trang 1-27 - 2023
Huu-Quang Nguyen1, Ya-Chi Chu2, Ruey-Lin Sheu3
1Department of Mathematics, Vinh University, Vinh, Vietnam
2Department of Mathematics, Stanford University, Stanford, USA
3Department of Mathematics, National Cheng Kung University, Tainan, Taiwan

Tóm tắt

Given a quadratic function $$f(x) = x^T A x + 2 a^T x + a_0$$ and its level sets, including $$\{x\in \mathbb {R}^n \mid f(x) < 0\}$$ , $$\{x\in \mathbb {R}^n \mid f(x) \le 0\}$$ , $$\{x\in \mathbb {R}^n \mid f(x) = 0\}$$ , $$\{x\in \mathbb {R}^n \mid f(x) \ge 0\}$$ , $$\{x\in \mathbb {R}^n \mid f(x) > 0\},$$ we derive conditions on the coefficients $$(A, a, a_0)$$ for each of the five level sets to be disconnected with exactly two connected components, say $$L^{-}$$ and $$L^{+}$$ . Once so, we are interested in, when the two connected components can be separated by another quadratic level set $$\{x\in \mathbb {R}^n \mid g(x) = x^T B x + 2b^T x + b_0 = 0\}$$ such that $$L^{-} \subset \{x\in \mathbb {R}^n \mid g(x) < 0\}$$ and $$L^{+} \subset \{x\in \mathbb {R}^n \mid g(x) > 0\}$$ . It has been shown that the particular case for $$\{x\in \mathbb {R}^n \mid g(x) = 0\}$$ to separate $$\{x\in \mathbb {R}^n \mid f(x) < 0\}$$ is equivalent to the $$\mathcal {S}$$ -lemma with equality, and thus answers the strong duality for $$\min \{f(x) \mid g(x) = 0\}.$$ In addition, the case when $$\{x\in \mathbb {R}^n \mid g(x) = 0\}$$ separates $$\{x\in \mathbb {R}^n \mid f(x) = 0\}$$ is closely related to the convexity of the joint range for a pair of quadratic functions (f, g). This paper completes the characterization for all five cases of separation, namely, for $$\{x\in \mathbb {R}^n \mid g(x) = 0\}$$ to separate $$\{x\in \mathbb {R}^n \mid f(x) \star 0\}$$ where $$\star \in \{<, \le , =, \ge , >\}$$ , which is expected to provide a new tool in solving quadratic optimization problems.

Tài liệu tham khảo

Boyd, S., Boyd, S.P., Vandenberghe, L.: Convex Optimization. Cambridge University Press (2004) Cui, G., Yu, X., Foglia, G., Huang, Y., Li, J.: Quadratic optimization with similarity constraint for unimodular sequence synthesis. IEEE Trans. Signal Process. 65(18), 4756–4769 (2017) Falk, J.E., Dandurova, Y., Yeganova, L.: Set separation problems and global optimization. Nonlinear Anal. Theory Methods Appl. 47(3), 1857–1867 (2001) Finsler, P.: Über das Vorkommen definiter und semidefiniter Formen in Scharen quadratischer Formen. Commentarii Mathematici Helvetici 9(1), 188–192 (1936–1937) Flores-Bazán, F., Opazo, F.: Characterizing the convexity of joint-range for a pair of inhomogeneous quadratic functions and strong duality. Minimax Theory Appl. 1, 257–290 (2016) Hiriart-Urruty, J.-B., Lemar\(\acute{\rm e}\)chal, C.: Fundamentals of Convex Analysis. Springer, Berlin Heidelberg (2004) Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press (2012) Liu, F., Shi, L., Huang, X., Yang, J., Suykens, J.A.: Analysis of regularized least-squares in reproducing kernel Kreĭn spaces. Mach. Learn. 110, 1145–1173 (2021) Luo, Z.Q., Ma, W.K., So, A.M.C., Ye, Y., Zhang, S.: Semidefinite relaxation of quadratic optimization problems. IEEE Signal Process. Mag. 27(3), 20–34 (2010) Nguyen, H.Q., Chu, Y.C., Sheu, R.L.: On the convexity for the range set of two quadratic functions. J. Ind. Manag. Optim. 18(1), 575–592 (2022) Nguyen, H.Q., Sheu, R.L.: Geometric properties for level sets of quadratic functions. J. Glob. Optim. 73, 349–369 (2019) Nguyen, H.Q., Sheu, R.L.: Quadratic optimization problems with non-crossover and non-separable constraint boundaries. Preprint submitted (2021) Nguyen, H.Q., Sheu, R.L., Xia, Y.: Deciding whether two quadratic surfaces actually intersect. Preprint at arXiv:2012.10318 (2021) Nguyen, H.Q., Sheu, R.L.: Separation properties of quadratic functions. https://doi.org/10.13140/RG.2.2.18518.88647 (2020) Polik, I., Terlaky, T.: A survey of the S-lemma. SIAM Rev. 49, 371–418 (2006) Polyak, B.T.: Convexity of quadratic transformations and its use in control and optimization. J. Optim. Theory Appl. 99(3), 553–583 (1998) Qi, Y., Jin, L., Luo, X., Zhou, M.: Recurrent neural dynamics models for perturbed nonstationary quadratic programs: a control-theoretical perspective. IEEE Trans. Neural Netw. Learn. Syst. 33(3), 1216–1227 (2021) Xia, Y., Wang, S., Sheu, R.L.: S-lemma with equality and its applications. Math. Program. 156(1), 513–547 (2016) Yakubovich, V.A.: \(\cal{S} \)-procedure in non-linear control theory. Vestnik Leningrad. Univ. Math. 4, 73–93 (1971). (in Russian)