3
$\begingroup$

When solving constraint optimization problems with (primal dual) interior points methods, I often read (e.g. on slide 17) that one should not use the inequality constraints $g(x)\leq 0$ directly, but use the slack variables $s\leq 0$ to form $g(x)-s=0$.

But why? Is it easier to find an initial feasible point? Or does the comment "That is, we lift the problem into a higher dimension by adding new variables, so that we have to work with. Frequently, in higher dimensions, we may have a better point of view." refer to this? Then I need an explanation for the comment.

Moreover, I wonder if this is a mainly a problem in the non-convex setting, as Boyd and Vandenberghe do not mention this.

$\endgroup$
3
  • $\begingroup$ There is a sign inconsistency between the direction of the inequality constraint, the constraint on the slack, and the sign in front of the slack in the equality constraint. You need to change one of them. $\endgroup$ Aug 30, 2022 at 14:34
  • $\begingroup$ Thanks. I corrected it. $\endgroup$ Aug 30, 2022 at 15:07
  • 1
    $\begingroup$ That works, but it is much more common for slack variables to be constrained to be nonnegative. $\endgroup$ Aug 30, 2022 at 15:12

2 Answers 2

3
$\begingroup$

That explanation sounds a little vague to me also. If I had to guess, I'd say that one of the advantages of introducing slack variables is because there are specialized algorithms like L-BFGS-B or the method outlined in this paper by Conn, Gould, and Toint that only work for simple bounds constraints $a \le u \le b$ and not for complex inequality constraints like $g(x) \le 0$. Introducing slack variables turns complex inequality constraints into simple ones.

That paper has an explanation of why simple bounds constraints are preferable as well:

One issue that is not present in unconstrained minimization, but is in evidence here, is the combinatorial problem of finding which of the variables lie at a bound at the solution (such bound constraints are said to be active). In active-set algorithms, the intention is to predict these variables and to minimize the function with respect to the remaining variables. Obviously, an incorrect prediction is undesirable, and it is then useful (indeed essential for large problems) to be able to make rapid changes in the active set to correct for wrong initial choices. Unfortunately, many existing algorithms for constrained optimization only allow very small changes in the active set at each iteration, and consequently, for large problems, there is the possibility of requiring a large number of iterations to find the solution. Fortunately, for simple bound constraints, it is easy to allow for rapid changes in the active set in the design of algorithms.

(Emphasis mine.)

$\endgroup$
2
  • $\begingroup$ L-BFGS-B wouldn't apply. There would still be at least one constraint other than a (simple) bound constraint, which makes it out of scope for L-BFGS-B. $\endgroup$ Aug 30, 2022 at 19:45
  • 1
    $\begingroup$ Ah you're right of course, I've corrected the answer. $\endgroup$ Aug 30, 2022 at 20:27
2
$\begingroup$

Based on my perilous self-taught journey through this material, I believe the intent of the advice (though its not immediately clear to me either) is not to compute the logarithm of your constraint function, which could get pretty messy. Instead of "directly" computing the logarithmic barrier function, you only need it implicitly. From Boyd's book:

$$ \begin{align*} \phi &= -\log\left(-f_i\right) \\ \nabla \phi& = -\frac{\nabla f_i}{f_i} \\ \nabla \nabla \phi &= -\frac{\nabla \nabla f_i}{f_i} + \frac{\nabla f_i \nabla f_i^T}{f_i^2} \end{align*} $$

If you are only computing, say, a Newton direction, at no point do you need $\phi = -\log\left(-f_i\right)$, just its derivatives. If you need to check for feasibility, just check $f_i < 0$, no need for the logarithm.

As for the slack variables, I see no reason other than mathematical formalism to define $g(x) = s$.

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