Saddle point and linear programming Let 
$$f(x,y)=(-c)\cdot x+y\cdot (Ax-b),$$
$x,c\in \mathbb{R}^n$, $y,b\in \mathbb{R}^m$ and $A\in \mathbb{R}^{m\times n}$. I want to prove that if $x^*$ is the solution to a linear programming problem
$$\min\{c\cdot x\colon Ax=b, \ x\geq 0\}$$
and $y^*$ is the solution to the dual problem, then $(x^*,y^*)$ is function's $f$ saddle point. Any ideas on how to approach this?
 A: Consider problem data $A,b,c$.
Write the primal as
$$
\mathsf{P}(A,b,c):= \max_{x}\{ \langle{c},{x}\rangle : Ax\leq b,\,x\geq0\}
$$
and the dual as
$$
\mathsf{D}(A,b,c):= \min_{y}\{ \langle{b},{y}\rangle : A^\top y\geq c,\,y\geq0\}.
$$
Then consider the function
$$
f(x,y):=c^\top x + y^\top(b-Ax).
$$
Plugging in $x^*$ and $y^*$, which are feasible for $\mathsf{P}$ and $\mathsf{D}$, respectively, we have
$$
b^\top y^*+p\equiv f(x,y^*) \leq f(x^*,y^*) \leq f(x^*,y) \equiv c^\top x^* + q
$$
where

*

*$p=(c-A^\top y^*)^\top x\leq0$ since $A^\top y^*\geq c$ and $x\geq0$ (for any $x$ feasible to $\mathsf{P}$);

*$q=y^\top(b-Ax^*)\geq0$ since $Ax^*\leq b$ and $y\geq0$ (for any feasible $y$ to $\mathsf{D}$).

So, $(x^*,y^*)$ is a saddle point of the $f$ I've defined.
A: For 
$$
f(x,y) = -c \cdot x + y \cdot (Ax - b) = f(u)
$$
with $u = (x_1,\dotsc,x_n, y_1, \dotsc, y_m)^\top$.
The first partial derivatives are
$$
\partial_k f = \partial_{x_k} f = y_i a_{ik} - c_k \quad (k \in \{1,\dotsc,n \}) \\
\partial_k f = \partial_{y_{k-n}} f = a_{(k-n)j} x_j - b_{k-n} \quad (k \in \{n+1,\dotsc,n+m \}) 
$$
or
$$
\DeclareMathOperator{grad}{grad}
\grad f = 
\begin{pmatrix}
A^\top y -c \\
Ax-b
\end{pmatrix}
$$
The Hessian is
$$
H_{ij} = \partial_i \partial_j f
$$
with
$$
H_{ij} = 0  \quad (i,j \in \{1, \dotsc, n\}) \\
H_{ij} = 0  \quad (i,j \in \{n+1, \dotsc, n+m\}) \\
H_{ij} = a_{(j-n)i}  \quad (i \in \{1, \dotsc, n\}, j \in \{n+1, \dotsc, n+m\}) \\
H_{ij} = a_{(i-n)j}  \quad (i \in \{n+1, \dotsc, n+m\}, j \in \{1, \dotsc, n\})
$$
or
$$
H = 
\begin{pmatrix}
0 & A^\top \\
A & 0
\end{pmatrix}
$$
It seems we need to show that $H$ has positive and negative eigenvalues to be indefinite and indicating a saddle point. Not sure if this is sufficient for Hessians with more than two variables.
$$
u^\top H u 
= x^\top A^\top y + y^\top A x
= y^\top A x + y^\top A x
= 2 y^\top A x 
$$
