All right, now I'm gonna uh,
show you how to solve the constrained least squares problem.
Um, actually, it's gonna turn out to be very much like the least squares problem.
Uh, then we will reduce it to something that involves our old friend,
the QR factorization for solving linear equations.
Now let's see how that works.
So we'll start with a derivation uh, from uh, calculus.
Um, that is if you remember this,
but it- actually after this,
I'm gonna give you a derivation which frankly I find much clear and is much simpler.
So- um, we'll start with this one because it's traditional, and after all,
most of you or many of you were already tortured by- you know,
by taking- having to take a calculus class.
And so we might as well go back and- and use- use what you learned there.
Okay. So um, what calculus is,
is something like this.
It says, if you want to solve this optimization problem here, uh,
then what you're gonna do is you're going to produce something called
the Lagrangian function that's named after a famous mathematician named Lagrange.
In fact, I think his name already came up once
already in Lagrange polynomials for example.
Okay? And what the Lagrangian is this- is this is,
you introduce these numbers,
z_1 up to z_p.
Now, these are called the Lagrange multipliers.
Um, and it says that you should take the objective function here and you should add,
that's the constraint because these are that- these are the constraint residuals,
these things, c1 transpose X1 is D1 into Cp transpose X1 is dp.
And we multiply those by the Lagrange multiplier,
and that's the Lagrangian.
Okay? Now, anyway then- then what you're told is this,
is the optimality conditions are simply this.
You take the partial derivative of the Lagrangian with respect to xi, that has to be 0.
And the partial derivative with respect to all the z_i's have to be 0.
Okay? So I actually remember being
taught this and having absolutely no clue what it meant.
I don't know that I actually really learned it until maybe I was
in grad school or something like that to really get it.
Now in this class we're not going to get- we're not
gonna get into what it really- what it is.
So we're not gonna do that.
But you know, if you take a course on optimization,
maybe- maybe at that point this will become clear.
And in fact, it's funny because it's actually normally just
taught as a set of behaviors or tips.
It's like you want to solve that, fine.
Form a Lagrangian, set the partial of z equal to 0.
And if you ask why, they're like, just do it.
So- okay. That's- that was my experience anyway.
So if you feel the same way, that's fine.
Okay. So let's look at these conditions.
Well, the first one says I should take the partial- the second one I
should say it takes the partial with respect to zi and set it equal to 0.
And if I take the partial derivative with respect to say z1,
I simply get c1 transpose x minus D1 is 0.
Okay? So I get these u, but we knew that, right?
That's the constraint. That's- so we knew that- okay?
So the second set group of equality is the partial derivative of L with respect to
the z i's is just basically reaffirming
that we have to choose something that is feasible.
Okay? Now the first n equations,
those are more interesting.
That's the partial derivative of L with respect to xi.
And when you go back and work out what it is,
we have to take the partial derivative of L with respect to xi.
And you can see there's contributions in here,
but there's also a contribution in here.
And that's actually a calculation we did before.
I'm not gonna do it right now,
but it turns out to be exactly this.
It's two times the sum of a transpose Aij x hat j minus 2A- A transpose b_i plus this.
These are the terms that come from those other terms-
the other terms where the dual variables are the Lagrange multipliers.
That's this thing, okay?
In matrix vector form,
you get this equation that is going to be,
that's the second set of equations that
have to be satisfied if- you know when you take the partial derivatives of a Lagrangian.
Okay? So [NOISE] this one I can write as cx hat equals D. And this one I write this way.
And now what I'm gonna do is I'm going to
collect this equation- equation- system of equations,
this set of equations.
And I'm going to collect them into one big equation for both variables,
the x hat and the z.
Now the truth is,
we don't care about the z. I mean- I mean in some applications you do care about the z,
but that's beyond the scope of this course. We don't care about z.
So z is just something you have to calculate in order to get x hat. So that's fine.
So what we'll do is we'll calculate x hat and z,
and then we'll just throw away z and use x hat.
So all right. So let's say that I've done this
correctly when I stack these two equations.
Well, the bottom equation is C. These are blocked multiplications I'm doing now.
Cx hat 0 times z is d. So the bottom one just says is this, okay?
The top one is to a transpose Ax hat plus c transpose z equals to a transpose b.
Hey, that's exactly this.
Okay? So this- this- this- this set of
equations here expresses basically these Lagrange conditions,
the Lagrange conditions are, well,
these things written out in a general form that the partial with respect to x I is 0,
partial with respect to zi 0.
Okay? And we get this,
and these equations [NOISE] have a name.
They are called the KKT for Karush-Kuhn-Tucker.
These are three mathematicians and who did some work on this.
Actually, what they did was something much more
sophisticated with inequality constraints.
But nevertheless, we would call these the KKT or Karush-Kuhn-Tucker conditions.
Now. And that's a square set of
N plus P linear equations in the variables which indeed have
size n plus p. So that's a square set of n plus b equations with n plus p variables.
And one very good way to think of this equation is
a generalization of the normal equations for least squares to constrained least squares.
So remember that the normal equations were something like a transpose Ax hat.
You know, equals A transpose b. That- these are the normal equations.
And that's actually- that's- what this equation comes down
to if you remove C. I mean, that's what it is.
You divide by 2 as well.
So- so you can think of this as,
this is- this is the KKT equations are
the extension of the normal equations to constrained least squares, right?
So that's what this is.
And these are called the optimality conditions, or something like that.
Okay? By the way,
this is very cool because what we've done is we have
reduced solving a problem that we didn't know how to solve,
which is a constrained least squares problem to one we do know how to solve,
which is solving linear equations, right?
So [NOISE] that's- that's- that's a- that's kind of our trick.
And truth is we kinda did it with least squares as well.
So- okay.
Now, assuming that that KT- KT matrix is invertible,
then you just solve for x hat and z.
You do something like this.
Um, and that's the solution.
Now we don't care about z, but we do get x-hat and that's great.
So we have a way now to solve- to solve constrained least squares problems.
Now, one simple method simply takes that matrix and just solves it,
and which it could do by,
for example, QR factorization of that.
Now you might be interested in when this matrix is invertible,
then that really means when is
your constrained least squares problem sensible, roughly speaking, right?
And I'm not gonna go into the details,
but it comes down to this.
C has linearly independent rows and then a stacked on C has linearly independent columns.
And- and you'll see that this kind of, well, first of all,
it implies something about the sizes of various things, right?
It says that the number of
linear equations has to be less than the dimension of the variable, well.
Sure, okay? In other words,
the cx equals d equations have to be underdetermined or square.
If they're squared, it's a bit silly,
but because you just solve it, then that's your answer.
And the cost of computing it,
there's many ways to do it, one is just to solve for this thing.
And it's basically like n plus p cubed is- is what it is, right?
So um, that's- that's how fast you can compute it.
So okay.
Now, what I wanna do now is give what I think is
a far better derivation of the solution of the constrained least squares problem.
Um, and it uses nothing but like
the most elementary matrix vector notation and deep mathematical concepts like,
you know, the sum of two non-negative numbers is non-negative.
Okay? So- and it also doesn't require any faith.
The truth is, if you go back to this [LAUGHTER] to this story,
this Lagrangian story, um,
we were lucky in that there was only one solution of these, right?
It's the KKT system or something like that.
But in general, uh,
the real story in calculus goes like this,
um, you can find points that satisfy these which are not optimal, right?
So roughly speaking, this Lagrangian method says,
I can give you some candidates and then it's
your job to go figure out if they're actually optimal or not?
That second question, actually a lot of people don't even- the- they forget about that.
Um, here, this will just be a completely independent verification,
very elementary. Goes like this.
[NOISE] So I'm gonna to show you that x hat is a solution.
X hat is- is this one.
It's the one that it's- that it's the x that- it's this one given by this.
I'm gonna show you that's the solution.
Okay, to do that, I'll say,
suppose x is any vector at all that satisfies C x equals d. So you- we would say,
any feasible vector satisfies the equations.
Okay. Then, what I'm gonna do is I'm gonna show you that the norm squared of A x minus b,
is bigger than- is bigger than or equal to the norm squared of A x hat minus b.
And then that'll show immediately that that's the- my x- my alleged x hat,
the solu- my alleged solution x hat is really the solution, okay?
So norm A x minus b. I did the same trick we did with least squares.
Um, I- I take that and I do something silly.
I add A x hat,
um, and I- I add A x hat here.
Okay? And I subtracted, which is silly,
but now I'm gonna use this formula for,
uh, the norm squared of two vectors.
It's the norm squared of the first plus the norm squared of the second,
and then plus 2 times the inner product of the vectors.
So [NOISE] the norm squared of the first is this,
norm squared of the second is that,
um, and then I had this- I had this inner product.
That's the inner product of the two vectors twice in the product.
Okay. Now what we're gonna do is,
we're gonna u- we're now gonna use- so far I
hadn't used anything about x hat, but now I am.
X hat satisfies this equation, right?
Because that-that's the first row of the KKT system.
Okay? That's the second row.
Um, and C x and
C x hat both have to be d because they're both feasible. That's our assumption.
Sorry, x hat is feasible by construction,
x is feasible by assumption.
Okay. So what this says is if I look at this inner product here,
and I work out what that is,
I get 2 x minus x hat transpose here.
I'm- I'm pulling the A out here and then putting it over here to A transpose.
Then I look at A transpose times A x hat minus b,
that's right up here, that's C. And I get this thing.
Um, and then I go over here and I get minus C times x minus x hat.
Now, C x- I can tell you this,
C x is d. C x hat is d,
because they're both feasible.
So C times x minus x hat,
[NOISE] is actually- is d- is actually d minus d. So that's- this thing is 0.
Um, and that says,
this- this thing is just 0. It's just gone.
And then, what this says is that, the norm of
A x minus b squared,
that here, is- it is actually equal to this.
It's the norm of A x hat minus b squared,
plus, and then this thing is non-negative.
So that means that it's bigger than this.
So I'm done.
So we're just kinda cool.
So that's, uh,- that's- it's that simple.
I didn't use any- anything complicated.
So that's a direct verification that
the solution of the constrained least squares problem,
um, is given by this- right, this- this.
It is a formula, but it doesn't matter.
Ah, you- you can compute it.
Um, many things act- actually,
a lot of linear algebra packages would have
a- a function that would solve the constrained least squares problem.
And, well you can write one yourself and it's about two lines long, right?
It just sets up forms the KKT matrix, then, you know,
solves it with, you know,
backslash or something like that.
So okay.
Now let's turn to the least norm problem.
We'll see a b- a beautiful thing emerges and something
pretty cool that ties a lot of the stuff we've seen together.
Um, so the least norm problem says minimize norm x squared subject to C x equals D. Well,
some pretty cool things happen.
Number 1, when we form the KKT matrix,
which is this, um,
it's actually- if assuming C has independent rows,
uh, this matrix is always invertible.
Uh, so because I stacked on top of C,
um, as independent columns, I mean,
of course because of it- if you look at the I on top,
um, we're gonna assume C has independent rows and that says you get this.
Um, now, here, uh,
this system- generally speaking,
when you see a system of equations,
the right thing to do is don't try to solve it by hand.
Mistake. Let a computer do it.
Now, there are exceptions.
Sometimes when something is simple enough,
it- you know, well,
this isn't a case of that.
Um, then it's time to get out your pencil and do some algebra and stuff like that.
Now, um, here, the first equation says basically
2 x hat plus C transpose z, equals 0.
And that tells us that x hat is minus one-half of C transpose z.
Now, the second equation is C x hat equals d,
and I simply plug in this value of x hat and I get this.
Um, that gives me z.
So I know z is minus 2 C C transpose inverse d,
uh, and I plug that into the first equation,
and I end up with this.
Uh, x is equal to C transpose,
times C C transpose inverse times d. But that's our friend,
that's, uh, C remember is wide and this is precisely the pseudo-inverse.
So it says that the solution of the least norm problem is the pseudo-inverse,
times the right-hand side.
That's it. So very cool.
Um, so what this says is,
if a matrix C has linearly independent rows, um, then,
we already saw, well, a while ago,
that's- that the- that the pseudo-inverse of
that matrix is a right inverse of C. We already saw that.
Um, uh, and what that tells you,
you know, is that, for any d at all,
if you plug in x hat equals C dagger d,
that satisfies C x equals d. That's what means to be a,
you know, a- a right inverse, right?
But now we know more.
This is special right inverse.
And it is the right inverse.
It says that x hat,
which is- is a s-solution of C x equals d. It's really cool.
Now we know it's actually the solution with the smallest norm.
So- so it gives you the smallest solution of C x equals d. Um, so it's very nice.
Ties a bunch of stuff we've seen together,
and of course you can compute this by a QR factorization on C transpose, right?
So um, that's all.
So uh, everything sorta ties nicely together.