0
$\begingroup$

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.

Thank you in advance.

$\endgroup$
6
  • 1
    $\begingroup$ So $w_t$ is a variable but $w_{t-1}$ is an input parameter? $\endgroup$
    – RobPratt
    Apr 5, 2021 at 1:07
  • 1
    $\begingroup$ Are the inputs $\gamma \geq 0$? $\endgroup$ Apr 5, 2021 at 1:18
  • $\begingroup$ @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$? $\endgroup$
    – vpy
    Apr 5, 2021 at 4:10
  • $\begingroup$ @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. $\endgroup$
    – vpy
    Apr 5, 2021 at 4:11
  • 2
    $\begingroup$ you can use standard tricks to reformulate this as a linear optimization problem $\endgroup$
    – LinAlg
    Apr 5, 2021 at 13:54

1 Answer 1

0
$\begingroup$

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}

$\endgroup$
3
  • $\begingroup$ 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] $ $\endgroup$
    – vpy
    Apr 6, 2021 at 3:45
  • $\begingroup$ 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. $\endgroup$
    – vpy
    Apr 6, 2021 at 3:58
  • $\begingroup$ 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. $\endgroup$
    – vpy
    Apr 6, 2021 at 5:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .