# A tricky optimization problem: writing the dual (using Lagrangian)

I am trying to find the dual problem of the following:$$\min_{θ_v\in\mathbb R^l,b_v\in\mathbb R,ξ_{i,v}\in\mathbb R,λ_{i,k,j}\in\mathbb R}\frac1n\sum_{i=1}^n\left(\sum_{v=1}^mξ_{i,v}+\sum_{k=1}^m\sum_{j=k+1}^mλ_{i,k,j}\right)+\frac12\sum_{v=1}^m\|θ_v\|^2$$such that $$|{\langle\theta_k, x_i^{(k)} \rangle + b_k - \langle\theta_j, x_i^{(j)} \rangle -b_j}| \leq \epsilon + \lambda_{i,k,j}$$

$$y_i (\langle\theta_{v}, x_i^{(v)} \rangle + b_v ) \geq 1 - \xi_{i,v}$$

$$\xi_{i,j} \geq 0$$

$$\lambda_{i,k,j}\geq 0$$

for $$i=1, \dots, n$$, $$k = 1, \dots, m$$ and $$j = k+1, \dots, m$$

We can replace the first condition by

$$({\langle\theta_k, x_i^{(k)} \rangle + b_k - \langle\theta_j, x_i^{(j)} \rangle -b_j})^2 \leq \epsilon + \lambda_{i,k,j}$$ if it helps. We can even look at a very similar problem if the previous one is too hard

$$\min\limits_{\theta_v\in \mathbb R^l, b_v \in \mathbb R, \xi_{i,v} \in \mathbb R, \lambda_{i,k,j} \in \mathbb R} \frac{1}{n} \sum\limits_{i=1}^{n} \left(\sum\limits_{v=1}^{m} \xi_{i,v} + \sum\limits_{k=1}^{m} \sum\limits_{j=k+1}^{m} \lambda_{i,k,j}^2 \right) + \frac{1}{2} \sum\limits_{v=1}^{m} ||\theta_v||^2$$

such that

$${\langle\theta_k, x_i^{(k)} \rangle + b_k - \langle\theta_j, x_i^{(j)} \rangle -b_j} = \lambda_{i,k,j}$$

$$y_i (\langle\theta_{v}, x_i^{(v)} \rangle + b_v ) \geq 1 - \xi_{i,v}$$

$$\xi_{i,j} \geq 0$$

$$\lambda_{i,k,j}\geq 0$$

for $$i=1, \dots, n$$, $$k = 1, \dots, m$$ and $$j = k+1, \dots, m$$

$$\newcommand{\R}{\mathbb{R}}\newcommand{\Minimize}{\operatorname*{Minimize}}$$Let us define the operator $$[{}\cdot{}]_+:\R^n\to\R$$ as

$$[z]_+ = \begin{cases} z, &\text{if } z \geq 0 \\ 0, &\text{otherwise} \end{cases}$$

Then, the optimization problem

$$\Minimize_{x} f(x) + [g(x)]_+,$$

is equivalent to

\begin{align} &\Minimize_{x} f(x) + y \\ &\text{subject to }y \geq 0, g(x) \leq y. \end{align}

One can be seen as the dual of the other.

That said, your optimization problem can be written as (I multiplied the cost by $$n$$ for convenience, but you can undo that)

\begin{align} &\Minimize_{\theta_\nu, b_\nu} \sum_{i,\nu} \left[1 - y_i (\langle \theta_\nu, x_i^{(\nu)}\rangle + b_\nu)\right]_+ \\ &+ \sum_{i,j,k} \left[ |\langle \theta_k, x_i^{(k)}\rangle+b_k - \langle \theta_j, x_i^{(j)}\rangle+b_j| - \epsilon \right]_+ + \tfrac{n}{2}\sum_\nu \|\theta_\nu\|^2. \end{align}

You can in fact think of your problem as the dual of this one (in fact, one if the dual of the other as the cost function is continuous).