How would I solve the following problem?
$$\min_{x\in\mathbb{R}^n} x^T A x$$ subject to the constraints $$x_i\geq 1,\,i=1,\dots,n,$$
where A is positive semidefinite and symmetric. Is it possible to solve that analytically? In what cases is the solution simply given by $x_1,\dots,x_n=1$?
Thank you!
We can rewrite the problem as follows.
$$\min x^TAx $$ $$ \text{s.t.} 1 - x \le 0 $$
This is a convex optimization problem in standard form, where $1$ is a vector of ones. We write the lagrage function.
$$ L(x,\lambda) = x^TAx + <\lambda, 1 - x> $$ $$ \Leftrightarrow $$ $$ L(x,\lambda) = x^TAx + \lambda - <\lambda, x> $$
Differentiating
$$ \nabla L _X(x,\lambda) = Ax - \lambda $$
We know solution must be where the gradient of the lagragian is zero. so
$$ Ax = \lambda $$
$$ x^* = A^{-1}\lambda $$
And and A is invertible.
Complimentary condition.
$$ \lambda_i( 1 - x_i) = 0 $$
If $x_i = 1$ then we already have the solution for the $i$ if not then $\lambda _i $ would have to be zero. but then the optimiality conidition from before would not hold. So $x_i^* = 1 \forall i$