Converting standard constrained optimization problem into an unconstrained one

Question

This question strikes me as if it must be a theorem or something, but I cannot find a good result. I was fiddling with Lagrange multipliers and their use when it comes to converting constrained optimization problems into unconstrained ones, but felt like I was missing the point in what seems to be the general case for the questions in my review, so I pose this question. (This isn't homework, just review).

Consider the quadratic $f : \mathbb{R}^{n} \rightarrow \mathbb{R}$ in standard form $f(x) = c^{T}x + \frac{1}{2} x^{T}Cx$, $b \in \mathbb{R}^{m}$, $A \in \mathbb{R}^{m \times n}$, $m < n$ and $A$ is a full rank matrix. How can we use QR decomposition (i.e. $A^{T} = QR$) to transform the constrained optimization problem $$ \min_{x \in \mathbb{R}^{n}} \{f(x) : Ax=b\}$$ into an unconstrained optimization problem of a quadratic function on $n-m$ variables? What would this new unconstrained problem look like?

Answer 1

Let $ x_0$ be a particular solution to $ Ax = b $ and let $ M $ be a matrix whose columns form a basis of the null space of $ A $. Then every solution to $ Ax = b $ is equal to $ x_0 + My $ for some vector $ y $.

So your optimization problem is equivalent to minimizing $ f (x_0 + My) $ with respect to $ y $, which is an unconstrained problem.

You can express $ M $ in terms of the QR factorization of $ A^T $.

Answer 2

I can't be sure, but what I think what you really want to do is use QR decomposition as a method for solving the system of equations that results from 'standard' dual reformulation and the KKT conditions.

The Lagrangian is $f(x) -\lambda'(Ax-b)$

The KKT conditions are:

$$\nabla f(x) - \lambda'\nabla h(x) = 0 \\ Ax-b = 0$$

Since the gradients form a system of linear equations (since we have a quadratic problem), we can find the optimum by solving this system. This can be done using QR decomposition.

Again, I can't be sure but that's what I think you're out to do...