MHB Inequality proof - for determining convex set

AI Thread Summary
The discussion revolves around proving that the set defined by the inequality \( \Omega = \{ \textbf{x} \in \mathbb{R}^2 | x_1^2 - x_2 \leq 6 \} \) is convex. The key step involves showing that for any two points \( \textbf{x} \) and \( \textbf{y} \) in the set, the convex combination \( \theta \textbf{x} + (1-\theta) \textbf{y} \) also satisfies the inequality. Participants suggest starting from the inequalities \( x_2 \geq x_1^2 - 6 \) and \( y_2 \geq y_1^2 - 6 \) to establish that the left-hand side of the convex combination is greater than or equal to the right-hand side. The proof ultimately simplifies to showing that a certain quadratic expression is non-negative, confirming the convexity of the set. The discussion concludes with the successful simplification of the expression, affirming the convexity condition.
numbersense
Messages
4
Reaction score
0
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.
 
Physics news on Phys.org
numbersense said:
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:

View attachment 721

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?
 

Attachments

  • problem-parabola.png
    problem-parabola.png
    1.6 KB · Views: 84
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]$.
 
numbersense said:
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! ;)
 

Similar threads

Replies
1
Views
1K
Replies
1
Views
1K
Replies
6
Views
1K
Replies
6
Views
2K
Replies
6
Views
1K
Replies
1
Views
2K
Replies
2
Views
2K
Back
Top