12
$\begingroup$

Let $\Omega$ be a convex, closed, compact set in $\mathbb{R}^d$ with a smooth boundary.

Given a data $(x_i,d_i)$, $x_i \in \Omega$,$d_i \in \mathbb{R}$, $i = 1,2,3...N$, $N>d$ and $\sum\limits_{i=1}^N d_i = 0$. Also given that, there are always $d$ vectors in $\{x_i\}$ which are linearly independent.

Let $A = \int_{\Omega}dx$

I want to find a continuous function $f:\Omega \to \mathbb{R}$, such that,

  1. $\int_{\Omega}f(x)dx = 0$ and
  2. $C(f)$ is minimum, where $$C(f) = \frac{A^{1/d}}{N}\bigg(\sum\limits_{i=1}^N |f(x_i)-d_i|^d\bigg)^{1/d} +\|f\|_{L^d}+ A^{1/d} \||\nabla f|\|_{L^d}$$

Does the solution exist? Is the solution unique? I mean any two solutions are equal almost everywhere?

$\endgroup$
22
  • $\begingroup$ If I understand correctly the problem, when $d>1$, the infimum of $C(f)$ among the mean-vanishing continuous functions on $\Omega$ is $0$, and it is not attained, because one can always find a continuous function $f$, with $\int_\Omega f dx=0$, with arbitrarily small $V_\Omega(f)+\|f\|_1$, and with $f(x_i)=d_i$ for $i=1,\dots,N$. $\endgroup$ Apr 19, 2017 at 23:53
  • $\begingroup$ @PietroMajer : When you don't allow jump discontinuties (as $f$ supposed to be continuous), then I am not sure, or atleast its no trivial for me, that you can construct such a function which concentrates on the data points. ... $\endgroup$
    – Rajesh D
    Apr 20, 2017 at 1:23
  • $\begingroup$ ...For example in 2 dimensions, consider a bump around a data point,and if the bump keeps shrinking (like $f(\alpha x)$, $\alpha$ increasing, the support vanishes, hence L1 norm vanishes, but the variation of bump goes to $\infty$ if we shrink the bump. So i dont have any suitable example to prove that. But if you consider disks (like step functions) around data points and make their circumpherence goes to zero by shrinking them, they the minimum value can be arbitrarily small, but here such discs are not continuous functions. $\endgroup$
    – Rajesh D
    Apr 20, 2017 at 1:23
  • $\begingroup$ In dimension $2$, a bump supported on a disk $B_r$ of radius $r$ (so area $O(r^2)$), and of height $1$, has gradient of size $1/r$, so doesn't it gives a variation $\int_{B_r}|\nabla f(x)|dx=O( r)$? $\endgroup$ Apr 20, 2017 at 7:12
  • $\begingroup$ @PietroMajer : Replacing $$C(f) = \frac{\int_{\Omega}dx}{N}\sum\limits_{i=1}^N |f(x_i)-d_i| +\|f\|_{L^1}+V_{\Omega}(f)$$, by $$C(f) = \frac{\int_{\Omega}dx}{N}\{\sum\limits_{i=1}^N |f(x_i)-d_i|^d\}^{1/d} +\|f\|_{L^d}+ \||\nabla f|\|_{L^d}$$ Its still the same for $d=1$ but for higher dimensions I am hoping it generalizes well without giving any trivial solutions (I need to prove/verify this) like infimum being zero. $\endgroup$
    – Rajesh D
    Apr 20, 2017 at 9:02

2 Answers 2

7
+100
$\begingroup$

The quick answer to your question (for $d > 1$) is no, there is no continuous solution. This can be rectified, however, by using a different $L^p$ norm.

Starting with the case of the $L^d$ norm as asked in the question, where $d$ is also the dimension of the Euclidean space, consider the following. For any $x_0\in\Omega$ and real numbers $r_0,A > 0$, define $f\colon\Omega\to\mathbb R$ by $$ f(x) = \begin{cases} 0,&{\rm if\ }r\ge r_0,\\ 1,&{\rm if\ }r\le e^{-A}r_0,\\ A^{-1}\log(r_0/r)&{\rm if\ }e^{-A}r_0 < r < r_0 \end{cases} $$ where $r=\lVert x-x_0\rVert_2$. The norm $\lVert f\rVert_{L^d}$ is bounded by $cr_0$ for constant $c$, so can be made small by taking $r_0$ to be small. Also, $\nabla f$ is of magnitude $1/(Ar)$ for $e^{-A}r_0 < r < r_0$. So (for some other constant $c$), \begin{align} \lVert\nabla f\rVert_{L^d}^d&=c\int_{e^{-A}r_0}^{r_0}(Ar)^{-d}\,(r^{d-1}dr)\\ &=cA^{-d}\left[\log r\right]_{e^{-A}r_0}^{r_0}=cA^{-(d-1)} \end{align} So, by taking $A$ large and $r_0$ small, we can make $\lVert f\rVert_{L^d}$ and $\lVert\nabla f\rVert_{L^d}$ as small as we like, with $f(x_0)=1$. By taking linear combinations of such functions (with $x_0$ replaced by the $x_i$ in the question, $C(f)$ can be made arbitrarily small. Clearly, the limit $C(f)=0$ is not obtained by a continuous function.

Instead, consider using the following for $C(f)$, $$ C(f)=a\left(\sum_{i=1}^N\lvert f(x_i)-d_i\rvert^p\right)^{1/p}+b\lVert f\rVert_{L^p}+c\lVert\nabla f\rVert_{L^p} \tag1 $$ for any positive constants $a,b,c$ and $p > d$. The Sobolev embedding theorem and Morrey's inequality bounds the $C^{0,\alpha}$-norm of $f$ by a positive multiple of $C(f)$, with $\alpha=1-\frac dp$. This guarantees that the limit of any sequence of continuous $f_n\colon\Omega\to\mathbb R$ with $C(f_n)$ bounded is, at the very least, $\alpha$-Hölder continuous. Any sequence $f_n$ with $C(f_n)$ converging to $\inf\{C(f)\colon \int f=0\}$ satisfies $$ a\left(\sum_{i=1}^N\lvert f_n(x_i)-f(x_i)\rvert^p\right)^{1/p}+b\lVert f_n-f\rVert_{L^p}+c\lVert\nabla(f_n-f)\rVert_{L^p}\to0 \tag2 $$ where $f\colon\Omega\to\mathbb R$ is the unique continuous function minimising $C(f)$. The convergence of $f_n$ and the existence and uniqueness of the limit $f$ follows from uniform convexity of the $L^p$ norm for $1 < p < \infty$.

$\endgroup$
16
  • $\begingroup$ I have a confusion. The norm $\||\nabla f|\|_{L^d}$ I have been using is not quite the Sobolev norm, if you had mistaken for it. I take the magnitude of gradient and then take the L^d norm, which is different from Sobolev norm. $\endgroup$
    – Rajesh D
    May 1, 2017 at 12:49
  • $\begingroup$ George, Can you please clarify? $\endgroup$
    – Rajesh D
    May 1, 2017 at 12:52
  • $\begingroup$ As all norms on $\mathbb R^d$ are equivalent, what you have is equivalent. $\endgroup$ May 1, 2017 at 12:56
  • $\begingroup$ sounds great! I like the example you have provided. By making the transition steeper and perimeter going to zero, you can trick the $L^d$ norm to zero, but can be avoided by going for a higher norm. But I wouldnt want to go any further than $L^{d+1}$ norm. $\endgroup$
    – Rajesh D
    May 1, 2017 at 13:08
  • $\begingroup$ The limit will in fact be Lipschitz, by looking at the PDE implied by your minimisation problem $\endgroup$ May 1, 2017 at 13:11
0
$\begingroup$

There will not be a continuous optimum, at least for $d = 1$. Assume that we have a solution $g$ --- we will see how to improve upon it. Write $C = C_1 + C_2 + C_3$ for the three terms of the functional.

Let $i$ be such that sign$(g(x_i)) \neq$ sign$(g(x_{i+1}))$. For concreteness, we assume that $g(x_i) > 0$, and that $\int_a^bgdx \geq 0$ (the other cases can be handled similarly). Let $(a,b) = (x_i,x_{i+1})$.

What does $g$ look like on this interval? Typically, it will be decreasing from $g(a)$ to $g(b)$, in which case $C_3(g) = g(a) - g(b)$. However, it could be that $\bar{g} := \max_{[a,b]}g(x) > g(a)$, in order to make $\int_a^bfdx$ sufficiently large (to help make $\int_\Omega f dx = 0$). In this case we will have $C_3(g) = (\bar{g} - g(a)) + (\bar{g} - g(b))$. Note that we will never have $\min_{[a,b]}g(x) < g(b)$, or $g$ could be improved.

We let $f = g$ everywhere except on $(a,b)$, so $C_1(f) = C_1(g)$. We let $k > 0$ be a large positive number, and construct $f$ on $(a,b)$ like this: i) grow linearly with rate $k$ until reaching $\bar{g}$, ii) stay constant for a time $h$, iii) decrease linearly with rate $k$ to 0, iv) stay 0, v) decrease linearly with rate $k$ to $g(b)$ at the end of the interval. Given $k$, we can always choose $h$ so that $\int_a^b f dx = \int_a^b g dx$. (In the case where $\bar{g} \leq g(a)$ step i) becomes void, and in the case $\int_a^bgdx = 0$ step ii) becomes void.)

The construction obviously gives $C_3(f) = C_3(g)$. But as $k$ increases, $C_2(f) = \int_a^b |f| dx$ will decrease downwards towards $\int_a^b f dx$, which contradicts the optimality of $g$.

The "problem" is that $C(f)$ does not penalise higher derivatives, which the construction above exploits. From a statistical learning perspective, this is usually solved by restricting the minimization of $C$-like functionals to some class of functions (the simplest examples would be ridge or lasso regressions).

$\endgroup$
14
  • $\begingroup$ What do you mean by answer is "no". You mean the solution is not unique? or Do you mean solution does not exist in this space? If so in which space the solution exist? $\endgroup$
    – Rajesh D
    Apr 28, 2017 at 11:26
  • $\begingroup$ And do you suggest infimum of $C(f)$ is same in all situations? As I stated earlier comments, I am not worried even if the minimum value not being attained, but I am fine as long as the infimum is not trivial. $\endgroup$
    – Rajesh D
    Apr 28, 2017 at 11:34
  • $\begingroup$ Yes, I mean that there cannot be an optimal continuous function (because if you show me a candidate, the construction will improve on it for sufficiently high $k$). I very much suspect that the infimum will be trivial, in some appropriate sense... The reason you can't get a continuous solution is that the optimization will "fit the data too much". $\endgroup$
    – svangen
    Apr 28, 2017 at 11:34
  • $\begingroup$ Its perfectly fine if the optimum solution is not continuous, so lets say the solution lies in a different space, I want to know what is that space? $\endgroup$
    – Rajesh D
    Apr 28, 2017 at 11:37
  • $\begingroup$ Think about the simple $N=2$ example in the comments to the OP. The optimum will be $-\alpha I_\delta +\alpha I_{1-\delta}$ for some number $\alpha>0$, where $I_x$ is the indicator function for $x$. $\endgroup$
    – svangen
    Apr 28, 2017 at 11:44

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.