Min of Quadratic Function subject to Linear Constraint - Two Variables

Let:

$X = \left[ \begin{matrix} x\\y \end{matrix} \right]$

The optimisation problem can be re-written as follows:

$f(X) = 0.5X^T HX + g^TX + C$

Subject to:

$AX = b$

Where:

$H = \left[ \begin{matrix} 10&3\\3&20 \end{matrix} \right]$ $f = \left[ \begin{matrix} 4\\-20 \end{matrix} \right]$ $A = \left[ \begin{matrix} 1&2\end{matrix} \right]$ $b = 10$ $C = 5$

The matrix $H$ is a positive definite matrix which guarantees the existence of a global minimum to this constrained optimisation problem. This is analogous to the second derivative test in higher dimensions.

Now, the cost function is re-written by introducing a Lagrange multiplier as follows:

$F = 0.5X^T HX + g^TX + C+ \lambda^T (AX-b)$

Computing the gradient of $F$ with respect to the vector $X$ and computing it to zero. Here, zero means the null vector where necessary.

$\nabla F =0\implies HX + A^T \lambda = -f$ $AX = b$

This gives rise to a system of linear equations:

$HX + A^T \lambda = -f$ $AX = b$

Multiplying the first equation by $AH^{-1}$ yields:

$AH^{-1}HX + AH^{-1}A^T \lambda = -AH^{-1}f$ $AX + AH^{-1}A^T \lambda = -AH^{-1}f$ $b + AH^{-1}A^T \lambda = -AH^{-1}f$

$\because AX = b$

$\implies \lambda = -(AH^{-1}A^T)^{-1} (AH^{-1}f+b)$

Plugging the above result in: $HX + A^T \lambda = -f$

Gives:

$X_{opt} = H^{-1}\left( A^T (AH^{-1}A^T)^{-1} (AH^{-1}f+b) - f\right)$

Finally, the minimum value of the function is:

$f_{min} = 0.5X_{opt}^T HX_{opt} + g^TX_{opt} + C = 181.625$

We can use the final two expression, crunch out the matrix multiplications and find the answer. I did this using a computer, for the sake of convenience. Of course, this can be done easily by hand, but I deliberately chose to demonstrate the linear algebra route to generalise the result for a quadratic problem minimisation subject to any number of linear constraints, in any number of variables.

Substituting $x = 10 - 2y$ into $f(x, y)$ , then simplifying, and then completing the square gives:

$5(10 - 2y)^2 + 3(10 - 2y)y + 10y^2 + 4(10 - 2y) - 20y + 50 = 24y^2 - 198y + 590 = 24(y - \cfrac{33}{8})^2 + \cfrac{1453}{8}$

Since the minimum of a square of a real number is $0$ , $f(x, y)$ has a minimum of $\cfrac{1453}{8} = \boxed{181.625}$ .