# Solving a linear program using just one call to a procedure that gives a feasible solution.

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.