3
$\begingroup$

Linear programming can solve only problems with weak inequalities, such as "maximize $c x$ such that $A x \leq b$". This makes sense, since problems with strict inequality often do not have a solution. For example "maximize $x$ such that $x<5$" does not have a solution.

But suppose we are interested in finding supremum instead of maximum. In this case, the above program does have a solution - the supremum is $5$.

Given a linear program with strict inequalities and a supremum or infimum objective, is it possible to solve it by reduction to a standard linear program?

$\endgroup$
3
$\begingroup$

Suppose that the supremum of a continuous function $f(x)$ subject to $Ax < b$ is $c$, and assume furthermore that the constraints imply a bound on $\|x\|_\infty$. Thus there is a sequence of feasible points $x_n$ such that $f(x_n) \to c$. Since all points in the sequence have bounded norm, it follows that some subsequence of $x_n$ converges to a limit point $y$ satisfying $f(y) = c$ and $Ay \leq b$. This implies that in the bounded case, your problem is equivalent to classical linear programming.

In the unbounded case this argument doesn't work. For example, the infimum of $x-y$ subject to $x-y > 0$ is $0$, but the sequence $(n+1/n,n)$ has no limit points. Nevertheless, the answer should be the same.

$\endgroup$
  • $\begingroup$ So the problem "supremum $c x$ s.t. $A x < b$" has the same solutions as the problem "maximum $c x$ s.t. $A x \leq b$"? But what about the problem "supremum $c x$ s.t. $x_1=5, x_2=5, x_1-x_2<0$" - it is not equivalent to "maximum $c x$ s.t. $x_1=5, x_2=5, x_1-x_2\leq 0$": the latter has a solution and the former does not. $\endgroup$ – Erel Segal-Halevi Aug 25 at 5:05
  • $\begingroup$ They should be equivalent when both are feasible and bounded. Your example is a corner case. $\endgroup$ – Yuval Filmus Aug 25 at 6:04

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.