Separating disconnected quadratic level sets by other quadratic level sets
Journal of Global Optimization - Trang 1-27 - 2023
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)