6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think it may be helpful to specify what the constraint set represents? For example, are you trying to project onto a knapsack constraint? $\endgroup$ – batwing Apr 3 at 4:18
  • 1
    $\begingroup$ Please tell us why the constraint is convex. Looks rather dubious to me $\endgroup$ – Mark L. Stone Apr 3 at 11:32
  • $\begingroup$ Thanks for your interest. I modified the question to answer to address your concern (a large part for convexity). $\endgroup$ – dourouc05 Apr 3 at 17:58
  • 2
    $\begingroup$ 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. $\endgroup$ – Mark L. Stone Apr 3 at 18:21
  • $\begingroup$ Thanks for pointing that out! It was a typo, I checked that again :). $\endgroup$ – dourouc05 Apr 3 at 22:56
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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)… $\endgroup$ – dourouc05 Apr 4 at 0:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.