Return to 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\geq0 \\ & \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} \geq 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.

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.

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\geq0\end{align}

This problem is convex, 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).

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.

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\geq0 \\ & \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} \geq 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.

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

$$\min_x \|x-x_k\|_2^2$$ $$\mathrm{s.t. }\ \max_{T\in\mathcal{T}} \sum_i \frac{t_i}{x_i} - f(t)^2\geq0$$

This problem is convex, 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).

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

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\geq0\end{align}

This problem is convex, 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).

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.