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

Related videos on Youtube

HavelTheGreat
Author by

HavelTheGreat

Updated on August 01, 2022

Comments

  • HavelTheGreat
    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?

    • HavelTheGreat
      HavelTheGreat about 8 years
      @mvw Oh, my apologies. $c \in \mathbb{R}^{n}$, $C$ is $n \times n$ symmetric, and $A$ is an under-determined system.
    • mvw
      mvw about 8 years
      Is that really $A^T$ in $A^T = QR$?
    • HavelTheGreat
      HavelTheGreat about 8 years
      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}$
    • mvw
      mvw about 8 years
      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.
    • HavelTheGreat
      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
    HavelTheGreat about 8 years
    This is exactly what I was looking for, ahhh. Makes perfect sense, thanks!