# Nonsmooth constrained convex optimisation: convergence results?

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).

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.

• I think it may be helpful to specify what the constraint set represents? For example, are you trying to project onto a knapsack constraint? – batwing Apr 3 '20 at 4:18
• Please tell us why the constraint is convex. Looks rather dubious to me – Mark L. Stone Apr 3 '20 at 11:32
• Thanks for your interest. I modified the question to answer to address your concern (a large part for convexity). – dourouc05 Apr 3 '20 at 17:58
• No. The constraint inequality is going the wrong direction to be convex, hence my original comment. {convex function} <= constant is convex. {convex function} >= constant is not. I think you can kiss off polynomial time unless you have some nice reformulation. – Mark L. Stone Apr 3 '20 at 18:21
• Thanks for pointing that out! It was a typo, I checked that again :). – dourouc05 Apr 3 '20 at 22:56

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.

• Thanks for your answer. The problem is the very large number of such constraints: it's exponential in the parameter $d$, in the worst case. That also rules out techniques like constraint generation (find the most violated constraint, add it), unless I can find a way to bound the number of constraints to add. I have also tried a similar idea, based on a technique often used in robust optimisation: dualise the max operator, replace it with a minimum, and be done with it. However, this replaces the set $\mathcal T$ with $\mathrm{conv}(\mathcal T)$, and thus returns a useless solution (0)… – dourouc05 Apr 4 '20 at 0:19