12
$\begingroup$

Once I learned from some post that the strict equality constraint in optimization problem does not make much sense. We should always use $\le$ constraint.

How far this is true.

If I must have a strict equality constraint, should I use both $\ge$ and $\le$ constraints to satisfy strict equality constraints?

$\endgroup$
  • $\begingroup$ If you know a definite relationship between variables, this would be a parameter, not a constraint. The optimization problem is designed to answer questions about what you don't know -- what values would be optimal. If you already know one value (perhaps in relationship to some others), that's not a question mark. $\endgroup$ – aparente001 Dec 8 '19 at 8:40
12
$\begingroup$

I suspect you read that actual floating point optimization solvers treat strict inequalities ($<$ and $>$) as non-strict inequalities ($\le$ and $\ge$). Solvers also give themselves a fudge factor, called feasibility tolerance, equal to the amount by which they may be violated in reality but treated as satisfying the constraint by the solver. If you must really have strict inequality and strict feasibility for a $\le$ constraint, $\textsf{LHS} < \textsf{RHS}$, then pick a number "margin", such that

$$\textsf{margin > feasibility tolerance}$$

and make your constraint

$$\sf LHS + margin \le RHS.$$

Similarly for $>$.

Equality constraints are treated by solvers as being satisfied if they are violated by no more than the feasibility tolerance. If you can not choose a feasibility tolerance which satisfies your desires across all constraint types to which it applies, then you can instead use two inequality constraints, with whatever tolerance for "equality satisfaction" you want. So, for the equality constraint $\sf LHS = RHS$, you could treat it as being $\sf |LHS - RHS| \le tolerance$, which is equivalent to $$\sf LHS - RHS \le tolerance,\quad\sf RHS - LHS \le tolerance$$

Keep in mind, that solvers will treat $\sf LHS = RHS$ as being $\sf |LHS - RHS| \le \textsf{feasibility tolerance}$.

You will never get (ensure) equality constraints satisfied strictly in floating point solvers.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I agree with the above, but to answer the last part of the original question, there is reason in a model to write $x \le y$ and $x \ge y$ rather than $x = y$. Writing equation constraints is fine; you just need to understand that they will be satisfied to within some tolerance. $\endgroup$ – prubin Dec 7 '19 at 18:45
4
$\begingroup$

This also depends on what "optimization" is for you. When you think of linear programs, or linear objective functions optimized over convex sets, an optimum would always be attained at the boundary of the feasible region. With strict inequality constraints you would just exclude that boundary.

There may be situations, however, in which you would like to "measure" whether you are strictly away from some value, in expressions as "if $x>0$ then something" which can be typically written as linear constraints with inequalities that are not strict but involves integer/binary variables.

Apart from all that, as @mark-l-stone said, $x>0$ always means $x \geq \varepsilon$ in practice.

| improve this answer | |
$\endgroup$
4
$\begingroup$

Equality constraints are typically fine, and often very useful:

  • branch and bound solvers use them for domain reduction (constraint propagation, FBBT , etc)

  • linear/non linear equality constraints are also used by some solvers to eliminate redundant variables and constraints. Note that this is not possible if we only have inequality constraints.

  • equality constraints are also used to produce cuts, both for MILPs, NLPs, and MINLPs.

Any decent solver will reformulate the constraints to a format that is better suited to its own calculations, so equality constraints are usually best left as they are. For instance, many linear solvers will reformulate all inequalities to equalities and add slack variables, in order to create a square system that can be iterated over.

One important exception is solvers that use callbacks, such as IPOPT or KNITRO. If all the solver can see is the derivatives/function values, it can't reformulate because it doesn't have the actual equations. In that case there's no one answer, and it's best to experiment. For instance, I've seen problems with many small linear equality constraints where IPOPT with mumps took forever to do one iteration, and switching to HSL was 100 times faster. However, running problem reduction algorithms before sending the problem to IPOPT/mumps solved about 100,000 times faster.

I would like to stress that although equality constraints can cause problems sometimes, the solution is never to use inequalities instead. It typically indicates a modelling problem, such as an overdefined linear system in the problem. The solution is to sanitize the linear system so that the degrees of freedom are equal to the number of equations, or to use a solver that will do these manipulations automatically.

| improve this answer | |
$\endgroup$

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.