Homework 3

Due: Oct. 22, 14:00:00

Midpoint convexity

1. A set $C\subseteq {\mathbb{R}}^n$$C \subseteq \mathbb{R}^n$ is midpoint convex, if for all $u,v\in C$$u, v \in C$, the midpoint $(u+v)/2$$(u+v)/2$ is also in $C$$C$. Obviously convex sets are also midpoint convex.

   Do you think midpoint convex sets are also convex?

   If not, please give a counterexample that is midpoint convex but not convex, and then add some mild conditions (like continuity for midpoint convex functions) to make midpoint convex sets become convex. Prove your claim.

Separating and supporting hyperplanes

2. Express the convex set $\{(x,y)\in {\mathbb{R}}_{\ge 0}^2:xy\ge 1\}$$\{(x, y) \in \mathbb{R}_{\geq 0}^2: xy \geq 1\}$ as an intersection of halfspaces.

Convex functions

3. The $\alpha$$\alpha$-sublevel set of a function $f:D\subseteq {\mathbb{R}}^n\to \mathbb{R}$$f:D\subseteq\mathbb{R}^n\to \mathbb{R}$ is defined as $C_{\alpha }=\{x\in D:f(x)\le \alpha \}$$C_\alpha=\{x\in D: f(x)\leq \alpha\}$. Show that sublevel sets of a convex function are convex for any value of $\alpha$$\alpha$.

   In particular, show that the set of global minima of a convex function is convex. Namely, the set $M=\{x^{\ast }:f(x^{\ast })\le f(x),\mathrm{\forall }x\in D\}$$M=\{x^*:f(x^*)\leq f(x), \forall x\in D\}$ is also convex if $f$$f$ is convex.

4. Suppose $f:{\mathbb{R}}^n\to \mathbb{R}$$f:\mathbb{R}^n\to \mathbb{R}$ is convex and bounded above over ${\mathbb{R}}^n$$\mathbb{R}^n$. Show that $f$$f$ is constant.

5. Suppose $f,g:{\mathbb{R}}^n\to \mathbb{R}$$f,g:\mathbb{R}^n\to \mathbb{R}$ are two functions defined on ${\mathbb{R}}^n$$\mathbb{R}^n$, $f$$f$ is convex and $g$$g$ is concave. Show that if $g(x)\le f(x)$$g(x)\leq f(x)$ for all $x\in {\mathbb{R}}^n$$x\in \mathbb{R}^n$, there exists an affine function $h$$h$ such that $g(x)\le h(x)\le f(x)$$g(x) \leq h(x) \leq f(x)$ for all $x\in {\mathbb{R}}^n$$x\in \mathbb{R}^n$.