Minimization of norm distance using SDPs, cone programming, etc.

Question

Building on top of this question Minimization of Frobenius norm using SDPs, I would like to know for what class of norms ($ \Vert \cdot \Vert $ in the following) can we represent the following problem using semidefinite programming (SDP), or cone programming, or some standard optimization problem:

$$ \begin{align*} & \text{min. } \Vert A - X \Vert \\ & \text{s.t. }X \in \mathcal{S} \end{align*} $$

where $A$ is a (symmetric) matrix and $\mathcal{S}$ is some convex set, for which the membership condition can be represented say using SDP constraints.

In particular, I am interested in the following cases:

1. The case where the problem can be represented using SDPs.
2. The norm is the Schatten p-norm.
3. The norm is an Operator norm.

Finally, any reference for dealing with this class of problems would be much appreciated.

Answer 1

A lazy answer would be to simply list the help on norm which lists cases that are supported out of the box in the modelling language YALMIP (which would write these using LP/SOCP/SDP formulations)

 For matrices...
   norm(X)       models the largest singular value of X, max(svd(X)).
   norm(X,2)     is the same as norm(X).
   norm(X,1)     models the 1-norm of X, the largest column sum, max(sum(abs(X))).
   norm(X,inf)   models the infinity norm of X, the largest row sum, max(sum(abs(X'))).
   norm(X,'inf') same as above
   norm(X,'fro') models the Frobenius norm, sqrt(sum(diag(X'*X))).
   norm(X,'nuc') models the Nuclear norm, sum of singular values.
   norm(X,'*')   same as above
   norm(X,'tv')  models the (isotropic) total variation semi-norm 
 For vectors...
   norm(V) = norm(V,2) = standard Euclidean norm.
   norm(V,inf) = max(abs(V)).
   norm(V,1) = sum(abs(V))

In addition to that, you have that $(\sum |x_i|^p)^{1/p}$ is conic representable for $p\geq 0$ (second-order cone, or more conveniently but perhaps slightly more esoteric using the power cone) thus covering arbitrary Schatten p-norms on matrices, as long as you can get that operator to act on a vector which upper bounds a sorted vector of the eigenvalues of $X^TX$ (which you also can through intricate modelling...)

Everything is available in (but hidden well...)

Nesterov, Yurii; Arkadii, Nemirovskii (1995). Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics. ISBN 0898715156.