[笔记] Convex Optimization 2015.10.21

int(K) : interior of K

• Definition: Cone K is proper if it is closed, convex, pointed (contains no line), solid (nonempty interior)
  If K is proper, then K∗ is proper, K∗={λ:λTx≥0∀x∈K}
• Fact1: x⪰ky⟺λTx≥λTy∀λs.t.λ⪰K∗0
• Proof: x⪰ky⟺x−y∈K⟺becauseK∗∗=KλT(x−y)≥0∀λ∈K∗
• Lemma: Let K be proper, then x∈int(K) if and only if λTx>0∀λ∈K∗∖{0}
• Proof: If x∈int(K) then obviously λTx≥0 for all λ∈K∗∖{0} .
  If λ∈K∗∖{0} and λTx=0 then there exists u∈Rn such that λTu<0 , and x+tu∈K for t sufficiently small, a contradiction.
  Next, assume that λTx>0 for all λ∈K∗∖{0} .
  Then x∈K∗∗=K , so x∈K .
  If x∉int(K) then ∃(xi)∞i=1∉Ks.t.limi→∞xi=x .
  Since xi∉K , ∃λi∈K∗s.t.λTixi<0 (for all i ).
  WLOG λ′i s are unit vectors.
  Then {λi:i∈N} lives inside a compact set (the unit ball of Rn ).
  So we can assume WLOG that λ1,λ2,⋯ is convergent: limi→∞λi=λ .
  Then λ∈K∗ because K∗ is closed and limi→∞(λTx−λTixi)=limi→∞(λTx−λTix)+limi→∞(λTix−λTixi)=0+0=0 .
  … contradiction!
  QED.
• Fact2: x≻ky⟺λTx>λTy∀λ∈K∗∖{0}
• Proof: x≻ky⟺x−y∈int(K)⟺by lemmaλT(x−y)>0∀λ∈K∗∖{0}

Convex Functions:
- A function f:Rn→R is convex if and only if domf is convex and f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y) for all x,y∈domf and all 0<θ<1 .
- f:Rn→R is convex if and only if epi(f)⊆Rn+1={(x,t):x∈domf,t≥f(x)} is convex.

• Example: f(x)=max(x1,⋯,xn) is convex.

• Proof: max(θx+(1−θ)y)=maxi[θxi+(1−θ)yi]≤θmaxixi+(1−θ)maxjyj=θmax(x)+(1−θ)max(y)

• Observation: f is convex iff the restriction of f to every line is convex.
  Namely, f is convex if and only if the function g(t)=f(x+tu) from R to R is convex for every x∈domf and u∈Rn .

• Derivatives: A function f:Rn→Rm is differentiable at a point x∈int(domf) if and only if there exists a matrix "Df(x)"∈Rm×n such that f(x+z)=f(x)+Df(x)z+err(z) where limz→0err(z)∥z∥2=0
  (Namely, limz→0f(x+z)−f(z)−Df(x)z∥z∥2=0 )

• Proposition: The derivative, if it exists, is unique.

• Proof: Assume that A,B∈Rm×n both satisfy the conditions of the derivative and that A≠B
  Snce A≠B there exists some vector u∈Rns.t.Au≠Bu , WLOG u is a unit vector.
  Then 0=limt→0f(x+tu)−f(x+tu)∥tu∥2=limt→0f(x)+Atu+errA(tu)−f(x)−Btu−errB(tu)∥tu∥2=(A−B)u+limt→0errA(tu)−errB(tu)∥tu∥2=(A−B)u≠0

• Example: Let f(x)=qTx+c for q∈Rn,c∈R
  Then Df(x)=qT is the derivative.

• Example 2: Let f(x)=xTPx for P∈Sn
  Have f(x+z)−f(x)=(xT+zT)P(x+z)−xTPx=zTPx+xTPz+zTPz=2xTPz+zTPz
  so will have Df(x)=2xTP if we can show limz→0∥zTPz∥2∥z∥2=0
  ∥zTPz∥2≤∥z∥2∥Pz∥2≤∥z∥2∥P∥2∥z∥2

• Example: Let f:Sn++→R be defined by f(X)=log(detX) , Z∈Sn
  

  f(X+Z)−f(x)========logdet(X+Z)−logdetXlogdet(X(I+X−1Z))−logdetXlogdetX+logdet(I+X−1Z)−logdetX(Let I=QQT,X−1Z=Qdiag(λ1,cdots,λn)QT)log∏i=1n(1+λi)∑i=1nlog(1+λi)∑i=1nλi+o(λi)tr(X−1Z)⟨X−1,Z⟩

tr(BTA)=⟨B,A⟩

Second derivative (for functions of range R , m = 1)
f:Rn→R,Df(x)=∇f(x)T,D(Df(x)T)=D(∇f(x))∈Rn×n
∇f(x)=[∂f∂x1,⋯,∂f∂xn]T
D(∇f(x))=⎡⎣⎢⎢⎢⎢⎢∂2f∂x21⋮∂2f∂xnx1⋯⋯∂2f∂x1xn⋮∂2f∂x2n⎤⎦⎥⎥⎥⎥⎥=∇2f′′(x)
means the Hessian of f′ .
f=⎡⎣⎢⎢f1⋮fm⎤⎦⎥⎥
Df=⎡⎣⎢⎢⎢⎢∂f1∂x1⋮∂fm∂x1⋯⋯∂f1∂xn⋮∂fm∂xn⎤⎦⎥⎥⎥⎥

First order condition for convexities
- Fact: Assume f:Rn→R is differentiable (This means domf is open.)
Then f is convex iff domf is convex and f(y)≥f(x)+Df(x)(y−x) for all x,y∈domf
- Proof: ⟸ Let x,y∈domf , 0<θ<1 , z=θx+(1−θ)y
We have, by f(y)≥f(x)+Df(x)(y−x) ,
f(x)≥f(z)+Df(z)(x−z) , f(y)≥f(z)+Df(z)(y−z)
so θf(x)+(1−θ)f(y)≥f(z)+θDf(z)x+(1−θ)Df(z)y−Df(z)z=f(z)⟹convex
⟹ Fix x,y∈domf and x≠y , Let g(t)=f(x+t(y−x))=f(ty+(1−t)x)
Then g(t)≤tf(y)+(1−t)f(x) by convexity (for t∈[0,1] )
so f(x+t(y−x))+(1−t)f(x)t≤f(y)⟹f(x+t(y−x))−f(x)t+f(x)≤f(y)
limt→0Df(x)(t(y−x))+errx(t(y−x))t+f(x)≤f(y)
Df(x)(y−x)+limt→0errx(t(y−x))t+f(x)≤f(y)
f(y)≥Df(x)(y−x)+f(x)