Nonsmooth constrained convex optimisation: convergence results?

Question

I am working on a projection problem on a very large set of highly related constraints:

\begin{align} \min_x & \quad\|x-x_k\|_2^2 \\ \mathrm{s.t.} & \quad\max_{T\in\mathcal{T}} \sum_i \frac{t_i}{x_i} - f(t)^2\leq0 \\ & \quad x\geq0 & \end{align}

It is quite easy to check whether the constraints are satisfied or to compute a gradient (of either the objective function or the constraint). $\mathcal{T}$ is a quite large set of points (it is a combinatorial set that can be described by $a^Tt\leq b$ with $t\in\{0,1\}^d$, so with $\mathcal{O}(2^d)$ points). I'd rather avoid writing out explicitly all constraints for all $t\in\mathcal T$ (even though that would be a standard smooth convex program).

These tricky constraints come from bandits theory, it's a link between the decisions to take $x$ and the variance $f(t)^2$ for the set of decisions $t$.

This problem is also convex, as it can be equivalently written as:

\begin{align} \min_x & \quad\|x-x_k\|_2^2 & \\ \mathrm{s.t.} & \quad\sum_i \frac{t_i}{x_i} \leq f(t)^2 & \forall T\in\mathcal{T} \subset 2^{\{0,1\}^d} \\ & \quad x\geq0 & \end{align}

The Hessian matrix of the latter constraint is:

\begin{pmatrix} \frac{2t_1}{x_1^3} & 0 & 0 & \cdots & 0 \\ 0 & \frac{2t_2}{x_2^3} & 0 & \cdots & \vdots\\ 0 & 0 & \ddots & \ddots & \vdots & \\ \vdots & \vdots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & 0 & \frac{2t_n}{x_n^3} \end{pmatrix}

As $t_i\in\{0,1\}$ and $x\geq0$, all eigenvalues are always nonnegative.

However, I need to be able to prove that I can solve this in polynomial time (i.e. reach a precision $\varepsilon$ on the objective function with all constraints satisfied within $\mathcal{O}(d/\varepsilon)$ time, probably with higher exponents).

This is why I explored the domain of nonsmooth optimisation (which is not my cup of tea).

• I know I can use methods like an augmented Lagrangian to solve it (as proposed in The proximal augmented Lagrangian method for nonsmooth composite optimization, for instance).
• I could only find theoretical results about the convergence of the methods to the optimum point for the smooth case (for instance, in the book Practical Augmented Lagrangian Methods for Constrained Optimization).
• I have found results for the unconstrained nonsmooth case with subgradients (Theorem 2.8 in The Subgradient Method), but not yet for constrained problems.
• I can across strange results like in Smoothing augmented Lagrangian method for nonsmooth constrained optimization problems with convergence in the case the algorithm never stops… I'm not sure how this could be interesting for me.

Based on the structure of the problem and the KKT conditions, I can find a maximum value for the dual multiplier of the constraint, if this can be useful.

Answer 1

This can be written as a Second Order Cone Problem (SOCP). Whatever you can say about SOCP in general, applies to this problem specifically.

This approach formulates this as a standard SOCP. If it happens to have a large number of constraints, that's the way it is. However, note that it only has a number of SOC constraints equal to the dimension of $x$ (plus one for the objective). The "combinatorial" number of (sum) constraints are all linear (affine).

Each $\frac{t_i}{x_i}$ term can be replaced by $t_iz_i$, using a new variable, $z_i$, combined with the rotated SOC constraint, $$\|1\|^2_2 \le \ z_ix_i, z_i\ge 0, x_i \ge 0$$

Use a linear (in $z_i$) constraint on the sum for each T. That takes care of the max.

As for the objective, change that to u, and add the Second Order Cone Constraint $\|x-x_k\|_2 \le u$.

If you use CVX (or similarly with CVXPY and other similar convex optimization tools), you can use inv_pos(x_i) and let CVX take care of that reformulation under the hood, as well as automatically reformulating the norm in the objective function into an SOCP constraint.