1
$\begingroup$

I guess my question is a follow up question of this one: usul, Existence of a strictly convex function interpolating given gradients and values, version: 2019-04-13.

In usul's question, the answer proves the existence of such a convex function. I think the assumption the question has - "For each point, we are given a linear function through it and strictly below the others" is very interesting. It's not difficult for us to construct such a convex function if the assumption is true. However, I am more interested in what conditions could make the assumption to be true?

In other words, I think my question is: suppose we are given a finite set $C$ with cardinality $T$ of pairs $(x,y) \in C$, with $x \in \mathbb{R}^d$ and $y \in \mathbb{R}$, under what conditions of $X = \{x_1, \dotsc, x_T\}$ and $Y = \{y_1, \dotsc, y_T\}$, can we construct $T$ linear functions $L =\{l_1, \dotsc, l_T\}$ such that each linear function $l_i$ passes through $(x_i, y_i)$ and is strictly below other points?

The mathematical formula for the above question may be written as the following: let each linear function $l_i = k_i(x - x_i) + y_i$, then the above question is to decide whether there exist a sequence of $K = \{k_1, \dotsc, k_T\}$ such that $l_i(x_i) > l_j(x_i)$, i.e., $$ y_i > k_j(x_i - x_j) + y_j \,\, \forall i\neq j. $$ Then I think the question is to decide the existence of such a sequence of $K$ which I am not sure about the answer. Also, I don't know if the above mathematical representation is the best way to solve this problem. Feel free to come up with your own method if my initial thinking doesn't work.

Updated: an image from usul's question so this question could be more intuitive: a strictly convex function through the given points with the given gradients

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ Maybe I don't understand the question ... isn't the condition just that each point should lie below the line joining the two points to either side of it? $\endgroup$
    – Nik Weaver
    Commented Apr 14, 2020 at 21:09
  • $\begingroup$ MathJax supports links, so I combined the separate text-and-URLs into a single link. Since you were concerned with pointing to a specific revision, I linked that, too. Also, the problem has two answers; I picked the one that seemed more likely and linked that. I hope that all this is agreeable. $\endgroup$
    – LSpice
    Commented Apr 14, 2020 at 22:19
  • $\begingroup$ Nik's understanding is correct, but my question is what kind of sequences of $X$ and $Y$ can make this condition (i.e. each point should lie below the line joining the two points to either side of it) be satisfied? For example, give some points $\{(0,1), (1,0), (2,1)\}$ (i.e. $f(x) = (x-1)^2$), we know we can construct 3 linear functions as desired. However, if we are given a set of $\{(0,-1), (1, 0), (2, -1)\}$ then we can't construct such linear functions. Therefore, my question is: if we are given a set of points, can we construct such linear functions? $\endgroup$
    – Francis
    Commented Apr 15, 2020 at 2:37
  • $\begingroup$ To be more specific, my question is like the following: given variable sequence $\{ x_t \}_{t \in [T]} $ and function value sequence $\{ y_t \}_{t \in [T]} $, when would it be possible to find a concave function $u$ such that $u(x_t) = y_t$. $\endgroup$
    – Francis
    Commented Apr 15, 2020 at 3:22
  • $\begingroup$ I think another problem here is that my $x$ is in $d$ dimension. Therefore, we don't have such kind of "neighboring relationship from Nik's comment" for the points, i.e. we don't have an ordering for the $\{x_t\}_{t\in T}$ so we don't have neighboring points for each point. $\endgroup$
    – Francis
    Commented Apr 20, 2020 at 20:39

0

Reset to default

You must log in to answer this question.