Solving optimization with absolute-value objective function using KKT conditions

Question

Given the following optimization problem:
$min_{w_t} |w_t - w_{t-1}|^T\gamma$
s.t. $w_t^T\phi \leq 0.15$
where $w_t, w_{t-1}, \phi, \gamma \in \mathbb{R}^{N\times 1}$;
$w_{t-1}, \phi, \gamma$ are given;
and $\phi > 0, \gamma > 0$

I reformulate this problem as a LP as follows:
$min_{x, w_t} x^T\gamma$
s.t.
$x\geq w_t - w_{t-1}$
$x\geq - w_t + w_{t-1}$
$w_t^T\phi \leq 0.15$
where $x, w_t, w_{t-1}, \phi, \gamma \in \mathbb{R}^{N\times 1}$.

Lagrangian for this problem: $L(x, w_t, \lambda, \theta, \mu) = x^T\gamma - \lambda(x-w_t + w_{t-1}) - \theta(x + w_t - w_{t-1}) - \mu(0.15-w_t^T\phi)$.

In attempt to solve for $w_t$, I list out the KKT conditions.
The stationary conditions are:

1. $\frac{\partial L}{\partial x} = \gamma - \lambda e - \theta e = 0$ [1]
2. $\frac{\partial L}{\partial w_t} = \lambda e - \theta e + \mu\phi= 0$ [2]

The complementary slackness conditions are:

1. $\lambda(x-w_t + w_{t-1}) = 0$ [3]
2. $\theta(x + w_t - w_{t-1}) = 0$ [4]
3. $\mu(0.15-w_t^T\phi) = 0$ [5]

Focusing on the interesting boundary condition of $0.15 = w_t^T\phi$.

I am not sure how to proceed by using [1], [2], [3], [4], [5] to find the solution for $w_t$. Any help is very much appreciated.

Answer 1

From first principles, if $w_{t-1}^T \phi \le 0.15$, then taking $w_t=w_{t-1}$ is optimal, with objective value $0$. Otherwise let $i^*=\arg\min_i \frac{\gamma_i}{\phi_i}$, and an optimal solution is to take $$w_t^i = \begin{cases} w_{t-1}^i &\text{if $i \ne i^*$}\\ \frac{0.15-\sum_{j \ne i^*} \phi_j w_{t-1}^j}{\phi_i} &\text{if $i = i^*$} \end{cases}$$ The resulting optimal $\mu$ is $-\gamma_{i^*}/\phi_{i^*}$. Maybe these hints will help you find $\lambda$ and $\theta$.