Convex Optimization Notes

Convex Optimization

• 2.1.1 Line

  Suppose $x_1\ne x_2$ are two points in ${\mathbb{R}}^n$. Points of the form

  $$y=\theta x1+(1-\theta )x2$$

  where θ ∈ R, form the line passing through $x_1$ and $x_2$.

• 2.1.2 Affine sets

  (It is hyperplane (may not passing the origin))

  A set $C\subseteq {\mathbb{R}}^n$ is affine if the line through any two distinct points in $C$ lies in $C$

  We refer to a point of the form ${\theta }_1{x}_1+···+{\theta }_k{x}_k,\text{ where }{\theta }_1+···+{\theta }_k=1$, as an affine combination of the points $x_1,...,x_k$

  If $C$ is an affine set and $x_0\in C$, then the set

  $$V=C-x_0=\{x-x_0|x\in C\}$$

  is a subspace

  The set of all affine combinations of points in some set $C\subseteq \mathbb{R}$ n is called the affine hull of $C$, and denoted $\mathrm{aff}C$:

  $$\mathrm{aff}C=\{{\theta }_1{x}_1+\cdots +{\theta }_k{x}_k|x_1,\dots ,x_k\in C,{\theta }_1+\dots +{\theta }_k=1\}$$

  The affine hull is the smallest affine set that contains $C$

• 2.1.3 Affine dimension and relative interior

  We define the affine dimension of a set $C$ as the dimension of its affine hull

  We define the relative interior of the set $C$, denoted $\mathrm{relint}C$ as its interior relative to $\mathrm{aff}C$:

  $$\mathrm{relint}=\{x\in C|B(x,r)\cap affC\subseteq C\text{ for some }r>0\}$$

  where $B(x,r)=\{y|\Vert y-x\Vert \le r\}$, the ball of radius $r$ and center $x$ in the norm $\Vert \cdot \Vert$

  We can then define the relative boundary of a set $C$ as $\mathrm{cl}C\setminus \mathrm{relint}C$, where $\mathrm{cl}C$ is the closure of C.

• 2.1.4 Convex sets

  A set $C$ is convex iff

  $$\theta x_1+(1-\theta )x_2\in C,\mathrm{\forall }\theta \in [0,1],x_1,x_2\in C$$

  Roughly speaking, a set is convex if every point in the set can be seen by every other point, along an unobstructed straight path between them, where unobstructed means lying in the set. Every affine set is also convex, since it contains the entire line between any two distinct points in it, and therefore also the line segment between the points.

  We call a point of the form ${\theta }_1{x}_1+\cdots +{\theta }_k{x}_k$, where ${\theta }_1+\cdots +{\theta }_k=1$ and ${\theta }_i\ge 0$, a convex combination of the points $x_1,\dots ,x_k$. As with affine sets, it can be shown that a set is convex if and only if it contain contains every convex combination of its points. A convex combination of points can be thought of as a mixture or weighted average of the points, with ${\theta }_i$ the fraction of $x_i$ in the mixture.

  The convex hull of a set $C$, denoted $\mathrm{conv}C$, is the set of all convex combinations of points in $C$:

  $$\mathrm{conv}C=\{{\theta }_1{x}_1+\dots +{\theta }_k{x}_k|x_i\in C,{\theta }_i\ge 0{\theta }_1+\cdots +{\theta }_k=1\}$$

  As the name suggests, the convex hull $\mathrm{conv}C$ is always convex. It is the smallest convex set that contains $C$

• 2.1.5 Cones

  A set $C$ is called a cone, or nonnegative homogeneous, if for every $x\in C$ and $\theta \ge 0$, we have $\theta x\in C$. A set $C$ is a convex cone if it is convex and a cone, which means that for any$x1,x2\in C$ and $\theta 1,\theta 2\ge 0$, we have

  $${\theta }_1{x}_1+{\theta }_2{x}_2\in C.$$

  A point of the form ${\theta }_1{x}_1+\cdots +{\theta }_k{x}_k$ with ${\theta }_1,\dots ,{\theta }_k\ge 0$ is called a conic combination (or a nonnegative linear combination) of $x_1,\dots ,x_k$. If $x_i$ are in a convex cone $C$, then every conic combination of $x_i$ is in $C$. Conversely, a set $C$ is a convex cone if and only if it contains all conic combinations of its elements.

  The conic hull of a set $C$ is the set of all conic combinations of points in $C$, i.e.,

  $$\{{\theta }_1{x}_1+\cdots +{\theta }_k{x}_k|x_i\in C,{\theta }_i\ge 0,i=1,\dots ,k\}$$

  which is also the smallest convex cone that contains $C$.

Convex functions

• 3.1 Basic properties and examples

• 3.1.1 Definition

  A function $f:{\mathbb{R}}^n\mapsto \mathbb{R}$ is convex if $\mathrm{dom}f$ is a convex set and

  $$\mathrm{\forall }x,y\in \mathrm{dom}f,0\le \theta \le 1,f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)$$

  We say $f$ is concave if $-f$ is convex, and strictly concave if $-f$ is strictly convex.

  A function is convex if and only if it is convex when restricted to any line that intersects its domain. In other words $f$ is convex if and only if for all $x\in \mathrm{dom}f$ and all $v$, the function $g(t)=f(x+tv)$ is convex (on its domain, $\{t|x+tv\in \mathrm{dom}f\}$). This property is very useful, since it allows us to check whether a function is convex by restricting it to a line.

• 3.1.2 Extended-value extensions

  It is often convenient to extend a convex function to all of ${\mathbb{R}}^n$ by defining its value $f$ to be $\mathrm{\infty }$ outside its domain.

  If f is convex we define its extended-value extension $\tilde{f}:{\mathbb{R}}^n\mapsto \mathbb{R}\cup \{\mathrm{\infty }\}$ by

  $$\tilde{f}(x)=\{\begin{array}{ll}f(x)& x\in \mathrm{dom}f.\\ \mathrm{\infty }& x\notin \mathrm{dom}f.\end{array}$$

• 3.1.3 First-order conditions

  Suppose $f$ is differentiable (i.e., its gradient $\nabla f$ exists at each point in $\mathrm{dom}f$, which is open). Then $f$ is convex if and only if $\mathrm{dom}f$ is convex and $f(y)\ge f(x)+\nabla f(x{)}^T(y-x)$ holds for all $x,y\in \mathrm{dom}f$

  Strict convexity can also be characterized by a first-order condition: $f$ is strictly convex if and only if $\mathrm{dom}f$ is convex and for $x,y\in \mathrm{dom}f,x\ne y$, we have

  $$f(y)>f(x)+\nabla f(x{)}^T(y-x).$$

• 3.1.4 Second-order conditions

  We now assume that $f$ is twice differentiable, that is, its Hessian or second derivative ${\nabla }^{2}f$ exists at each point in $\mathrm{dom}f$, which is open. Then $f$ is convex if and only if $\mathrm{dom}f$ is convex and its Hessian is positive semidefinite: for all $x\in \mathrm{dom}f$

  $${\nabla }^{2}f(x)⪰0.$$

  Strict convexity can be partially characterized by second-order conditions. If ${\nabla }^{2}f(x)\succ 0$ for all $x\in \mathrm{dom}f$, then $f$ is strictly convex. The converse, however, is not true: for example, the function $f:\mathbb{R}\mapsto \mathbb{R}$ given by $f(x)=x^4$ is strictly convex but has zero second derivative at $x=0$.

  Remark 3.1 The separate requirement that $\mathrm{dom}f$ be convex cannot be dropped from the first- or second-order characterizations of convexity and concavity. For example, the function $f(x)=\frac{1}{x2}$, with $\mathrm{dom}f=\{x\in R|x\ne 0\}$, satisfies $f^{″}(x)>0$ for all $x\in \mathrm{dom}f$, but is not a convex function.

• 3.1.6 Sublevel sets

  The $\alpha$-sublevel set of a function $f:{\mathbb{R}}^n\mapsto R$ is defined as

  $C_{\alpha }=\{x\in \mathrm{dom}f|f(x)\le \alpha \}$.

• 3.1.7 Epigraph

  The epigraph of a function $f:{\mathbb{R}}^n\mapsto R$ is defined as

  $$\mathrm{epi}f=\{(x,t)|x\in \mathrm{dom}f,f(x)\le t\}$$

• 3.1.8 Jensen’s inequality and extensions

• 3.1.9 Inequalities