Exercise 4.10 (Saddle points of the Lagrangean)

Question

\documentclass{article}
\usepackage{graphicx}
\usepackage{bm}
\begin{document}

%\section{Saddle points of the Lagrangean}
Consider the standard form problem of minimizing $\bm{c^{\prime}x}$ subject to $\bm{Ax = b}$ and $\bm{x{\geq}0}$.We define the {\itshape Lagrangean} by 
$$
\bm{L(x,p) = c^{\prime}x + p^{\prime}(b-Ax)}.
$$
Consider the following "game": player 1 choose some $\bm{x{\geq}0}$, and player 2 chooses some $\bm{p}$;then player 1 pays to player 2 the amount $\bm{L(x,p)}$. player 1 would like to minimize $\bm{L(x,p)}$, while player 2 would like to maximize it.

A pair $\bm{x^{\prime},p^{\prime}}$ ,with $\bm{x^{\prime}{\geq}0}$, is called an {\itshape equilibrium} point (or a saddle point, or a {\itshape Nash equilibrium} if 
$$
\bm{L(x^{\prime},p){\leq}L(x^{\prime},p^{\prime}){\leq}L(x,p^{\prime}),\qquad \forall x{\geq}0, 
\quad \forall p.}
$$
(Thus, we have an equilibrium if no player is able to improve her performance by unilaterally modifying her choice.)

Show that a pair $\bm{x^{\prime},p^{\prime}}$ is an equilibrium if and only if $\bm{x^{\prime}}$ and $\bm{p^{\prime}}$ are optimal solution to the standard form problem under consideration and its dual respectively.
\end{document}

liuliuzi · Accepted Answer

\documentclass{article}
\usepackage{graphicx}
\usepackage{bm}
\begin{document}

\section{Saddle points of the Lagrangean}

first we want to proof the two inequality:
$$L(p^{\ast},x){\leq}L(p^{\ast},x^{\ast})$$
$$L(p^{\ast},x^{\ast}){\leq}L(p,x^{\ast})$$
we transform it to:
$$
c^{\prime}x + p^{\ast \prime}(b - Ax) - c^{\prime}x^{\ast} - p^{\ast \prime}(b - Ax^{\ast}) {\geq} 0 
$$
$$
c^{\prime}x^{\ast} + p^{\ast \prime}(b - Ax^{\ast}) - c^{\prime}x^{\ast} - p^{\prime}(b - Ax^{\ast}) {\geq} 0 
$$
And then we will discuss the problem in some situation

First we think the that $x^{\ast},p^{\ast}$ is the optimal solution of the primal and dual problem. We will find that $x^{\ast}$ satisfy $Ax^{\ast} = b$, so the first inequality come to $c^{\prime}x - c^{\prime}x^{\ast} + p^{\ast \prime}(b - Ax) {\leq} 0 $ 
it is equal to $(c^{\prime} - p^{\ast \prime}A)x + p^{\ast \prime}b - c^{\prime}x^{\ast}$
as the strong dual and the feasibility of the $p^{\ast}$ we know that  $(c^{\prime} - p^{\ast \prime}A)x = 0$ and $c^{\prime} - p^{\ast \prime}A {\geq} 0$ so we hold the first inequality 
and because ${x^{\ast}}$ is the optimal solution and it satisfy $Ax^{\ast} = b$ so the second inequality is right.

Second we consider the situation that ${x^{\ast}}$ satisfy $Ax^{\ast} = b$ but it is not the optimal so for the first inequality we let $x=0$ ,then we find that  $p^{\ast \prime}b-c^{\prime}x^{\ast}{\leq}0$ so the first inequality does not hold, and the situation about the dual is similar

Final we will discuss the situation that the constrains is not active, we can see that if the primal problem does not follow the constrain, for the second inequality there must be some element that not equal to 0, because of $p$ can can be any real number, we can let $p$ be a large number that make the inequality not hold, the dual is similar
\end{document}

Exercise 4.10 (Saddle points of the Lagrangean)

Answers

1 Saddle points of the Lagrangean

Comments

Exercise 4.10 (Saddle points of the Lagrangean)

Answers

1 Saddle points of the Lagrangean

Comments

Add answer