# Linear programs with strict inequalities and supremum objectives

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?

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.
• 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. – Erel Segal-Halevi Aug 25 at 5:05