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?

  • $\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$ – Pietro Majer Apr 19 '17 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 Dachiraju Apr 20 '17 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 Dachiraju Apr 20 '17 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$ – Pietro Majer Apr 20 '17 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 Dachiraju Apr 20 '17 at 9:02

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

  • $\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 Dachiraju May 1 '17 at 12:49
  • $\begingroup$ George, Can you please clarify? $\endgroup$ – Rajesh Dachiraju May 1 '17 at 12:52
  • $\begingroup$ As all norms on $\mathbb R^d$ are equivalent, what you have is equivalent. $\endgroup$ – George Lowther May 1 '17 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 Dachiraju May 1 '17 at 13:08
  • $\begingroup$ The limit will in fact be Lipschitz, by looking at the PDE implied by your minimisation problem $\endgroup$ – George Lowther May 1 '17 at 13:11

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).

  • $\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 Dachiraju Apr 28 '17 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 Dachiraju Apr 28 '17 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 '17 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 Dachiraju Apr 28 '17 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 '17 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.