Suppose we have some procedure $F$ which takes any set of linear constraints and either returns either infeasible or returns a vector satisfying these constraints.

If we now take a linear program $L$, how can we solve it with only one call to $F$ (where the number of variables and constraints input to $F$ is polynomial in the number of variables and constraints in $L$)?

I was thinking there might be a way of using the dual of $L$ in combination with $L$ to form a new linear program which has a convex hull with essentially $0$ volume so that any call to $F$ will return the same feasible solution which by strong duality theorem must be the optimal one too.


Assume you have a linear program of the form

$\quad$ maximize $\mathbf{n}^T\mathbf{x}$ subject to $A\mathbf{x}\leq\mathbf{a}$.

The dual lp is

$\quad$ minimize $\mathbf{a}^T\mathbf{u}$ subject to $A^T\mathbf{u}=\mathbf{n}, \mathbf{u}\geq \mathbf{0}$.

By weak duality for any solution $\mathbf{x}_0$ of the primal lp and $\mathbf{u}_0$ of the dual lp it holds:

$\quad$ $\mathbf{n}^T\mathbf{x}_0 \leq \mathbf{a}^T\mathbf{u}_0$,

and by strong duality it holds

$\quad$ $\mathbf{n}^T\mathbf{x}_0 = \mathbf{a}^T\mathbf{u}_0$ if and only if $\mathbf{x}_0$ and $\mathbf{u}_0$ are optimal solutions.

Hence, any feasible solution $(\mathbf{x}_0,\mathbf{u}_0)$ of the system

$\quad$ $A\mathbf{x} \leq \mathbf{a}$, $A^T\mathbf{u} = \mathbf{n}$, $\mathbf{u}\geq\mathbf{0}$, $\mathbf{n}^T\mathbf{x} \geq \mathbf{a}^T\mathbf{u}$ $\quad$(*)

is an optimal solution of the primal (and also of the dual) lp.

Now, let (*) be the input of your procedure $F$, then any solution is an optimal solution of the primal (and also the dual) lp.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.