Skip to main content
Bounty Ended with 500 reputation awarded by Giskard
fixed some typos
Source Link
Michael Greinecker
  • 13.7k
  • 1
  • 27
  • 38

The Lagrangian is not really symmetric; something that is easier to see if you formulate it without the calculus implementation. First order-order conditions for maxima and minima might look similar, but maxima and minima are very different.

You have the function $f:\mathbb{R}^n\to\mathbb{R}$ you want to maximize, subject to the constraint (written using vector notation) that $G(x)\leq b$ for a function $G:\mathbb{R}^n\to\mathbb{R}^m$ and some $b\in\mathbb{R}^m$. The Lagrangian $L:\mathbb{R}^n\times\mathbb{R}^m_+\to\mathbb{R}$ is given by $$L(x,\lambda)=f(x)+\lambda\cdot (b-G(x)).$$ You can view the Lagrangian as the payoff function-function of a zero-sum game. One player, the one controlling $x$, wants to maximize the Lagrangian, and the other player, the one controlling $\lambda$, wants to minimize the Lagrangian. The sufficiency conditions tell you that if you have an equilibrium of this game, then the payoff of the maximizer is the maximum of the optimization problem. The necessary conditions guarantee that an equilibrium exists and that a minimax theorem holds for this game: $$\sup_{x\in\mathbb{R}^n}\inf_{\lambda\in\mathbb{R}^m_+}L(x,\lambda)=\inf_{\lambda\in\mathbb{R}^m_+}\sup_{x\in\mathbb{R}^n} L(x,\lambda).$$ The sup becomes a max, the inf becomes a min, and the solutions are given by first-order conditions. Here is the idea of why this works: If the maximizer maximizes $f$ under the constraint, we get $b-G(x)\geq 0$, and thus, for every $\lambda\geq 0,$ one has $\lambda\cdot (b-G(x))\geq 0$. SInceSince $\lambda=0$ is always possible for the minimizer, we must have $\lambda\cdot (b-G(x))= 0$. However, if the maximizer would violate the constraint, there must be some coordinate $i=1,\ldots,m$ such that $b_i-G_i(x)<0$. Let $e_i\in\mathbb{R}^m$ be the vector with ana $1$ in the $i$th place, and all other coordinates $0$. For $\lambda=C e_i$ with $C$ a large positive number, the LAgragianLagragian can be made arbitrarily small (negative). So the maximizer has to satisfy the constraint in order for the minimizer not to "win." Duality tells you that it doesn't matter which player would move first, but it doesn't change the asymmetry between maximizing and minimizing. Of course you can rewrite the result to be one for minimization problems, which is exactly what you get by maximizing $-f$.

The Lagrangian is not really symmetric; something that is easier to see if you formulate it without the calculus implementation. First order conditions for maxima and minima might look similar, but maxima and minima are very different.

You have the function $f:\mathbb{R}^n\to\mathbb{R}$ you want to maximize, subject to the constraint (written using vector notation) that $G(x)\leq b$ for a function $G:\mathbb{R}^n\to\mathbb{R}^m$ and some $b\in\mathbb{R}^m$. The Lagrangian $L:\mathbb{R}^n\times\mathbb{R}^m_+\to\mathbb{R}$ is given by $$L(x,\lambda)=f(x)+\lambda\cdot (b-G(x)).$$ You can view the Lagrangian as the payoff function of a zero-sum game. One player, the one controlling $x$, wants to maximize the Lagrangian, the other player, the one controlling $\lambda$, wants to minimize the Lagrangian. The sufficiency conditions tell you that if you have an equilibrium of this game, then the payoff of the maximizer is the maximum of the optimization problem. The necessary conditions guarantee that an equilibrium exists and that a minimax theorem holds for this game: $$\sup_{x\in\mathbb{R}^n}\inf_{\lambda\in\mathbb{R}^m_+}L(x,\lambda)=\inf_{\lambda\in\mathbb{R}^m_+}\sup_{x\in\mathbb{R}^n} L(x,\lambda).$$ The sup becomes a max, the inf becomes a min, and the solutions are given by first-order conditions. Here is the idea why this works: If the maximizer maximizes $f$ under the constraint, we get $b-G(x)\geq 0$ and thus, for every $\lambda\geq 0,$ one has $\lambda\cdot (b-G(x))\geq 0$. SInce $\lambda=0$ is always possible for the minimizer, we must have $\lambda\cdot (b-G(x))= 0$. However, if the maximizer would violate the constraint, there must be some coordinate $i=1,\ldots,m$ such that $b_i-G_i(x)<0$. Let $e_i\in\mathbb{R}^m$ be the vector with an $1$ in the $i$th place, and all other coordinates $0$. For $\lambda=C e_i$ with $C$ a large positive number, the LAgragian can be made arbitrarily small (negative). So the maximizer has to satisfy the constraint in order for the minimizer not to "win." Duality tells you that it doesn't matter which player would move first, but it doesn't change the asymmetry between maximizing and minimizing. Of course you can rewrite the result to be one for minimization problems, which is exactly what you get by maximizing $-f$.

The Lagrangian is not really symmetric; something that is easier to see if you formulate it without the calculus implementation. First-order conditions for maxima and minima might look similar, but maxima and minima are very different.

You have the function $f:\mathbb{R}^n\to\mathbb{R}$ you want to maximize, subject to the constraint (written using vector notation) that $G(x)\leq b$ for a function $G:\mathbb{R}^n\to\mathbb{R}^m$ and some $b\in\mathbb{R}^m$. The Lagrangian $L:\mathbb{R}^n\times\mathbb{R}^m_+\to\mathbb{R}$ is given by $$L(x,\lambda)=f(x)+\lambda\cdot (b-G(x)).$$ You can view the Lagrangian as the payoff-function of a zero-sum game. One player, the one controlling $x$, wants to maximize the Lagrangian, and the other player, the one controlling $\lambda$, wants to minimize the Lagrangian. The sufficiency conditions tell you that if you have an equilibrium of this game, then the payoff of the maximizer is the maximum of the optimization problem. The necessary conditions guarantee that an equilibrium exists and that a minimax theorem holds for this game: $$\sup_{x\in\mathbb{R}^n}\inf_{\lambda\in\mathbb{R}^m_+}L(x,\lambda)=\inf_{\lambda\in\mathbb{R}^m_+}\sup_{x\in\mathbb{R}^n} L(x,\lambda).$$ The sup becomes a max, the inf becomes a min, and the solutions are given by first-order conditions. Here is the idea of why this works: If the maximizer maximizes $f$ under the constraint, we get $b-G(x)\geq 0$, and thus, for every $\lambda\geq 0,$ one has $\lambda\cdot (b-G(x))\geq 0$. Since $\lambda=0$ is always possible for the minimizer, we must have $\lambda\cdot (b-G(x))= 0$. However, if the maximizer would violate the constraint, there must be some coordinate $i=1,\ldots,m$ such that $b_i-G_i(x)<0$. Let $e_i\in\mathbb{R}^m$ be the vector with a $1$ in the $i$th place, and all other coordinates $0$. For $\lambda=C e_i$ with $C$ a large positive number, the Lagragian can be made arbitrarily small (negative). So the maximizer has to satisfy the constraint in order for the minimizer not to "win." Duality tells you that it doesn't matter which player would move first, but it doesn't change the asymmetry between maximizing and minimizing. Of course you can rewrite the result to be one for minimization problems, which is exactly what you get by maximizing $-f$.

Source Link
Michael Greinecker
  • 13.7k
  • 1
  • 27
  • 38

The Lagrangian is not really symmetric; something that is easier to see if you formulate it without the calculus implementation. First order conditions for maxima and minima might look similar, but maxima and minima are very different.

You have the function $f:\mathbb{R}^n\to\mathbb{R}$ you want to maximize, subject to the constraint (written using vector notation) that $G(x)\leq b$ for a function $G:\mathbb{R}^n\to\mathbb{R}^m$ and some $b\in\mathbb{R}^m$. The Lagrangian $L:\mathbb{R}^n\times\mathbb{R}^m_+\to\mathbb{R}$ is given by $$L(x,\lambda)=f(x)+\lambda\cdot (b-G(x)).$$ You can view the Lagrangian as the payoff function of a zero-sum game. One player, the one controlling $x$, wants to maximize the Lagrangian, the other player, the one controlling $\lambda$, wants to minimize the Lagrangian. The sufficiency conditions tell you that if you have an equilibrium of this game, then the payoff of the maximizer is the maximum of the optimization problem. The necessary conditions guarantee that an equilibrium exists and that a minimax theorem holds for this game: $$\sup_{x\in\mathbb{R}^n}\inf_{\lambda\in\mathbb{R}^m_+}L(x,\lambda)=\inf_{\lambda\in\mathbb{R}^m_+}\sup_{x\in\mathbb{R}^n} L(x,\lambda).$$ The sup becomes a max, the inf becomes a min, and the solutions are given by first-order conditions. Here is the idea why this works: If the maximizer maximizes $f$ under the constraint, we get $b-G(x)\geq 0$ and thus, for every $\lambda\geq 0,$ one has $\lambda\cdot (b-G(x))\geq 0$. SInce $\lambda=0$ is always possible for the minimizer, we must have $\lambda\cdot (b-G(x))= 0$. However, if the maximizer would violate the constraint, there must be some coordinate $i=1,\ldots,m$ such that $b_i-G_i(x)<0$. Let $e_i\in\mathbb{R}^m$ be the vector with an $1$ in the $i$th place, and all other coordinates $0$. For $\lambda=C e_i$ with $C$ a large positive number, the LAgragian can be made arbitrarily small (negative). So the maximizer has to satisfy the constraint in order for the minimizer not to "win." Duality tells you that it doesn't matter which player would move first, but it doesn't change the asymmetry between maximizing and minimizing. Of course you can rewrite the result to be one for minimization problems, which is exactly what you get by maximizing $-f$.