2
$\begingroup$

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\}$$

$\endgroup$
3
  • $\begingroup$ Are all variables continuous? $\endgroup$
    – Reinderien
    Sep 7, 2023 at 23:19
  • 1
    $\begingroup$ The general mathematical term for this kind of problem is "not well-defined" because the minimum typically does not exist. $\endgroup$ Sep 8, 2023 at 12:07
  • $\begingroup$ @MichalAdamaszek I agree. I think this is correct answer. The feasible region is an open set. One can get arbitrarily close to $b$ without ever getting there. So, for any solution within an $\epsilon$ from $b$, there is always one even closer. If you posted this as an answer I would accept it. $\endgroup$
    – k88074
    Sep 12, 2023 at 11:52

2 Answers 2

4
$\begingroup$

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 }.$$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.