1
$\begingroup$

Let $f(x)$ be a convex function on $\Pi = [a,b] \times [c,d]$ such that there exists $y \in \mathbb{R}^2$ with property $ y\cdot x\geq f(x), \;\;\; \forall x \in \Pi. $ I want to find such $y$.

Let $x_{j}$, $j=\overline{1,4}$ be corners of $\Pi$. I solve systems $ \left\{ \begin{array}{rcl} y \cdot x_{i_1} & = & f(x_{i_1}), \\ y \cdot x_{i_2} & = & f(x_{i_2}) \end{array}\right. $ for different pairs $(i_1 i_2)$ of corner points and test property $y \cdot x_{i} \geq f(x_{i})$ for two different corner points.

Question 1. Is it true that if these inequalities hold, then $ y \cdot x \geq f(x), \;\;\; \forall x \in \Pi, $ i.e. found $y$ solves my problem?

Question 2. Is it possible that my procedure will not give a solution of my problem?

  • 0
    Use the fact that if point $P$ is within a convex quadrilateral $ABCD$, then $P= aA + bB + cC + dD$ for some $a+b+c+d = 1$ and $0 \leq a, b, c , d\leq 1$. (This holds for all convex polygons, and you can even require that at most 3 coefficients are non-zero.)2012-12-31

2 Answers 2

2

Q1: yes. Your goal is to make sure that the maximum of the convex function $g_y(x)=f(x)-x\cdot y$ on $\Pi$ is at most $0$. Any convex function $g_y$ attains its maximum on $\Pi$ at an extreme point, and the extreme points of $\Pi$ are exactly the vertices. (For a rectangle one can prove this directly by considering one-dimensional restrictions of $g_y$.) Thus, if you found $y$ such that $g_y\le 0$ at all vertices, you have a solution.

Q2: no. If there is $y_0$ such that $g_{y_0}\le 0$ on $\Pi$, then there is also a solution $y^*$ such that $g_{y^*}=0$ at two of the vertices of $\Pi$. Indeed, from the family $\{ty_0 : t\in\mathbb R\}$ you can pick a solution $y_1$ such that $g_{y_1}=0$ at some vertex $v$ of $\Pi$. Let $\ell:\mathbb R^2\to\mathbb R$ be a nonzero linear function that vanishes at $v$. Consider the family $\{y_1+t\ell : t\in\mathbb R\}$ and pick a solution that vanishes at another vertex of $\Pi$. Done. (Clarification: in both steps, consider the set of all $t$ for which the vector is a solution, and pick a boundary point of that set.)

0

Here's another way to look at part 2. Consider the vertices and their function values as points in 3D space, $(x_i, f(x_i))$, and take the convex hull of their union with the origin. The existence of a solution $y\cdot x\ge f(x)$ implies that the origin does not lie in the interior of the convex hull. Then the convex hull has at least one triangular face which contains the origin and whose normal points upwards; this corresponds to a $y$ such that $y\cdot x_i=f(x_i)$ on the two vertices of the face, and $y\cdot x_i\ge f(x_i)$ on all other points.