1
$\begingroup$

Stumbled across this example in a video:

minimise $x^Tx$

subject to $Ax = b$

first step:

$L(x,\nu) = x^Tx+\nu^T(Ax-b)$

$\nabla_xL(x,\nu) = 2x + A^T\nu = 0 \Rightarrow x = - \frac{1}{2}A^T\nu$

Alright, I'm not used to calculating the gradient like that.

I can see

$\nabla_x x^Tx =\nabla_x(x_1^2,x_2^2,..,x_n^2)^T = (2x_1,2x_2,..,2x_n)^T = 2x$

And

$\nabla_x \nu^Tb = 0$

makes sense, I guess.

I don't immediately see

$\nabla_x\nu ^TAx = A^T\nu$

though.

I can try

$\nabla_x\nu ^TAx = \nabla_x \nu^T\begin{bmatrix}((A^T)_1)^T x\\ ((A^T)_2)^T x\\ ...\\ ((A^T)_n)^T x\end{bmatrix} = \nabla_x[((A^T)_1)^T x\cdot \nu_1 + ((A^T)_2)^T x\cdot \nu_2+ ...+ ((A^T)_n)^T x\cdot \nu_n]$

But apart from my not knowing where to go from here, that also looks very wrong.

So what's happening, here?

And are there calculation rules for vector formulae that one can follow without having to break it down to the individual components?

$\endgroup$
2
$\begingroup$

For

$$L(x,\nu) = x^Tx+\nu^T(Ax-b)$$

with $\partial_i = \partial/\partial x_i$ we have \begin{align} \partial_i L(x, \nu) &= \partial_i \left( \sum_k x_k^2 + \left( \sum_j v_j \sum_k a_{jk} x_k - b_j \right) \right) \\ &= \sum_k \partial_i x_k^2 + \sum_j v_j \sum_k a_{jk}\partial_i x_k - \partial_i b_j \\ &= \sum_k 2 x_k \delta_{ik} + \left( \sum_j v_j \sum_k a_{jk} \delta_{ik} \right) \\ &= 2 x_i + \sum_j v_j a_{ji} \\ &= 2 x_i + \sum_j a_{ij}^T v_j \end{align} or $$ \DeclareMathOperator{grad}{grad} \grad_x L(x, \nu) = 2 x + A^T \nu $$ Note: I usually omit the summations and use Einstein summation convention (summing over indices that occur twice).

$\endgroup$
  • $\begingroup$ Thank you. So I have no choice but to properly break it down to the component level? $\endgroup$ – User1291 Mar 20 '17 at 10:43
  • $\begingroup$ Maybe someone else has a different idea. $\endgroup$ – mvw Mar 20 '17 at 11:06
  • $\begingroup$ @User1291 you break it down to the component level until you can reassure yourself that the direct approach you found in the video actually works. $\endgroup$ – Michael Grant Mar 20 '17 at 15:02

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.