patternMinor
Linear programs with strict inequalities and supremum objectives
Viewed 0 times
linearwithinequalitiesprogramsandstrictobjectivessupremum
Problem
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?
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?
Solution
Suppose that the supremum of a continuous function $f(x)$ subject to $Ax 0$ is $0$, but the sequence $(n+1/n,n)$ has no limit points. Nevertheless, the answer should be the same.
Context
StackExchange Computer Science Q#112999, answer score: 4
Revisions (0)
No revisions yet.