I am currently solving a complex optimisation problem, with constraints that take the form: $1 - all(g(x)<a) <= 0$, meaning I require all values $g(x)$ (for some function $g$) to be below some threshold, given a vector $x$.

I have been told that logical operator all() can be re-written in terms of heavy-side functions, and then we can use some approximation of the heavy-side function to attain a differentiable constraint, as well as write down its gradient to help speed up optimisation. My problem comines in that I do not see how one can re-write all() in terms of a heavy-side function. Can anyone provide insight into this?

  • $\begingroup$ So what's wrong with a standard vector constraint $g(x)-a<0$ and then using a standard solver (well, doesn't work in practice as you cannot have strict inequalities, so make that $g(x)-a +\epsilon\leq 0$). Sounds a bit like you are re-inventing a barrier function or something $\endgroup$ – Johan Löfberg May 8 at 11:30
  • $\begingroup$ I was unsure if having a large number of non-linear constraints (g(x) can be non-linear in my problem) would be so detrimental to performance that solving in a reasonable time-frame would become impossible. I was planning to combine these into a single one, replace the heavy-side functions with a smooth approximation and then analytically specify the Jacobian of my constraint. Is this unnecessary? $\endgroup$ – Kieran108 May 8 at 12:05
  • $\begingroup$ In the end, I hope you are going to use some readily available solver, and they will handle constraints in the most efficient manner. What typically is done in nonlinear solvers is to scalarize vector constraints using barrier functions or penalty functions. Don't do this manually outside a solver, its core machinery is all about clever ways to do this in the best possible way. Don't re-invent the wheel $\endgroup$ – Johan Löfberg May 8 at 12:15

Let's have $H_0\ :\begin{cases}0 & x<0 \\ 1 & x\ge 0\end{cases}$

Note: it can also be calculated from the floor function as $H_0(x)=\left(1+\dfrac{\lfloor\frac{x+1}{|x|+1}\rfloor-\frac 14}{|\lfloor\frac{x+1}{|x|+1}\rfloor-\frac 14|}\right)/2$

Then you can define the translated functions:

$H_a(x)=H_0(x-a)\ :\begin{cases}0 & x<a \\ 1 & x\ge a\end{cases}\quad$ and $\quad G_a(x)=H_0(a-x)\ :\begin{cases}1 & x\le a \\ 0 & x> a\end{cases}$

And then all the characteristic functions for intervals:

$\begin{align} \delta_a(x) &= H_a(x)G_a(x)\\ 1_{[a,+\infty)}(x) &= H_a(x)\\ 1_{(a,+\infty)}(x) &= 1 - G_a(x)\\ 1_{(-\infty,b]}(x) &= G_b(x)\\ 1_{(-\infty,b)}(x) &= 1 - H_b(x)\\ 1_{[a,b]}(x) &= H_a(x) + G_b(x) - 1\\ 1_{(a,b)}(x) &= 1 - G_a(x) + H_b(x)\\ 1_{[a,b)}(x) &= H_a(x) - H_b(x)\\ 1_{(a,b]}(x) &= G_b(x) - G_a(x)\end{align}$

Regarding your problem, you are interested in $g(x)<a$ which thus involves $1_{(-\infty,a)}(g(x))$.

But this has only $0,1$ values, we need to multiply by $g(x)$ itself to get back the values of $g$ and do the comparison $1-g(x)\le 0$

So we have now $1_{(-\infty,a)}(g(x))\times(1-g(x))\le 0$ and when $g(x)\ge a$ you can notice that the indicator function is $0$ which also respects the condition $0\le 0$.

Rewriting in terms of $H_0$ only you get the condition $$\big(1-H_0(g(x)-a)\big)\big(1-g(x)\big)\le 0$$

  • $\begingroup$ Thanks for this, it is clear and exactly what I was looking for. $\endgroup$ – Kieran108 May 8 at 12:00

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.