2
$\begingroup$

In an optimization problem, I have an inequality constraint, say

$\begin{array}{c} {\min\limits_x~} c(x)\\ {s.t.~}g(x)\le 0 \end{array}$

The function $g(x)$ in general is unknown. So, numerical perturbation is necessary if the solver is gradient-based.

Now, I can pass it to a universal nonlinear optimization solver, e.g., fmincon in MATLAB. However, what if I convert the constraint to

$\begin{array}{c} {\min\limits_x~} c(x)\\ {s.t.~}\max(g(x),0) = 0 \end{array}$

and pass this equality constraint to the same optimization solver?

I would expect to have the same results in both cases (Please ignore the numerical tolerance for simplicity). But does this conversion bring any disadvantage or advantage theoretically? Could there be any major impact?

$\endgroup$
  • $\begingroup$ Are you asking if greater than is faster than greater than equals? $\endgroup$ – The Great Duck Jul 5 '16 at 21:51
  • $\begingroup$ Not exactly.. I am concerned with what will happen by forcing an inactive constraint to always being active. Will this to any extent limit the ability of a solver to find the solution? Using the 'active-set' algorithm for example, the equality constraint will always be taken into account for constructing the active-set. $\endgroup$ – Jiang Jul 5 '16 at 21:55
  • $\begingroup$ I dont understand what you mean? You are referring to a conditional statement, correct? $\endgroup$ – The Great Duck Jul 5 '16 at 22:02
  • $\begingroup$ If the current x0 is such that g(x0)<0. Then this condition is inactive. However, after conversion, the constraint max(g(x0),0) = 0 is always active because it is equality. As far as I understand, in nonlinear programming, active and inactive constraints are often treated differently. So, I am concerned with if the conversion will change the behavior of a solver. $\endgroup$ – Jiang Jul 5 '16 at 22:16
  • $\begingroup$ I presume you are not referring to the optimization of code? I think I misread your post... Lol. $\endgroup$ – The Great Duck Jul 5 '16 at 22:24
0
$\begingroup$

If the solver is smart, it'll actually convert $\max(g(x),0)=0$ back into $g(x)\leq 0$. Basically, the $\max$ function is nondifferentiable, which makes it much more difficult to work with numerically since we typically need derivatives for fast optimization algorithms. As such, a solver with a good preprocessor will take $\max(g(x),0)=0$ and turn it into \begin{align*} y =& 0\\ y\geq& g(x)\\ y\geq& 0 \end{align*} which then gets further processed into $$ 0\geq g(x) $$ which you started with. Or, at least, that's one way to process it. There's probably more.

Anyway, in answer to your original question. No. Your transformation makes things much more difficult numerically. Again, the $\max$ function is nondifferentiable, so it's hard to use fast algorithms to work with it. In addition, if $g$ were convex, you just reformulated a nice convex constraint into something that's hard to work with. Now, unless $g$ is affine, it's likely that the solver is going to add a slack variable anyway and reformulate your problem as $$ \min\limits_{x\in X} \{c(x) : y = g(x), y\leq 0\} $$ It'll do this since most algorithms to handle inequalities need to figure out how far we can traverse before becoming infeasible. For a nonaffine $g$, this is hard to determine, so we just add a slack variable and then handle the equality constraint. As such, the real question then becomes whether or not we can effectively solve the linear systems that involve $g^\prime(x)$, which arise when attacking the KKT conditions using something like a Newton method. Basically, algorithms like SQP. In any case, if you want to speed up the computation, likely the biggest speedup is focusing on quickly solving these linear systems.

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