6

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.

dourouc05
  • 998
  • 7
  • 17
  • 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 03 '20 at 04:18
  • 1
    Please tell us why the constraint is convex. Looks rather dubious to me – Mark L. Stone Apr 03 '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 03 '20 at 17:58
  • 2
    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 03 '20 at 18:21
  • Thanks for pointing that out! It was a typo, I checked that again :). – dourouc05 Apr 03 '20 at 22:56

1 Answers1

3

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.

Mark L. Stone
  • 13,392
  • 1
  • 31
  • 67
  • 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 04 '20 at 00:19