1

I am starting up my Masters after being out of school for awhile and this is my first week back. I am recalling how to complete a problem and I am wondering if anyone can help me get started. I do not need a final answer, just steps needed to complete.

Problem: Solve the following optimization problem using Lagrange multiplier. Express your answer in terms of $A, b,$ and $y$.

minimize $x$, $||x-y||^2$ subject to $Ax=b$

Attempt

$$L(x,\lambda) = ||x-y||^2 + \lambda^T(Ax -b)$$ $$L(x,\lambda) = ||x-y||^2 + \lambda^TAx -\lambda^Tb$$

Now, do I take a partial derivative with respect to $x$? For clarity, below is an image of the problem.

enter image description here

Austin Gaylor
  • 13

1 Answers1

1

I'm not 100% sure, but the derivative of the langrangian with respect to x is $2(x-y)+A^\intercal \lambda=0$ and the derivative with respect to $\lambda$ is $Ax-b=0$.

This solution assumes that y is given and at some point that A is a square matrix, but it should work even if A is not square if the last few steps are omitted.

From the first equation, $x=\frac 1 2 (-A^\intercal\lambda+y)$. Putting this in the second equation,$\frac 1 2 A(-A^\intercal\lambda+y)-b=0$. So $-\frac 1 2 AA^\intercal\lambda+\frac 1 2Ay=b$. So $\lambda=-2(AA^\intercal)^{-1}(b-\frac 1 2 Ay)$. Putting this back in what we got from the first equation, we eventually get $x=\frac 1 2(-A^\intercal(-2)(AA^\intercal)^{-1}(b-\frac 1 2 Ay)+y)=\frac 1 2(2A^{-1}b-y+y)=A^{-1}b$

Vons
  • 11,004