Converting standard constrained optimization problem into an unconstrained one
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 $.
Related videos on Youtube
HavelTheGreat
Updated on August 01, 2022Comments

HavelTheGreat over 1 year
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 $nm$ variables? What would this new unconstrained problem look like?

HavelTheGreat about 8 years@mvw Oh, my apologies. $c \in \mathbb{R}^{n}$, $C$ is $n \times n$ symmetric, and $A$ is an underdetermined system.

mvw about 8 yearsIs that really $A^T$ in $A^T = QR$?

HavelTheGreat about 8 yearsYup, since the system is underdetermined we can't use normal QR factorization, we take the transpose, after which partitioning $Q$ into $(Y,Z)$ where $Y$ represents the first $m$ columns, we can rewrite $A = R^{T} Y^{T}$

mvw about 8 yearsHm.. my idea was to reformulate the constraint $Ax = b$ and add it to $f$ such that we have a new quadratic function with the same minimum, but I am not sure if that works out with the above.

HavelTheGreat about 8 years@mvw Actually, I think that's exactly what I've been trying to do, I just don't know how :P I figured the QR decomposition might be useful because it's mentioned in the book I'm using for reference with respect to this general case, although not shown.


HavelTheGreat about 8 yearsThis is exactly what I was looking for, ahhh. Makes perfect sense, thanks!