How to handle strict inequalities?

Question

Perhaps two trivial questions: What kind of problem is the following (please note the strict inequality)? How do we solve it?

$$\min_{x\geq 0}\{c^\top x: Ax < b\}$$

Answer 1

In practice, most solvers are implemented to use fast but inexact floating-point arithmetic and thus can only ever guarantee to satisfying the optimality conditions of your problem to within some nonzero tolerances. Due to the presence of these nonzero tolerances, strict and nonstrict inequality hence carry the exact same meaning. What you can do, however, is to rewrite $Ax < b$ as $Ax \leq b - \epsilon$, for some small constant $\epsilon > 0$ significant enough to make up for tolerances as well as the inexact floating-point arithmetic used to verify those tolerances.

In theory, with infinite precision or symbolic computations, you would need some kind of nonlinearity to represent a strict inequality in terms of standard inequalities. As example, your problem could be reformulated as a second-order cone problem as explained in a previous answer (https://or.stackexchange.com/a/7357/198):

Strict positivity, $x > 0$, is equivalent to the existence of nonnegative variable, $r \geq 0$, such that $xr \geq 1$. This means that it can be represented in second-order cone programming by the conic quadratic constraint $$x+r \geq \sqrt{ (x-r)^2 + 1^2 }.$$

Answer 2

I'm not aware of a special name for those kind of problems. In order to solve it in practice, you might add a small constant numerical tolerance $\varepsilon > 0$, e.g. $\varepsilon = 10^{-8}$, and solve

$$ \min_{x \geq 0} c^\top x \quad \text{s.t} \quad Ax \leq b - \varepsilon $$

instead.