1
$\begingroup$

I am trying to solve the following optimization problem: $\min_{w_{t}} \frac{1}{2}(w_t - w_{t-1})^T\Lambda(w_t - w_{t-1}) \text{ s.t. } w_t^T\phi\leq 0.15.$
where $w_t, w_{t-1}, \phi \in R^{Nx1}$ and $\Lambda \in R^{NxN}$.

The KKT conditions are then:

  1. $\nabla f = \lambda \nabla g \to \Lambda(w_t - w_{t-1}) + \lambda \phi = 0$
  2. Complementary slackness: $\lambda (0.15-w_t\phi) = 0$
  3. Primary feasibility and dual feasibility

I proceed to try to solve for the solution.
Case 1: $w_t^T\phi < 0.15; \lambda = 0$

  • Solution $w_t = w_{t-1}$

Case 2: $w_t^T\phi = 0.15; \lambda > 0$ [I am unsure on how to proceed for this case.]

  • [1] $w_t^T\phi = 0.15$
  • [2] $\Lambda(w_t - w_{t-1}) + \lambda\phi = 0$

An attempt was to left-multiply [2] by $w_t^T$. Hence, we obtain, $w_t^T\Lambda(w_t - w_{t-1}) + \lambda0.15 = 0$.

But I am not sure how to solve for $w_t$ from $w_t^T\Lambda(w_t - w_{t-1}) + \lambda0.15 = 0$.

Any help, guidance and reference will be very much appreciated. Thank you in advance.

$\endgroup$
2
  • $\begingroup$ Your statement of the problem implies that you are only trying to optimise over the value of $\ w_{t-1}\ $, and therefore that $\ w_t\ $ is *fixed*. Should the problem instead be $$ \min_{w_{\color{red}t}}\frac{1}{2}\big(w_t-w_{t-1}\big)^T\Lambda\big(w_t-w_{t-1}\big)\\ \hspace{-2.5em}\text{subject to }\hspace{2em}w_t^T\phi\le0.1\ . $$ $\endgroup$ Apr 4, 2021 at 4:38
  • $\begingroup$ @lonzaleggiera yes. Thank you for pointing that out. I have edited the post. Any idea on how to proceed for the 2nd case? $\endgroup$
    – vpy
    Apr 4, 2021 at 4:53

1 Answer 1

1
$\begingroup$

You appear to be assuming that $\ \Lambda\ $ is symmetric $\big($otherwise you would have $\ \ \nabla f=\frac{\left(\Lambda+\Lambda^T\right)\left(w_t-w_{t-1}\right)}{2}\ \big)$. Unless $\ \Lambda\ $ is non-negative semi-definite $\ f\ $ will not be bounded below over the space of feasible $\ w_t\ $ and will have no minimum. I therefore assume that it is non-negative semi-definite.

Note that if $\ \phi\not\in\mathscr{R}(\Lambda)\ $, then $\ \phi=\phi_1+\phi_2\ $ with $\ \phi_1\in\mathscr{R}(\Lambda)\ $, $\ \phi_2\in\mathscr{R}(\Lambda)^\perp=\ker(\Lambda)\ $, and $\ \phi_2\ne0\ $. So, if $\ w_t=w_{t-1}-\mu\phi_2\ $, then $\ \frac{\left(w_t-w_{t-1}\right)^T\Lambda\left(w_t-w_{t-1}\right)}{2}=0\ $, and for sufficiently large $\ \mu\ $, $\ w_t\ $ will satisfy the constraint $\ w_t^T\phi<0.15\ $, putting us in Case 1. Likewise, if $\ \phi=0\ $, we are also in Case 1.

Thus, in Case 2, we can assume $\ \phi\ne0\ $ and$\ \phi\in\mathscr{R}(\Lambda)\ $. You can therefore solve the linear equations $$ \Lambda y=\phi $$ for $\ y\ $ and put $\ w_t=w_{t-1}-\lambda y\ $. Since $\ \phi\ne0\ $, then $\ y\not\in\ker(\Lambda)\ $, and we must have $\ y^T\phi=y^T\Lambda y>0\ $. If you now put $$ \lambda=\frac{w_{t-1}^T\phi-0.15}{y^T\phi}\ , $$ then you will have $\ w_t^T\phi=0.15\ $, thus completing the solution of Case 2.

$\endgroup$

You must log in to answer this question.

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