Was a quotient of two norms considered as a constraint to a convex optimization problem before? I want to solve the optimization problem
$$
\text{minimize }g(x) \quad \text{subject to} \quad \Vert x\Vert_{\infty}/\Vert x\Vert_{2} \le s
$$
for $x\in\mathbb{R}^d$ and $s\in(0,\infty)$.
The function $g:\mathbb{R}^d\to\mathbb{R}$ is (strongly) convex and Lipschitz smooth.
I know, that I could probably try to find saddle points of the corresponding Lagrangian but I would like to know, if there is a faster or more elegant way.
Do you know of a similar problem, that has been considered before?
 A: As @Mark L. Stone commented, that constraint isn't convex (and therefore not a convex optimization problem). You could instead consider the different constraint:
$$\|x\|_{\infty} \leq sM$$
$$\|x\|_{2} \leq M$$
which is convex. Note that the elements $x$ satisfying $\|x\|_{\infty} \leq s \|x\|_2$ and $\|x\|_2 \leq M$ satisfy this constraint. So the solution $\tilde{x}^*$ of this new optimization problem will do at least as well (in terms of the criteria $g$) as the solution $x^*$ of your nonconvex optimization problem as long as $\|x^*\|_{2} \leq M$ (of course, you might be overfitting).
From a practical perspective, I can't imagine there is any loss in using this constraint. Also, this type of constraint has been used in practice (e.g. Lasso/Ridge/ElasticNet regression with a lower/upper bound on the coefficients, bounded Lipschitz regression).
As a note, the nonconvex constraint is only interesting/well-defined if $s \in [1/\sqrt{d},1)$. This is because we always have $\|x\|_{\infty} \leq \|x\|_2$ and $\|x\|_2  \leq \sqrt{d}\|x\|_{\infty} \leq \sqrt{d}s\|x\|_2$. Also, it is not clear to me apriori that the original nonconvex constraint offers any kind of meaningful regularization.
Edit: Actually if you set $s=1/\sqrt{d}$ then the nonconvex constraint is equivalent to $\|x\|_2 = \|x\|_{\infty}$ which implies $x$ has only one nonzero element. So in that sense, it might give sparse solutions for small $s$. This is interesting as $\|\cdot\|_2$ regularization alone only shrinks and does not give sparse solutions.
