1
$\begingroup$

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.

I tried many ways, but still cannot solve it. Could you please help?

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!

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

1 Answer 1

1
$\begingroup$

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)$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .