0

Consider the following problem: $$ \min \mathbf{c}^T\mathbf{x}, \mathbf{x} \in \mathbf{R}^N\\ \mathbf{A}\mathbf{x}=\mathbf{b} $$ where $\mathbf{A}\in\mathbf{R}^{D \times N}, \mathbf{b}\in\mathbf{R}^D$.

I am trying to find the Lagrangian and then the dual. I wrote down: $$ L(\mathbf{x},\mathbf{\lambda},\mathbf{\nu})=\mathbf{c}^T\mathbf{x} + \sum \lambda_i(\mathbf{a}_i^T\mathbf{x}-b_i) $$ where $\mathbf{a}_i$ are the rows of the matrix $\mathbf{A}$. Then the derivative would be: $$ \mathbf{c}+\sum\lambda_i\mathbf{a}_i $$

But this does not depend on $\mathbf{x}$. I am almost sure I made a mistake somewhere in the derivative. How can I find the dual if I cannot replace it in the Lagrangian?

Joe Doe
  • 1
  • For the dual you have to minimize the Lagrangian over $x$. The Lagrangian is linear in $x$. What do you get when you minimize a linear function? – LinAlg Jul 05 '18 at 14:44
  • I get a constant which is what I got here. But then what? Do I set $x$ to $0$? – Joe Doe Jul 05 '18 at 14:47
  • the question wasn't "what do you get when you derive a linear function" – LinAlg Jul 05 '18 at 14:48
  • I get negative infinity? – Joe Doe Jul 05 '18 at 14:49
  • unless the linear function is constant – LinAlg Jul 05 '18 at 14:51
  • Ok I see but now I need to replace $x$ in the Lagrangian. The $x$ that minimizes that would be either infinity or negative infinity depending on the slope of the function. The lagrangian becomes negative infinity now. How can I solve that to get an $x$ that satisfies my constraints – Joe Doe Jul 05 '18 at 14:56
  • you do need to replace $x$, you need to find the value of the lagrangian. And that value is $-\infty$ if $c+\lambda_i a_i \neq 0$. – LinAlg Jul 05 '18 at 15:00
  • Thank you for your answers. It still does not answer my question of how to find $c^Tx$. For example if we have a ridiculously easy problem e.g $\min x: x=2$. I would get the derivative of the lagrangian to be $1+\lambda=0$. Solve for $\lambda$, replace that in my lagrangian and that would give me $L=2$ which is of course the answer to my problem. Here $L$ becomes $-\infty$. I don't think $c^Tx$ is negative infinity, is it? – Joe Doe Jul 05 '18 at 15:34
  • The dual is $\min_x x + \lambda(x-2) = \min_x -2\lambda + (1+\lambda)x$. You cannot solve anything for $\lambda$; the optimization variable is $x$. The minimum is either $-2\lambda$ or $-\infty$. – LinAlg Jul 05 '18 at 16:20

0 Answers0