On the Projection-Based Convexification of Some Spectral Sets

Let $(\mathbb{E},\langle{\cdot},{\cdot}\rangle)$ be a finite-dimensional real inner-product space and $\emptyset\neq\mathcal{K}\subseteq\mathbb{R}^{n}$ be a closed and convex cone. Consider a function $\lambda:\mathbb{E}\to\mathcal{K}$ that satisfies the following two properties:

1. (P1)

   For all $x,y\in\mathbb{E}$, we have $\langle{x},{y}\rangle\leq\langle{\lambda(x)},{\lambda(y)}\rangle:=\sum_{i=1}^{n}\lambda_{i}(x)\lambda_{i}(y)$.

2. (P2)

   For all $\mu\in\mathcal{K}$ and $y\in\mathbb{E}$, there exists $x\in\mathbb{E}$ such that $\lambda(x)=\mu$ and $\textstyle\langle{x},{y}\rangle=\langle{\lambda(x)},{\lambda(y)}\rangle.$

(In particular, $\lambda$ is surjective with range $\mathcal{K}$.) We call $\lambda:\mathbb{E}\to\mathcal{K}$ a spectral map. Given $\lambda$ and a nonempty set $\mathcal{C}\subseteq\mathbb{R}^{n}$, we can define the following spectral set (associated with $\lambda$ and $\mathcal{C}$):

The aim of this paper is to provide projection-based characterizations of $\mathsf{clconv}\,\mathcal{S}$ under different structural assumptions of $\lambda$, $\mathcal{C}$ and $\mathcal{K}$. To avoid triviality, throughout this paper we assume the set $\mathcal{C}$ to be feasible, namely $\mathcal{C}\cap\mathcal{K}\neq\emptyset$.

The definition above suggests that the triple $(\mathbb{E},\mathbb{R}^{n},\lambda)$ is a generalized version of the (finite dimensional) FTvN system, which was initially proposed in the seminal work [5]. Specifically, the original definition of the FTvN system requires the spectral map $\lambda$ to be isometric, namely, $\|x\|=\|\lambda(x)\|_{2}$ for all $x\in\mathbb{E}$, where $\|\cdot\|$ is induced by the inner product $\langle{\cdot},{\cdot}\rangle$ on $\mathbb{E}$. In this work, we relax this requirement to requiring the range of $\lambda$ (namely, $\mathcal{K}$) to be a closed and convex cone, which is a consequence of the isometry property as well as (P1) and (P2). The FTvN system subsumes two fairly general systems, namely the normal decomposition system [9] and the system induced by complete and isometric (c.i.) hyperbolic polynomials [1], both of which include many important special cases. To elaborate the latter, let $p:\mathbb{E}\to\mathbb{R}$ be a degree-$n$ homogeneous polynomial that is hyperbolic with respect to (w.r.t.) some direction $d\in\mathbb{E}$, namely, $p(d)\neq 0$ and for all $x\in\mathbb{E}$, the univariate polynomial $t\mapsto p(td-x)$ has only real roots, which are denoted by $\lambda_{1}(x)\geq\cdots\geq\lambda_{n}(x)$. In [1], it was shown that if $p$ is complete and isometric, then the characteristic map of $p$ (w.r.t. $d$), namely, $x\mapsto(\lambda_{1}(x),\ldots,\lambda_{n}(x))$ for $x\in\mathbb{E}$, is indeed an isometric spectral map. A notable special case of such a characteristic map is the eigenvalue map on a Euclidean Jordan algebra of rank $n$, which in turn includes the eigenvalue map on the vector space of $n\times n$ real symmetric matrices $\mathbb{S}^{n}$ as a special case. (The eigenvalue map on $\mathbb{S}^{n}$ is given by $X\mapsto(\lambda_{1}(X),\ldots,\lambda_{n}(X))$, where $\lambda_{1}(X)\geq\ldots\geq\lambda_{n}(X)$ are the eigenvalues of $X\in\mathbb{S}^{n}$.) Beyond the system induced by c.i. hyperbolic polynomials, the FTvN system also includes the system induced by the singular-value map $\sigma:\mathbb{R}^{m\times n}\to\mathbb{R}^{l}$ for $l:=\min\{m,n\}$. Here $\sigma(X):=(\sigma_{1}(X),\ldots,\sigma_{n}(X))$ for any $X\in\mathbb{R}^{m\times n}$ with singular values $\sigma_{1}(X)\geq\cdots\geq\sigma_{l}(X)\geq 0$. In addition, when $\mathbb{E}=\mathbb{R}^{n}$, examples of the FTvN system include the systems induced by the reordering, absolute-value and absolute-reordering maps. For details and more examples, we refer readers to [4, Section 4].

The spectral set $\mathcal{S}$ appears as the spectral constraints in many optimization problems, where $\lambda$ can take various forms, including the absolute-reordering map on $\mathbb{R}^{n}$ [8], the eigenvalue map on $\mathbb{S}^{n}$ [3, 10] or more generally on a Euclidean Jordan algebra of rank $n$ [6], and the singular-value map on $\mathbb{R}^{m\times n}$ [10]. Recently, some works [5, 6] pioneered the study of the optimization problems with spectral constraints $\mathcal{S}$ defined by the isometric spectral map in the FTvN system, which unifies and generalizes all the aforementioned forms of $\lambda$. Indeed, optimization problems of this form not only possess great generality, but also enjoy many attractive properties for algorithmic development.

Despite the important role that $\mathcal{S}=\lambda^{-1}(\mathcal{C})$ plays in optimization, to our knowledge, the study of $\mathcal{S}$ has mainly focused on the setting where $\mathcal{C}$ has certain invariance properties [9, 8, 7]. Indeed, the proper notion of invariance depends on the spectral map $\lambda$. For example, if $\lambda$ is the eigenvalue (resp. singular-value) map, then the corresponding notion of invariance is the permutation- (resp. permutation- and sign-) invariance. More generally, in the normal decomposition system, the invariance of $\mathcal{C}$ is defined w.r.t. some closed group of orthogonal transformations on $\mathbb{R}^{n}$ [9], and in the FTvN system, the invariance is defined via a $\lambda$-compatible spectral map on $\mathbb{R}^{n}$ [4] (see Definitions 2.1 and 2.2 for details). When $\mathcal{C}$ is invariant (in some proper sense), from the seminal works [9, 8, 7], we know that $\mathcal{S}$ is closed and convex if and only if $\mathcal{C}$ is closed and convex [9, 7], and furthermore, $\mathsf{clconv}\,\mathcal{S}=\lambda^{-1}(\mathsf{clconv}\,\mathcal{C})$ [8, 7]. On the other hand, there also exist simple examples demonstrating that for a general set $\mathcal{C}$ without any invariance property, $\mathcal{S}$ may not be convex even if $\mathcal{C}$ is. This leads to the main question that we aim to address in this work:

Apart from addressing the main question above, a side goal of this work is to establish alternative characterizations of $\mathsf{clconv}\,\mathcal{S}$ when $\mathcal{C}$ is invariant in the context of FTvN system (cf. Definitions 2.1 and 2.2). Although the result $\mathsf{clconv}\,\mathcal{S}=\lambda^{-1}(\mathsf{clconv}\,\mathcal{C})$ in [7] is simple and elegant, sometimes $\mathsf{clconv}\,\mathcal{C}$ is complicated and difficult to describe, even though $\mathcal{C}$ itself admits a simple description (see Remark 2.5). Therefore, we aim to characterize $\mathsf{clconv}\,\mathcal{S}$ in certain ways that do not involve $\mathsf{clconv}\,\mathcal{C}$, and hopefully in some cases, these new characterizations admit simpler descriptions compared to $\lambda^{-1}(\mathsf{clconv}\,\mathcal{C})$.

First, we derive projection-based characterizations of $\mathsf{clconv}\,\mathcal{S}$, where $\mathcal{S}:=\lambda^{-1}(\mathcal{C})$ is defined by a class of sets $\mathcal{C}$ that do not have any invariance property, but instead satisfy some other relatively mild assumptions (see Theorem 2.1 and Corollary 2.1 for details). Our approach is based on a simple idea, namely characterizing the bipolar set of $\mathcal{S}$. Despite its simplicity, this idea allows us to judiciously exploit (P1) and (P2) through convex dualities. To our knowledge, our approach is the first one for characterizing $\mathsf{clconv}\,\mathcal{S}$ without leveraging the invariance properties of $\mathcal{C}$.

Second, we consider the setting where a $\lambda$-compatible spectral map $\gamma$ exists on $\mathbb{R}^{n}$ and $\mathcal{C}$ is $\gamma$-invariant (cf. Definitions 2.1 and 2.2). (Indeed, this notion of invariance is fairly general, and includes many common notions of invariance as special cases, e.g., permutation- and sign-invariance.) Under this setting, we derive a projection-based characterization of $\mathsf{clconv}\,\mathcal{S}$, which is complementary to the characterization $\lambda^{-1}(\mathsf{clconv}\,\mathcal{C})$ [7]. We demonstrate that in some cases, our characterization admits a simpler description compared to $\lambda^{-1}(\mathsf{clconv}\,\mathcal{C})$ (cf. Remark 2.5). In addition, our result unifies and extends the related results in [8] established for certain special cases of $\lambda$ and $\mathcal{C}$.

We start by introducing some preliminary convex analytic facts, which can be found in Rockafellar [11, Sections 12–14]. For any nonempty set $\mathcal{U}\subseteq\mathbb{R}^{n}$, define its support function $\sigma_{\mathcal{U}}(y):=\sup_{x\in\mathcal{U}}\;\langle{y},{x}\rangle$ for $y\in\mathbb{R}^{n}$. It is clear that $\sigma_{\mathcal{U}}$ is proper, closed, convex and p.h. In addition, for any $x_{0}\in\mathbb{R}^{n}$, we have $\sigma_{\mathcal{U}-x_{0}}(y)=\sigma_{\mathcal{U}}-\langle{y},{x_{0}}\rangle$ for all $y\in\mathbb{R}^{n}$. We also denote the indicator function of $\mathcal{U}$ by $\iota_{\mathcal{U}}$, such that $\iota_{\mathcal{U}}(x):=0$ for $x\in\mathcal{U}$ and $\iota_{\mathcal{U}}(x):=+\infty$ otherwise. For any proper function $f:\mathbb{R}^{n}\to\overline{\mathbb{R}}:=(-\infty,+\infty]$, define its Fenchel conjugate

It is clear that $\sigma_{\mathcal{U}}=\iota_{\mathcal{U}}^{*}$, and if $\mathcal{U}$ is closed and convex, we also have $\iota_{\mathcal{U}}=\sigma_{\mathcal{U}}^{*}$. Let $\mathcal{U}^{\circ}$ denote the polar set of $\mathcal{U}$, which is defined as

We define $\mathcal{U}^{\circ\circ}:=(\mathcal{U}^{\circ})^{\circ}$, which we call the bipolar set of $\mathcal{U}$. An important fact about $\mathcal{U}^{\circ\circ}$ is that

• Proof

  Indeed, by definition,

  $$(\mathcal{S}-x_{0})^{\circ}:=\{y\in\mathbb{E}:\sigma_{\mathcal{S}-x_{0}}(y)\leq 1\}=\{y\in\mathbb{E}:\sigma_{\mathcal{S}}(y)\leq 1+\langle{y},{x_{0}}\rangle\}.$$

  (3.5)

  Since we can write $\mathcal{S}=\{x\in\mathbb{E}:\lambda(x)\in\mathcal{D}\}$, from Lemma 3.1, we have

  	$\displaystyle\sigma_{\mathcal{S}}(y):={\sup}_{x\in\mathbb{E}}\;\{\langle{y},{x}\rangle:\lambda(x)\in\mathcal{D}\}$	$\displaystyle={\sup}_{\mu\in\mathbb{R}^{n}}\;\{\langle{\lambda(y)},{\mu}\rangle:\mu\in\mathcal{D}\}$
  		$\displaystyle=-{\inf}_{\mu\in\mathbb{R}^{n}}\;-\langle{\lambda(y)},{\mu}\rangle+\iota_{\mathcal{K}}(\mu)+\iota_{\mathcal{D}}(\mu).$		(3.6)

  Since $\iota_{\mathcal{D}}^{*}=\sigma_{\mathcal{D}}$ and the Fenchel conjugate of the function $x\mapsto-\langle{\lambda(y)},{\mu}\rangle+\iota_{\mathcal{K}}(\mu)$ is $z\mapsto\sigma_{\mathcal{K}}(\lambda(y)+z)=\iota_{\mathcal{K}^{\circ}}(\lambda(y)+z)$ for $z\in\mathbb{R}^{n},$ we can write down the Fenchel dual problem of (3.6) as follows:

  $${\inf}_{z\in\mathbb{R}^{n}}\;\sigma_{\mathcal{D}}(z)+\iota_{\mathcal{K}^{\circ}}(\lambda(y)-z)={\inf}_{z\in\mathbb{R}^{n}}\;\{\sigma_{\mathcal{D}}(z):\lambda(y)-z\in\mathcal{K}^{\circ}\}.$$

  (3.7)

  Note that since $\mathcal{D}\neq\emptyset$ is convex, we always have $\mathsf{ri}\,\mathcal{D}\cap\mathcal{K}\neq\emptyset$ (since $\emptyset\neq\mathsf{ri}\,\mathcal{D}\subseteq\mathcal{K}$). In addition, if $\mathcal{C}\cap\mathsf{ri}\,\mathcal{K}\neq\emptyset$, then $\mathsf{ri}\,\mathcal{D}\cap\mathsf{ri}\,\mathcal{K}\neq\emptyset$ (otherwise, since $\mathsf{ri}\,\mathcal{D}\subseteq\mathcal{K}$, we have $\mathsf{ri}\,\mathcal{D}\subseteq\mathsf{rbd}\,\mathcal{K}$ and hence $\mathcal{D}=\mathcal{C}\cap\mathcal{K}\subseteq\mathsf{rbd}\,\mathcal{K}$, contradicting $\mathcal{C}\cap\mathsf{ri}\,\mathcal{K}\neq\emptyset$). Now, using classical results on Fenchel duality (see e.g., [11, Theorem 31.1]), if $\mathcal{K}$ is polyhedral or $\mathcal{C}\cap\mathsf{ri}\,\mathcal{K}\neq\emptyset$, we know that strong duality holds between (3.6) and (3.7), and the infimum in (3.7) is attained. Consequently, from (3.5), we know that $y\in(\mathcal{S}-x_{0})^{\circ}$ if and only if

  $${\min}_{z\in\mathbb{R}^{n}}\;\{\sigma_{\mathcal{D}}(z):\lambda(y)-z\in\mathcal{K}^{\circ}\}=\sigma_{\mathcal{S}}(y)\leq 1+\langle{y},{x_{0}}\rangle.$$

  $\square$

  $\square$