# Reformulating absolute-value objective functions to take derivatives

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}$$ and $$\phi > 0, \gamma > 0$$

I am trying to find closed-form solution for this problem. However, before I attempt to write the Lagrangian and proceed to use the KKT conditions to solve for the solution, I believe I need to reformulate the optimization problem (as we cannot take derivatives of the absolute-value function required for the stationarity condition of KKT).

Any help, guidance or reference on how I can proceed to reformulate the problem and subsequently solve for the analytical solution will be very much appreciated.

• So $w_t$ is a variable but $w_{t-1}$ is an input parameter? Apr 5, 2021 at 1:07
• Are the inputs $\gamma \geq 0$? Apr 5, 2021 at 1:18
• @RobPratt yes, $w_{t-1}, \gamma, \phi$ are input parameters. Only $w_t$ is a variable to be optimized over. Do you happen to have any suggestions on how I can proceed to solve for $w_t$?
– vpy
Apr 5, 2021 at 4:10
• @BrianBorchers, yes, $\gamma > 0; \phi > 0$. I have included that in the question. Please let me know if there are any other clarifications I can provide. Any help towards solving for $w_t$ is very much appreciated.
– vpy
Apr 5, 2021 at 4:11
• you can use standard tricks to reformulate this as a linear optimization problem Apr 5, 2021 at 13:54

Introduce variable $$x\in \mathbb{R}^{N}$$ to represent the absolute value, and the resulting linear programming problem is to minimize $$x^T \gamma$$ subject to \begin{align} x &\ge w_t - w_{t-1} \\ x &\ge -w_t + w_{t-1} \\ w_t^T\phi &\le 0.15 \end{align}

In standard form, minimize $$\gamma^T x$$ subject to \begin{align} x - w_t &\ge - w_{t-1} \\ x + w_t &\ge w_{t-1} \\ -\phi^T w_t &\ge -0.15 \end{align}

The dual problem is to maximize $$-w_{t-1}^T\lambda+w_{t-1}^T\theta-0.15\psi$$ subject to \begin{align} \lambda + \theta &= \gamma \\ -\lambda + \theta - \phi \psi &= 0 \\ \lambda &\ge 0\\ \theta &\ge 0 \\ \psi &\ge 0 \end{align}

Alternatively, introduce variables $$x^+, x^-\in \mathbb{R}^{N}$$, and minimize $$(x^++x^-)^T \gamma$$ subject to \begin{align} x^+ - x^- &= w_t - w_{t-1} \\ x^+ &\ge 0 \\ x^- &\ge 0 \\ w_t^T\phi &\le 0.15 \end{align}

• Thanks. To follow up, if using the first approach, the optimization problem becomes: $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$. Hence, the Lagrangian now becomes, $L(x,w_t, \lambda, \theta, \psi) = x^T\gamma - \lambda(x - w_t + w_{t-1}) - \theta(x + w_t - w_{t-1}) - \psi(0.15 - w_t^T\phi)$. With that the KKT conditions are then, Stationary Condition: $\frac{\partial L}{\partial x} = \gamma - \lambda e - \theta e = 0 [1]; \frac{\partial L}{\partial w_t} = \lambda e - \theta e +\psi\phi = 0 [2]$
– vpy
Apr 6, 2021 at 3:45
• Considering the interesting case where the 3rd condition is active, $w_t^T\phi = 0.15 [3]$, I am unsure how I could use [1], [2], [3], to solve for $w_t$. Any help will be very much appreciated. Please feel free to edit your answer with any hints/helps.
– vpy
Apr 6, 2021 at 3:58
• thank you for updating your answer with the duals. It is still not clear to me how I am able to solve for $w_t$ using the duals. I recently posted another question discussing more explicitly on how we could solve for $w_t$. Please feel free to provide your answer there. I am going to accept your answer for this question as this question was mainly posed for reformulation techniques.
– vpy
Apr 6, 2021 at 5:00