# Optimal solution of a linear program

I have a question about linear optimization.

Consider two LPs, $$\begin{array}{ll} \underset {x} {\text{maximize}} & c^T x \\ \text{subject to} & Ax = b \\ & x \geq 0 \end{array} \tag{P}$$ $$\begin{array}{ll} \underset {x} {\text{maximize}} & c^T x \\ \text{subject to} & Ax = b \\ & x \text{ is free}\end{array} \tag{F}$$ where $$A$$ has linearly independent rows.

1. Prove that if $$(F)$$ has an optimal solution, then $$c = A^T z$$ for some vector $$z$$.
2. Prove that if $$(F)$$ has an optimal solution, then in every canonical form of $$(P)$$, the objective function is $$0^T x + q$$, where $$q$$ is a constant.

For part 1, I'm not able to find the vector $$z$$, totally has no clue. For part 2, I think I can use the conclusion of part 1, assume there's a vector $$z$$, such that $$c = A^T z$$. Then assume $$x^*$$ is an optimal solution for $$c^T x$$, then $$Ax^* = b$$, and $$c^T x^* = (A^T z)^Tx^* = z^TAx^* = z^T b$$. We can let $$q = z^T b$$, then the objective function is $$c^Tx^* = q = 0^T x + q$$. But from this solution, I'm concerned as (F) has $$x$$ is free, but (P) has $$x \geq 0$$. So I'm not able to figure it out.

Could you please give me some clue for part 1, and point out anything wrong in point 2? Thanks a lot!

Anybody could give me some clue how to find the vector $$z$$? And what is the relationship of $$F$$ with the canonical form of $$P$$? Thanks a lot!

• Part 1. Use the Lagrange dual. You do not have to find $z$ but just show that it exists.
– KBS
Commented Jun 18, 2023 at 13:50

Let $$\nu(F) = \max_x \{c^\top x : Ax=b\}$$ be the optimal value of $$(F)$$. The Lagrangian of $$(F)$$ is $$L(x;y) = c^\top x + y^\top(b-Ax) = (c - A^\top y)^\top x + b^\top y.$$ By the max-min inequality (i.e., weak duality) , $$\nu(F) = \max_x \min_y L(x;y) \leq \min_y \max_x L(x;y) = \nu(D)$$ for dual problem $$(D)$$. Since $$x$$ is free, the dual problem $$\min_y \max_x L(x;y)$$ is finite only when $$c-A^\top y=0$$, so $$\nu(D) = \min_y\{b^\top y : A^\top y = c\}.$$ By LP strong duality, knowing that $$(F)$$ has an optimal (finite) solution means that the dual is neither infeasible nor unbounded, so it must have an optimal (finite) solution. That is, there exists $$y^*$$ such that $$A^\top y^*=c$$ and $$b^\top y^*=c^\top x^*$$ for an optimal $$x^*$$ to $$(F)$$.