Convex Optimization 2 -- Convex

Outline

• affine and convex sets
• some important examples
• operations that preserve convexity
• generalized inequalities
• separating and supporting hyperplanes
• dual cones and generalized inequalities

Affine set

    line through x_1,x_2:all points
x = \theta x_1+(1-\theta)x_2,(\theta\in\mathbb{R})

    affine set: contains the line through any two distinct points in the set.
    example: solution set of linear equations \{x|Ax=b\}
    (conversely, every affine set can be expressed as solution set of system of linear equations)

Convex set

    line segment between x_1 and x_2: all points
x = \theta x_1+(1-\theta)x_2
    with 0\leq\theta\leq1

    convex set: contains line segment between any two points in the set
x_1,x_2\in\mathbb{C},0\leq\theta\leq 1\Longrightarrow \theta x_1+(1-\theta)x_2\in\mathbb{C}

Convex combination and convex hull

    convex combination of x_1,...,x_k: any point x of the form:
x=\theta_1x_1+\theta_2x_2+...+\theta_kx_k
    with \theta_1+...+\theta_k = 1, \theta_i\geq 0

    convex hull conv S: set of all convex combinations of points in S

Convex cone

    conic (nonnegative) combination of x_1 and x_2: any point of the form
x = \theta_1x_1+\theta_2x_2
    with \theta_1\geq 0,\theta_2\geq 0

    convex cone: set that contains all conic combinations of points in the set

Hyperplanes and halfspaces

    hyperplane: set of the form \{x|a^Tx=b\}(a\ne 0)

    halfspace: set of the form \{x|a^Tx\leq b\}(a\ne 0)
        - a is the normal vector
        - hyperplanes are affine and convex; halfspaces are convex

Euclidean balls and ellipsoids

    (Euclidean) ball with center x_c and radius r:
B(x_c,r)=\{x|\ ||x-x_c||_2\leq r\}=\{x_c+ru|\ ||u||_2\leq 1\}

    ellipsoid: set of the form
\{x|(x-x_c)^TP^{-1}(x-x_c)\leq 1
    with P\in \mathbb{S_{++}^n}(i.e. P symmetric positive definite)
    other representation: \{x_c+Au|\ ||u||_2\leq 1\} with A square and nonsingular.

Norm balls and norm cones

    norm: a function ||\cdot|| that satisfies
        - ||x||\geq0,||x||=0 if and only if x=0
        - ||tx||=|t|||x|| for t\in\mathbb{R}
        - ||x+y||\leq||x||+||y||

    norm ball with center x_c and radius r:\{x|\ ||x-x_c||\leq r\}

    norm cone: \{(x,t)|\ ||x||\leq t\}

    Euclidean norm cone is called second-order cone

    norm balls and cones are convex

Polyhedra

    solution set of finitely many linear inequalities and equalities
Ax\preceq b,\qquad Cx=d
        (A\in \mathbb{R}^{m\times n},C\in \mathbb{R}^{p\times n})

Polyhedra.jpg

polyhedron is intersection of finite number of halfspaces and hyperplanes.

Positive semidefinite cone

    notation:
        - \mathbb{S}^n is set of symmetric n\times n matrices
        - \mathbb{S}_{+}^{n} = \{X\in\mathbb{S}^n| X\succeq 0\}: positive semidefinite n\times n matrices
X\in\mathbb{S}_{+}^{n} \Longleftrightarrow z^TXz\geq0 \ for\ all\ z
            \mathbb{S}_{+}^{n} is a convex cone
        - \mathbb{S}_{+}^{n} = \{X\in\mathbb{S}^n| X\succ 0\}: positive definite n\times n matrices

Positive semidefinite cone.jpg

Operations that preserve convexity

    practical methods for establishing convexity of a set C
    1. apply definition
x_1,x_2\in C,\quad 0\leq\theta\leq 1 \Longrightarrow \theta x_1+(1-\theta)x_2\in C
    2. show that C is obtained from simple convex sets (hyperplanes, halfspaces, norm balls, ...) by operations that preserve convexity
        - intersection
        - affine functions
        - perspective function
        - linear-fractional functions

    intersection: the intersection of any number of convex sets is convex
    Affine function: suppose f:\mathbb{R}^n\to\mathbb{R}^m is affine (f(x) = Ax+b with A\in\mathbb{R}^{m\times n},b\in\mathbb{R}^m)
        - the image of a convex set under f is convex
        - the inverse image f^{-1}(C) of a convex set under f is convex.
    examples:
        - scaling, translation, projection
        - solution set of linear matrix inequality \{x| x_1A_1+...+x_mA_m\preceq B\} (with A_i,B\in\mathbb{S}^p)
        - hyperbolic cone \{x| x^TPx\leq(c^Tx)^2,c^Tx\geq 0\}(with P\in\mathbb{S}_{+}^{n})
    Perspective and linear-fractional function
        -perspective funtion P:\mathbb{R}^{n+1}\to\mathbb{R}^n:
P(x,t)=x/t,\qquad domP=\{(x,t)|t\ >0\}
    images and inverse images of convex sets under perspective are convex.

        -linear-fractional function f:\mathbb{R}^n\to\mathbb{R}^m:
f(x)=\frac{Ax+b}{c^Tx+d},\qquad dom f=\{x| c^Tx+d>0\}
    images and inverse images of convex sets under linear-fractional functions are convex.

Generalized inequalities

a convex cone K\subset\mathbb{R}^n is a proper cone if

• K is closed (contains its boundary)
• K is solid (has nonempty interior)
• K is pointed (contains no line)

examples

• nonnegative orthant K=\mathbb{R}_{+}^{n}=\{x\in\mathbb{R}^n| x_i\geq0,i=1,..,n\}
• positive semidefinite cone K = \mathbb{S}_{+}^{n}
• nonnegative polynomials on [0,1]:
  K=\{x\in\mathbb{R}^n| x_1+x_2t+x_3t^2+...+x_nt^{n-1}\geq0\ for\ t\in[0,1]\}

generalized inequality defined by a proper cone K:
x\preceq_{K} y \Longleftrightarrow y-x\in K,x\prec_{K} y \Longleftrightarrow y-x\in \textbf{int}K
properties: many properties of \preceq_K are similar to \leq on \mathbb{R},e.g.,
x\preceq_K y,\quad u\preceq_Kv \Longrightarrow x+u\preceq_K y+v

Minimum and minimal elements
\preceq_K is not in general a \textit{linear ordering}

x\in\mathbb{S} is the minimum element of S with respect to \preceq_K if
y\in\mathbb{S}\Longrightarrow x\preceq_K y
x\in\mathbb{S} is a minimal element of S with respect to \preceq_K if
y\in\mathbb{S},y\preceq_K x\Longrightarrow y=x

Differences.jpg

Separating hyperplane theorem

if C and D are disjoint convex sets, then there exists a\ne 0,b such that
a^Tx\leq b\ for\ x\in C,\quad a^Tx\geq b\ for\ x\in D
the hyperplane \{x | a^Tx = b\} separates C and D

strict separation requires additional assumptions(e.g.,C is closed, D is a singleton)

Supporting hyperplane theorem

supporting hyperplane to set C at boundary point x_0:
\{x| a^Tx = a^Tx_0\}
where a\ne 0 and a^Tx\leq a^Tx_0 for all x\in C

supporting hyperplane theorem: if C is convex, then exists a supporting hyperplane at every boundary point of C

Dual cones and generalized inequalities

dual cone of a cone K:
K^* = \{y| y^Tx\geq 0\ for\ all\ x\in K\}
examples:

• K = \mathbb{R}_{+}^n: K^* = \mathbb{R}_+^n

• K = \mathbb{S}_{+}^n: K^* = \mathbb{S}_+^n

• K = \{(x,t)|\ ||x||_2\leq t\}: K^*=\{(x,t)|\ ||x||_2\leq t\}

• K = \{(x,t)|\ ||x||_1\leq t\}: K^*=\{(x,t)|\ ||x||_{\infty}\leq t\}
  first three examples are self-dual cones
  dual cones of proper cones are proper, hence define generalized inequalities:
  y\succeq_{K^*} 0 \Longleftrightarrow y^Tx\geq0\ for\ all\ x\succeq_K 0

Minimum and minimal elements via dual inequalities

minimum element w.r.t. \preceq_K
x is minimum element of S iff for all \lambda\succ_{K^*}0,x is the unique minimizer of \lambda^Tz over S

minimal element w.r.t. \preceq_K

• if x minimizes \lambda^Tz over S for some \lambda\succ_{K^*}0, then x is minimal
• if x is a minimal element of a convex set S, then there exists a nonzero \lambda\succeq_{K^*}0 such that x minimizes \lambda^Tz over S
  Examples:
  Examples.jpg