How do I solve for the optimal solution to the maximization problem?

Question

I am trying to solve the following optimization problem:

$$\max_{x} \alpha^T x \text{ subject to } \sum_{n=}^{N} x_n^2 \leq 1$$ Using the Cauchy-Schwarz inequality, I was able to obtain $$\max_{x} \langle\alpha, x\rangle \leq ||\alpha||_2 $$ which means $$\alpha^T x^* = \sqrt{\alpha^T \alpha}$$

My question is, how do you find a solution for $x^*$? Since $x$ is a vector, we can't just divide by $\alpha$ to solve for the optimal solution. I am still very new to optimization, but I think the general idea is that we want to express our objective function in terms of the constraint in order to find an upper bound which I was able to do using Cauchy-Schwarz. I still am unable to determine how to solve for $x$ though. Maybe I'm also a bit rusty on vector algebra. Thanks.

EDIT

I see that equality happens in the Cauchy-Schwarz equation when $x$ is linearly dependent on $\alpha$. Using this fact, I came to the following result, $$x^* = \frac{\alpha}{||\alpha||_2} $$

I believe this logic is correct, but could someone correct me if I am wrong?

Answer 1

With Lagrange multipliers.

$$ L(x,\lambda,s) = \alpha'x+\lambda(\|x\|^2-1+s^2) $$

The stationary points obey

$$ \nabla L = 0 = \cases{\alpha+2\lambda x\\ \|x\|^2-1+s^2 \\ \lambda s = 0} $$

now making $s=0$ (restriction is actuating) we have

$$ \cases{\alpha+2\lambda x = 0\\ \|x\|^2-1 = 0}\ \ \Rightarrow x^* = \pm \frac{\alpha}{\|\alpha\|} $$

etc.

Answer 2

You can use Fenchel's duality scheme and theorem. Using convex conjugates.

Consider the minimization problem

Minimize $-a^{T}x$ subject to $\left\|x \right\|_{2}\leq1$.

Write $P(x)=-a^{T}x$ and $Q(x)=0$ if $\left\|x \right\|_{2}\leq1$ and $-\infty$ otherwise.

Then $min[ P(x)-Q(x)]=max [Q^{\star}(x^{\star})-P^{\star}(x^{\star})]$.

And $P^{\star}$($x^{\star}$)$=sup[x^{\star}x-(-a^{T}x)]=sup[x^{\star}x+a^{T}x]=0$ if $x^{\star}=-a^{T}$ and $+\infty$ otherwise.

Also $Q^{\star}$($x^{\star}$)=$inf$[$x^{\star}x\,:\left\|x \right\|_{2}\leq1]$=$inf[-a^{T}x\,:\left\|x \right\|_{2}\leq1]$.

But $-a^{T}x\geq-\left\|a \right\|\left\|x \right\|\geq-\left\|a \right\|$

and clearly the minimum is attained at $x=\dfrac{a}{\left\|a \right\|}$.

Therefore $Q^{\star}$($x^{\star}$)=$-\left\|a \right\|$. So $max[Q^{\star}-P^{\star}]=-\left\|a \right\|$.

Hence $min[-a^{T}x]=-\left\|a \right\|$. And clearly $-min[-a^{T}x]=max[a^{T}x]=\left\|a \right\|_{2}$.

Therefore the $max$ is $\left\|a \right\|_{2}$ and is attained at $x=\dfrac{a}{\left\|a \right\|_{2}}$.

Another simpler proof is that $a^{T}x\,\leq\,\left\|x \right\|\left\|a \right\|\leq\,\left\|a \right\|$ and hence the max is $\left\|a \right\|_{2}$ and is attained

at $x=\dfrac{a}{\left\|a \right\|_{2}}$.