Solving KKT Conditions

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.

• 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\ .$$ Apr 4, 2021 at 4:38
• @lonzaleggiera yes. Thank you for pointing that out. I have edited the post. Any idea on how to proceed for the 2nd case?
– vpy
Apr 4, 2021 at 4:53

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.