0
$\begingroup$

Can anyone derive the update method (2nd equationn of (10) in [1]) in details without using the proximal method? Especially, how does taking the gradient of the dual function wrt "y" yield $\rho(Ax^{k+1}-b)$. [1]: https://i.stack.imgur.com/O610e.png

$\endgroup$
0
$\begingroup$

For a fixed vector $u$, consider the function $r(y) := y^Tu = \sum_i y_i u_i$. Now, for a perturbation $\Delta y$ on $y$, one computes the difference $$\Delta r(y) := r(y + \Delta y) - r(y) = (y + \Delta y)^Tu - y^Tu = \Delta y^Tu = \Delta y^Tu + o(\|\Delta y\|^2). $$

Thus $r$ is smooth at any $y$, with constant gradient $\nabla r(y) = u$. Such a result can be easily read off any standard text on "matrix calculus", but i preferred to do it here from "first principles" so that you may see what's really going on...

Now invoke this fact on your problem with $u = Ax^{k+1} - b$. To conclude, note that a dual gradient ascent step reads: $$\text{new point} = \text{old point} + \text{step size} \times \text{gradient at old point}, $$ i.e $y^{k+1} = y^k + \rho (Ax^{k+1} -b )$.

$\endgroup$
  • $\begingroup$ Thanks! Will think through your answer a little more! $\endgroup$ – CS101 Jan 22 '18 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.