Welcome to our community

Be a part of something great, join today!

[SOLVED] Inequality proof - for determining convex set

numbersense

New member
Mar 26, 2013
5
I am stuck at the inequality proof of this convext set problem.

$\Omega = \{ \textbf{x} \in \mathbb{R}^2 | x_1^2 - x_2 \leq 6 \}$

The set should be a convex set, meaning for $\textbf{x}, \textbf{y} \in \mathbb{R}^2$ and $\theta \in [0,1]$, $\theta \textbf{x} + (1-\theta)\textbf{y}$ also belong to $\Omega$.

How can I show that $(\theta x_1 + (1-\theta)y_1)^2 - (\theta x_2 + (1-\theta)y_2) \leq 6$?

I am stuck after expanding the LHS.
\begin{align*}
& (\theta x_1 + (1-\theta)y_1)^2 - (\theta x_2 + (1-\theta)y_2) \\
=& \theta^2 x_1^2 + 2\theta(1 - \theta)x_1 y_1 + (1 - \theta)^2 y_1^2 - \theta x_2 - (1 - \theta) y_2
\end{align*}

Any hints or pointers are welcome. Thanks in advance.
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,774
I am stuck at the inequality proof of this convext set problem.

$\Omega = \{ \textbf{x} \in \mathbb{R}^2 | x_1^2 - x_2 \leq 6 \}$

The set should be a convex set, meaning for $\textbf{x}, \textbf{y} \in \mathbb{R}^2$ and $\theta \in [0,1]$, $\theta \textbf{x} + (1-\theta)\textbf{y}$ also belong to $\Omega$.

How can I show that $(\theta x_1 + (1-\theta)y_1)^2 - (\theta x_2 + (1-\theta)y_2) \leq 6$?

I am stuck after expanding the LHS.
\begin{align*}
& (\theta x_1 + (1-\theta)y_1)^2 - (\theta x_2 + (1-\theta)y_2) \\
=& \theta^2 x_1^2 + 2\theta(1 - \theta)x_1 y_1 + (1 - \theta)^2 y_1^2 - \theta x_2 - (1 - \theta) y_2
\end{align*}

Any hints or pointers are welcome. Thanks in advance.
Welcome to MHB, numbersense! :)

Graphically, your problem is that any weighted mean of 2 points above the parabola $x^2-6$ is also above that parabola.
Something like this:

problem-parabola.png

Summarized, your problem is that:
$$\text{Given} \\
\qquad x_2 \ge x_1^2 - 6 \qquad (1) \\
\qquad y_2 \ge y_1^2 - 6 \qquad (2) \\
\text{Proof that: } \theta x_2 + (1-\theta)y_2 \ge (\theta x_1 + (1-\theta)y_1)^2 - 6 \qquad (3)$$

Starting with the LHS of (3), we get with (1) and (2) that:
$$\theta x_2 + (1-\theta)y_2 \ge \theta (x_1^2 - 6) + (1-\theta)(y_1^2 - 6) = \theta x_1^2 + (1-\theta)y_1^2 - 6 \qquad (4)$$

So we're left to proof that:
$$(\theta x_1^2 + (1-\theta)y_1^2) - (\theta x_1 + (1-\theta)y_1)^2 \overset{?}{\ge} 0 \qquad (5)$$

Can you simplify that?
 

numbersense

New member
Mar 26, 2013
5
Thank you I like Serena! I think I managed to simplify that.

\begin{align*}
& \theta x_1^2 + (1 - \theta) y_1^2 - (\theta x_1 + (1-\theta) y_1)^2 \\
=& \theta x_1^2 + (1-\theta)y_1^2 - ( \theta^2 x_1^2 + 2 (\theta - \theta^2) x_1 y_1 + (1-2\theta + \theta^2) y_1^2)\\
=& (\theta - \theta^2) x_1^2 - 2(\theta - \theta^2)x_1 y_1 + (\theta - \theta^2) y_1^2\\
=& \left((\theta - \theta^2)^\frac{1}{2} x_1 - (\theta - \theta^2)^\frac{1}{2} y_1\right)^2\\
\geq & 0
\end{align*}

$\theta - \theta^2 \geq 0$ as $\theta \in [0,1]$.
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,774
Thank you I like Serena! I think I managed to simplify that.

\begin{align*}
& \theta x_1^2 + (1 - \theta) y_1^2 - (\theta x_1 + (1-\theta) y_1)^2 \\
=& \theta x_1^2 + (1-\theta)y_1^2 - ( \theta^2 x_1^2 + 2 (\theta - \theta^2) x_1 y_1 + (1-2\theta + \theta^2) y_1^2)\\
=& (\theta - \theta^2) x_1^2 - 2(\theta - \theta^2)x_1 y_1 + (\theta - \theta^2) y_1^2\\
=& \left((\theta - \theta^2)^\frac{1}{2} x_1 - (\theta - \theta^2)^\frac{1}{2} y_1\right)^2\\
\geq & 0
\end{align*}

$\theta - \theta^2 \geq 0$ as $\theta \in [0,1]$.
Yep! ;)