notes on convex optimization (1): convex sets

1. Affine and Convex Sets

Suppose $x_1ne x_2$ are two points in $mathbb{R}^n$.

1.1 Affine sets

line through $x_1$, $x_2$: all points

$$x=theta x_1 + (1-theta)x_2quad(theta in mathbb{R})$$

affine set: contains the line through any two distinct points in the set

$$x_1,x_2in C, thetainmathbb{R} Longrightarrow theta x_1 + (1-theta)x_2 in C$$

1.2 Convex sets

line segment between $x_1$ and $x_2$: all points

$$x=theta x_1 + (1-theta)x_2$$

with $0leqthetaleq1$

convex set: contains line segment between any two points in the set

$$x_1,x_2in C, 0leqthetaleq1 Longrightarrow theta x_1 + (1-theta)x_2 in C$$

convex combination of $x_1,dots,x_k$: any point $x$ of the form

$$x=theta_1x_1+theta_2x_2+dots+theta_kx_k$$

with $theta_1+dots+theta_k=1,theta_i geq 0$

convex hull of a set $C$, denoted $mathbf{conv} C$: set of all convex combinations of points in $C$

1.3 Cones

conic 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

$$x_1,x_2in C, theta_1ge0, theta_2ge0 Longrightarrow theta_1 x_1 + theta_2x_2 in C$$

2. Some Important Examples

2.1 Hyperplanes and halfspaces

hyperplane: set of the form {$xmid a^Tx=b$}$(ane0)$

halfspace: set of the form {$xmid a^Txleq b$}$(ane0)$

• $a$ is the normal vector
• hyperplanes are affine and convex; halfspaces are convex

2.2 Euclidean balls and ellipsoids

(Euclidean) ball with center $x_c$ and radius $r$:

$$B(x_c,r)={xmidlVert x-x_crVert_2leq r}={x_c+ru midlVert u rVert_2 leq 1 }$$

ellipsoid: set of the form

$${x mid (x-x_c)^TP^{-1}(x-x_c)leq 1}$$

with $Pin mathbf{S}^n_{++}$ (i.e., P symmetric positive definite)

another representation: {$x_c+Aumid lVert urVert_2le1$} with $A$ square and nonsingular

• Euclidean balls and ellipsoids are all convex.

2.3 Norm balls and norm cones

norm: a funtion $lVert centerdot rVert$ that satisfies

• $lVert x rVert geq 0$; $lVert x rVert=0$ if and only if $x=0$
• $lVert tx rVert = lvert t rvert lVert x rVert$ for $tin mathbb{R}$
• $lVert x+yrVert leq lVert x rVert+lVert y rVert$

norm ball with center $x_c$ and radius $r: {x mid lVert x-x_c rVert leq r}$

norm cone: ${(x,t) mid lVert x rVert leq t}$

• norm balls and cones are convex
• norm cores (as the name suggest) are convex cones

2.4 Polyhedra

polyhedra: solution set of finitely many linear inequalities and equalities

$$Ax preceq b, quad Cx=d$$

($Ain mathbb{R}^{mtimes n}$, $Cinmathbb{R}^{ptimes n}$, $preceq$ is componentwise inequality)

• polyhedron is intersection of finite number of halfspaces and hyperplances

2.5 The positive semidefinite cone

positive semidefinite cone:

• $mathbf{S}^n$ is set of symmetric $ntimes n$ matrices
• $mathbf{S}^n_+={Xinmathbf{S}^nmid Xsucceq0}$: positive semidefinite $ntimes n$ matrices $Xinmathbf{S}^n_+ iff z^TXz geq 0 mathrm{for all }z$ $mathbf{S}^n_+$ is a convex cone
• $mathbf{S}^n_{++}={Xinmathbf{S}^nmid Xsucc0}$: positive definite $ntimes n$ matrices

3. Operations that preserve convexity

intersection: the interction of (any number of) convex sets is convex

affine function: suppose $f: mathbb{R}^n rightarrow mathbb{R}^m$ is affine ($f(x)=Ax+b$ with $Ainmathbb{R}^{mtimes n}, binmathbb{R}^m$)

• the image of a convex set under $f$ is convex

$$S subseteq mathbb{R}^n convex Longrightarrow f(S)={f(x)mid xin S} convex$$

• the inverse image $f^{-1}(C)$ of a convex set under $f$ is convex

$$C subseteq mathbb{R}^m convex Longrightarrow f^{-1}(C)={xinmathbb{R}^nmid f(x)in C} convex$$

perspective function $P: mathbb{R}^{n+1} rightarrow mathbb{R}^n$:

$$P(x,t)=x/t, quad mathbf{dom} P={(x,t)mid t>0}$$

images and inverse images of convex sets under perspective are convex

linear-fractional function $f:mathbb{R}^n rightarrow mathbb{R}^m$:

$$f(x)=frac{Ax+b}{c^Tx+d}, quad mathbf{dom} f={xmid c^Tx+d>0}$$

images and inverse images of convex sets under linear-fractional functions are convex

4. Generalized Inequalities

4.1 Proper cones and generalized inequalities

a convex cone $Ksubseteqmathbb{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)

generalized inequality defined by a proper cone $K$:

$$% <![CDATA[ begin{split} x preceq_K y &iff y-x in K\ x prec_K y &iff y-x in mathbf{int} K end{split} %]]>$$

4.2 Minimum and minimal elements

$xin S$ is the minimum element of $S$ with respect to $preceq_K$ if

$$y in S Longrightarrow x preceq_K y$$

$xin S$ is a minimal element of $S$ with respect to $preceq_K$ if

$$y in S, y preceq_K x Longrightarrow y=x$$

5. Separating and Supporting Hyperplanes

separating hyperplane theorem: if $C$ and $D$ are disjoint convex sets, then there exists $ane0$, $b$ such that

$$a^Tx le b mathrm{for} xin C,quad a^Txge b mathrm{for} xin D$$

supporting hyperplane to set $C$ at boundary point $x_0$:

$${xmid a^Tx=a^Tx_0}$$

where $ane0$ and $a^Txle a^Tx_0$ for all $xin C$

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

6. Dual Cones and Generalized Inequalities

6.1 Dual cones

dual cone of a cone $K$:

$$K^*={ymid y^T x ge 0mathrm{ for all } xin K}$$

Dual cons satisfy several properties, such as:

• $K^*$ is closed and convex
• $K_1 subseteq K_2$ imples $K_2^* subseteq K_1^*$
• $K^{**}$ is the closure of the convex hull of $K$ (Hence if $K$ is convex and closed, $K^{**}=K$)

Thsese properties show that if $K$ is a proper cone, then so is its dual $K^{*}$, and moreover, that $K^{**}=K$

6.2 Dual generalized inequalities

dual cones of proper cones are proper, hence define generalized inequalities:

$$ysucceq_{K^*}0 iff y^Txge0mathrm{ for all } xsucceq_K0$$

Some import properties relating a generalized inequality and its dual are:

• $xpreceq_K y$ iff $lambda^Tx le lambda^Ty$ for all $lambda succeq_{K^{*}} 0$
• $xprec_K y$ iff $lambda^Tx < lambda^Ty$ for all $lambda succ_{K^{*}} 0, lambdane0$

Since $K=K^{**}$, the dual generalized inequality associated with $preceq_{K^{*}}$ is $preceq_K$, so these properties hold if the generalized inequality and its dual are swapped

6.3 Minimum and minimal elements via dual inequalities

dual characterization of 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 $zin S$

dual characterization of 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 $z in S$