Minimize quadratic form with equality constraints

Question

I want to minimize function:

$f(x) = x^T \cdot A \cdot x + b \cdot x$

given constraints:

$B \cdot x = 0$.

Here: $x$ is a vector ($x \in \mathbb{R}^n$), $A$ is a matrix of size $n \times n$, $b$ is a vector of size $n$ and $B$ is a matrix of size $k \times n$ (we have $k$ constraints).

Without constraint this problem is standard optimization problem. I also know that I can reduce this problem to quadratic programming (because $B \cdot x = 0$ is equivalent of $B \cdot x \geq 0$ and $-B \cdot x \geq 0$). But I hope that this problem can be solved in a easier way.

Answer 1

Writing the Lagrangian gives rise to the following optimality conditions

$B x^* =0 $ and $A x^* + b +A^T\lambda^*=0 $.

Rewritten in matrix-form we have

\begin{align} \underbrace{\begin{bmatrix} A&B^T \\B &0 \end{bmatrix}}_{=:K}\begin{bmatrix} x \\ \lambda\end{bmatrix} =\begin{bmatrix} -b \\ 0\end{bmatrix}. \end{align}

If $K$ is non singular then you have a unique, optimal pair $(x^*,\lambda^*)$. Otherwise the quadratic optimization problem is unbounded below or infeasible.

Answer 2

At first, I thought that Nicolas' answer was right, and then I looked at the question again.

For a quadratic program (QP), $A$ is symmetric by convention, and it's possible to re-express it as such, so without loss of generality, suppose that $A$ is symmetric.

If $A$ is also positive semidefinite, then a local optimum is a global optimum, and the KKT conditions that Nicolas cites are both necessary and sufficient for finding a global optimum because the constraints in this particular case are linear.

A counterexample to Nicolas' answer in the case where $A$ is positive semidefinite can be constructed by setting $b = 0$, and setting $B$ and $A$ such that the nullspace of $B$ corresponds to the eigenspace of $A$ with eigenvalue zero. For instance, set

\begin{align} A = \left[\begin{array}{cc}1 & 0 \\ 0 & 0\end{array}\right], \\ B = \left[\begin{array}{cc}1 & 0\end{array}\right], \end{align}

so the problem becomes minimizing $x_{2}^{2}$ such that $x_{1} = 0$. The problem then has an infinite number of optimal solutions (any ordered pair such that $x_{2} = 0$), and the KKT matrix constructed by Nicolas has the form

\begin{align} K = \left[\begin{array}{ccc} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 0\end{array}\right], \end{align}

where $K$ is obviously rank-deficient. (Trivial counterexamples also arise when $B$ is not full rank.)

If $A$ is not positive semidefinite, then the problem is no longer convex. The KKT conditions are still necessary, but not sufficient.

In general, QP solvers for the convex case are efficient and robust, so I would just use a library for that case. The nonconvex case is NP-hard, but there are still really good solvers available, such as CPLEX, which has free licenses for academics.

Answer 3

Quadratic optimization problems with linear equality constraints are pretty simple to solve and a standard problem. Nicolas already gave the correct answer but I'd like to point out that you will find this problem discussed in every textbook on optimization. My favorite is the one by Nocedal and Wright, "Numerical Optimization".