# Converting standard constrained optimization problem into an unconstrained one

2,130

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$.

Share:
2,130

Author by

### HavelTheGreat

Updated on August 01, 2022

• 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 $n-m$ variables? What would this new unconstrained problem look like?

@mvw Oh, my apologies. $c \in \mathbb{R}^{n}$, $C$ is $n \times n$ symmetric, and $A$ is an under-determined system.
Is that really $A^T$ in $A^T = QR$?
Yup, since the system is under-determined 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}$
Hm.. 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.