$\min f(x)=\frac{1}{2}x^t Bx + c^t x$ subject to $Ax=b, x\ge 0$ then $f(\overline{x})=\frac{1}{2}(c^t\overline{x}+b^t\overline{\lambda})$

305 Views Asked by At

$$\min f(x)=\frac{1}{2}x^t Bx + c^t x\\\mbox{s.t.} \\Ax=b\\ x\ge 0$$

Let $\overline{x}$ be a regular solution of the problem and $\overline{\lambda}$ the vector of Lagrange Multipliers associated to the equality restrictions.

Prove that $f(\overline{x})=\frac{1}{2}(c^t\overline{x}+b^t\overline{\lambda})$

This problem is the same as

$$\min f(x)=\frac{1}{2}x^t Bx + c^t x\\\mbox{s.t.} \\Ax-b\le 0\\ -x\le 0$$

I can't use advances method like KKT or whatever, so to solve problems with inequality constraints I must create a matrix with all the inequalities and analyze the intersection points. That is, the points $x$ such that $a_ix-b_i= 0$ and $a_jx-b_j= 0$ for some $i$ and $j$ or that $a_ix-b_i= 0$ and $-x\le 0$. I must investigate if the points $x$ in the intersection are written like this: $\nabla f(x) = B_I\lambda$, where $B$ is the matrix of all inequalities, and $B_I$ is the submatrix of $B$ that contains only the inequalities of the intersection.

However I have some questions. The minimum point will always be in the intersections? If it's true, how do I arrive at the final result? If $\overline{x}$ is a point in the intersection of two inequalities and satisfy $\nabla f(\overline{x})=B_I\overline{\lambda}$ for negative $\lambda_i$ for all $i$ then how $f(\overline{x})=\frac{1}{2}(c^t\overline{x}+b^t\overline{\lambda})$?

1

There are 1 best solutions below

4
On BEST ANSWER

The KKT conditions are: if $x$ reaches $\min(f)$, then there are $2$ vectors $\lambda,\mu$ s.t.

$Bx+c=A^T\lambda+\mu$ and satisfying the relations $x_i\mu_i=0$ (also $\mu$ has a constant signum, that here is useless).

Thus $x^TBx+x^Tc=x^TA^T\lambda+x^T\mu=b^T\lambda$.

Then $f(x)=1/2x^TBx+c^Tx=1/2c^Tx+1/2b^T\lambda$.