Minimizing convex quadratic with box constraints

709 Views Asked by At

I have the function

$$f(x)=\frac{1}{2}x^TAx - b^T x + c$$

where $A$ is positive semidefinite, and $x\in \mathbb{R}^n$. I know that the minimum of $f(x)$ lies at the solution $x^*=A^{-1}b$. Now, I have box constraints of the form $\mathcal{l}_i \leq x_i \leq \mathcal{u}_i$ for $i=1,\ldots,n$.

Let us replace $x^*_i$ with $l_i$ if $x^*_i < l_i$ or with $u_i$ if $x^*_i >u_i$ for $i=1,\ldots,n$. Let us call such a vector as $y$. Is $y$ a solution to the optimization problem of minimizing $f(x)$ with box constraints ?

1

There are 1 best solutions below

2
On BEST ANSWER

The answer, in general, is NO.

Take $A = \begin{pmatrix}2&1\\1&3\end{pmatrix}$ and $b=(3, -3)^T$. The minimizer of $x^T A x - b^T x$ is $x^*=(1.2, -0.9)^T$.

Adding the constraints $0 \leq x_1,x_2 \leq 1$, the minimizer is $(0.75, 0)^T$, which does not conform to the rule you presented.