Minimize $(x^TWx)$ s.t $||x||_{\infty} \leq 1, ||x||_2 \leq 1$
Probably there are many ways to solve this problem, but I am interested in solving this problem via dual formulation. So I started with this:
$L(x,v,k) = x^TWx +v(||x||_{\infty}-1)+k(||x||_2-1)$
$g(v,k) = \inf_x(L(x,v,k))$
Here I dont know how to minimize this function with respect to $x$. I can differentiate $x^TWx$ and $||x||_2$, but how can I deal with $||x||_{\infty}$?
You can construct various dual formulations, all of them are quite different. First, you can reformulate the problem as was suggested in the comments into $$ \begin{aligned} \min{x} &\quad x^T W x \\ \text{s.t.} &\quad \|x\|_2^2 \leq 1 \\ &\quad x_i^2 \leq 1 & i = 1, \dots, n \end{aligned} $$ And now construct the Lagrangian with the scalar $\lambda \geq 0$ and the non-negative vector $\mu \in \mathbb{R}^n_+$ $$ \begin{aligned} L(x, \lambda, \mu) &= x^T W x + \lambda(\|x\|_2^2 - 1) + \sum_{i=1}^n \mu_i (x_i^2 - 1) \\ &= x^T (W + \lambda I + \operatorname{diag}(\mu))x - \lambda - \sum_{i=1}^n \mu_i \end{aligned} $$ The minimum is $-\infty$ if at least one eigenvalue of $W + \lambda I + \operatorname{diag}(\mu)$ is negative. Otherwise, the minimum is obtained at $x = 0$ and it is $-\lambda - \sum_{i=1}^n \mu_i$. So your dual is a semidefinite program, and I do not see how it is easier than the original.
Another reformulation might be obtained by giving a multiplier only to the constraints $x_i^2 \leq 1$. In that case, the Lagrangian is $$ L(x, \mu) = x^T (W + \operatorname{diag}(\mu)) x - \sum_{i=1}^n \mu_i $$ Minimizing $L$ subject to $\|x\|_2^2 \leq 1$ results in $$ q(\mu) = \lambda_{\min}(W + \operatorname{diag}(\mu)) - \sum_{i=1}^n \mu_i $$ and the minimizer is the eigenvector corresponding to the minimum eigenvalue of $W + \operatorname{diag}(\mu)$. Again, can be reformulated as a semidefinite program, and I do not see how it is easier than the primal problem.
Finally, another approach is adding auxiliary variables $y = x$ and $z = x$, resulting in $$ \begin{aligned} \min_{x, y, z} &\quad x^T W x \\ \text{s.t.} &\quad -x + y = 0 \\ &\quad -x + z = 0 \\ &\quad \|y\|_2 \leq 1 \\ &\quad \|z\|_\infty \leq 1 \end{aligned} $$ In that case, giving a multiplier to the first two constraints, we obtain the Lagrangian $$ L(x, y, z, \lambda, \mu) = x^T W x + \lambda^T(-x + y) + \mu^T(-x + z) = x^T W x - (\lambda^T - \mu^T) x + \lambda^T y + \mu^T z $$ Minimizing the Lagrangian subject to $\|y\|_2 \leq 1$ and $\|z\|_\infty \leq 1$, and noting that we can minimize separately over $x$, $y$ and $z$, we obtain $$ q(\lambda, \mu) = \min_x \{ x^T W x - (\lambda^T - \mu^T) x \} + \min_y \{ \lambda^T y : \|y\|_2 \leq 1 \} + \min_z \{\mu^T z : \|z\|_\infty \leq 1 \} $$ The first minimum is a quadratic function, which is easily obtained, including the minimizer, by comparing the gradient of the term inside $\{ \}$ to zero (if $W$ is positive semidefinite). If $W$ is not PSD, then this dual problem is useless, since the minimum is $-\infty$ regardless of $\lambda$ and $\mu$. The second minimum is $\|\lambda\|_\infty$, while the third is $\|\mu\|_1$, using our knowledge about dual norms of the $\ell_1$ and $\ell_\infty$ norms. This dual might be useful, but is still hard.