6
$\begingroup$

Take the following optimization problem:

\begin{align}\min_x&\quad f(x)\\\text{s.t.}&\quad g(x)\le0\end{align}

with $f$ and $g$ nonlinear functions. Suppose I want to relax the constraint by replacing it with a penalty term proportional to the extent of the violation.

A straigtforward way to do this would be $$ \min_x f(x) + c\cdot\max\{0,g(x)\}. $$

In practice, however, I see it often implemented as \begin{align}\min_x&\quad f(x) + c\cdot\xi\\\text{s.t.}&\quad g(x)\leq \xi,\\&\quad 0\leq \xi.\end{align}

I have heard that this is to prevent the non-differentiability in the objective function, but the non-differentiability isn't really gone with this formulation, is it? Is there something fundamentally different between the two formulations that makes general nonlinear solvers better able to cope with the latter one?

$\endgroup$
9
$\begingroup$

Using the max operator, your objective function has directional derivatives but is not smoothly differentiable. For instance, if $x$ is scalar and $g(x) = x-2$, then at $x=2$ the max term has directional derivative 0 in the direction of decreasing $x$ and $c$ in the direction of increasing $x$. For a gradient-based algorithm, this makes the value of the gradient ambiguous. Some algorithms may tolerate the ambiguity better than others.

With the second formulation, the objective is differentiable and the kink in the derivative has been replaced by a constraint. Since the solver already knows how to deal with inequality constraints, you get differentiability in the objective without making the problem more difficult technically (just slightly bigger, to the tune of one variable and one constraint).

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