1

Consider the non-negative orthant $$ R\equiv \{(x_1,...,x_n): x_i\geq 0 \text{ }\forall i\} $$ The boundary of $R$ is not smooth. I'm looking for a function which can smooth the boundary of $R$ and which depends on only one smoothing parameter. Could you advise? I'm a beginner and any related question you may have to clarify my request are welcome.

Star
  • 222

1 Answers1

0

I guess the question is, why would you want to do that? Since your question is somewhat vague, I'm going to imagine that you are trying to solve an optimization problem like $$ \max_{x \in \mathbb{R}^N} f(x) $$ subject to $x \ge 0$ and $h(x) \le 0$, where $h(x)$ is quasi-convex and smooth, $f(x)$ is strictly quasi-concave and smooth, and $\{x:x \ge 0 \text{ and } h(x) \le 0 \} \neq \varnothing$. For some reason, you don't want to deal with $x \ge 0$, perhaps because $N$ is large and $2^N$ of these corner cases is too computationally taxing for a numerical solver or something.

Take $g(x,\alpha) = -\sum_{i=1}^N ( \min\{ 0, \alpha_i-x_i\})^2$. If $x_i$ drops below $\alpha_i$, it activates a penalty that pushes you away from $x_i=0$. The function $(\min\{0,\alpha_i-x_i\})^2$ is differentiable since $\lim_{x_i \uparrow \alpha_i } -(\alpha_i-x_i) = 0$ and $\lim_{x_i \downarrow \alpha_i} 0 = 0$. So if you maximize the Lagrangian $$ \mathcal{L}(x,\alpha) = f(x) - \mu h(x) + g(x,\alpha), $$ the $g(x,\alpha)$ function will push you away from picking corner solutions if $\mathcal{L}(x,0)$ has them.

Then you can take a sequence $\alpha_n \rightarrow 0$. Since $f$ is strictly quasi-concave and $h$ is quasi-convex, there is a unique maximizer, and by Berge's theorem of the maximum it is an upper-hemi continuous correspondence in $\alpha$ (and so a continuous function), so that $x^*(\alpha_n) \rightarrow x^*(0)$.

You could implement this idea of penalties a bunch of different ways. Perhaps by looking at which penalties get activated for small $||\alpha||$, you can get a guess of which corners are likely to be the problem for the optimization in advance of taking $\alpha \rightarrow 0$.

  • Should I add a Lagrangian multiplier in front of $g$ in $\mathcal{L}(x,\alpha)$? – Star Apr 10 '20 at 10:48
  • 1
    No, because it isn't a constraint. It ensures that if $\nabla f(x^) - \mu^ \nabla h(x^)=0$ and $x^$ is a corner solution, $x^*$ cannot still be a critical point of the Lagrangian once $g$ is introduced because its gradient does not vanish on the boundary of $\mathbb{R}^n_+$. –  Apr 10 '20 at 11:53