Relaxations for the spectral norm maximization problem

Question

Optimizing the spectral norm of some positive semidefinite matrix $A(x) \in S^{n}$, w.r.t. a list of variables $x \in \mathbb{R}^d$ and semidefinite constraints is, in general, a nonconvex problem (ref.: Can one maximize the spectral norm of a matrix via semidefinite programming?)

Example: $$ \max \;\;\left\lVert\begin{pmatrix} 1 & x_1 & x_2\\ x_1 & 1 & x_3 \\ x_2 & x_3 & 1 \end{pmatrix}\right\rVert_2 \\ \text{s.t. } \;\; 0 \leq x_1, x_2, x_3 \leq 1 $$

What other approaches are possible?

For instance, are there relaxations that turn the problem convex (e.g., an upper bounds w.r.t. some quantity that can be optimized). Or can it be modeled as a hierarchy of conditions (as is possible, for example, with polynomial optimization)?

Any reasonably good upper bound would be helpful.

Answer 1

Minimizing a concave function subject to convex constraints is Concave Programming.

If the constraints of a Concave Programming problem are compact, as in your example, there must be a global optimum at an extreme of the constraints. In this example, if any semidefinite constraints are ignored, the extreme point of the constrains are the 8 vertices having $x_i = $ 0 or 1. So evaluating the objective function at all 8 points and picking the largest objective value will produce the global optimum. This is a viable method if the number of variables is not too high.

If there are (also) semidefinite constraints, explicit enumeration of all extreme points will not be possible. However, eliminating the semidefinite constraints constitutes a relaxation of the original problem, and therefore provides an upper bound on the optimal objective value of the original problem. If the optimal solution of the relaxation satisfies the semidefinite constraints, then the solution to the relaxed problem is tight, i.e., solves the original unrelaxed problem. If not, this method does not provide information on how tight the upper bound is. In your particular example, the relaxed problem has optimal objective value 3, achieved at $x_1 = x_2 = x_3 =1$, which produces a positive semidefinite matrix, hence the solution to the relaxed problem solves the original unrelaxed problem.

If you can generate a series of linear (affine) inequalities which constitute a relaxation of one or more of the semidefintie constraints, the above method can still be applied, and may provide a tighter upper bound on the original problem.

Note: If the constraints are not compact and convex, there need not be a global optimum at an extreme of the constraints.