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?



Was a quotient of two norms considered as a constraint to a convex optimization problem before?
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.


