1
$\begingroup$

In the book "Sparse and Redundant Representations", the following optimization problem is stated:

$$\min_x J(x) \quad \text{subject to} \quad b=Ax$$

then using Lagrange multipliers, the following Lagrangian has been defined:

$$\mathcal{L}(x)= \parallel x\parallel_2^2+\lambda^T (Ax-b)$$

Where $\lambda$ is the $Lagrange\;multipliers$ for the constraint set.

And the following requirement has been obtained by taking a derivative of $\mathcal{L}(x)$ with respect to $x$:

$$\frac{\partial\mathcal{L}(x)}{\partial(x)}=2x+A^T\lambda$$

  1. My first question is, why in the derivative, we have $A^T\lambda$? Shouldn't it be $\lambda^TA$ instead?

The above optimization problem has been solved differently in the book "Convex Optimization by Stephen Boyd":

For the following optimization problem: $$\min_x f_0(x)\\\text{subject to}\quad h_i(x)=0, \quad i = 1, . . . , p$$

The Lagrangian associated with the above problem is:

$$L(x,\lambda,v)=f_0(x)+\sum_{i=1}^{p}v_ih_i(x)$$

Where $\lambda_i$ is referred to as $Lagrange\;multiplier$ associated with the $i$th inequality constraint $f_i(x) ≤ 0$

  1. Why $Lagrangian$ has been defined differently in the two books?
$\endgroup$
  • $\begingroup$ For question number 1: $\lambda^TA$ doesn't even have the proper dimensions; $2x+\lambda^TA$ would be ill-posed. $\endgroup$ – Michael Grant Sep 6 '16 at 22:14
  • $\begingroup$ Why do you think they've been defined differently? In the first case all you have are equality constraints. In the second you have both inequalities and equations. $\endgroup$ – Michael Grant Sep 6 '16 at 22:15
  • $\begingroup$ Thank you for your comments @MichaelGrant, great help. I still don't understand your answer to question 1, isn't the derivative of $\lambda^TAx$, $\lambda^TA$? $\endgroup$ – Gigili Sep 7 '16 at 1:32
  • $\begingroup$ No, it is not. And again, how could it be added to $2x$ if it were? $\endgroup$ – Michael Grant Sep 7 '16 at 1:50
  • $\begingroup$ Look at it this way: why is the derivative of $x^Tx$ equal to $2x$, and not $2x^T$? $\endgroup$ – Michael Grant Sep 7 '16 at 3:51
1
$\begingroup$

Q1 (already answered by Michael Grant)

The derivative of $\langle \lambda ,A x\rangle $ is $A^T \lambda $. Maybe it becomes clearer if you look at the following:

$$ \langle \lambda , Ax \rangle = \sum_{i=1}^n \lambda_i \sum_{j=1}^m A_{ij} x_j$$

so the $j$th element of the gradient, is the derivative of the above with respect to $x_j$ which is

$$ \sum_{i=1} \lambda_i A_{ij} = (A^T\lambda)_j$$

Q2: For your second question, the two Lagrangians are essentially the same (except that in the first case they only consider an equality constraint while in the second I suspect they consider both equality and inequality (*)). Just write:

$$ h_i(x) = (Ax -b)_i$$

and $\nu_i=\lambda_i$ then, in the first case, you have $\lambda^T(Ax-b) = \sum_{i=1}^p \lambda_i(Ax-b)_i$ and in the second you have $\nu^T(Ax-b) = \sum_{i=1}^p \nu_i(Ax-b)_i = \sum_{i=1}^p \nu_i h_i(x)$, indeed, exactly the same thing.

(*) by the way, your edits are a bit confusing here, (a) either add the sum corresponding to the inequality constraint and leave the sentence below it or (b) remove the sum (as you have done) and the sentence below, and the $\lambda$ in the Lagrangian.

$\endgroup$

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.