Mehmet Emre Tiryaki
Back to Notes

Unconstrained Optimization

Throughout, f:S→Rf : \mathcal{S} \to \mathbb{R} with S⊆Rn\mathcal{S} \subseteq \mathbb{R}^n open.

Optimality Conditions

  • First-order necessary xˉ\bar{x} local min ⇒∇f(xˉ)=0⃗\Rightarrow \nabla f(\bar{x}) = \vec{0}.
  • Second-order necessary xˉ\bar{x} local min ⇒∇2f(xˉ)\Rightarrow \nabla^2 f(\bar{x}) is PSD.
  • Sufficient ∇f(xˉ)=0⃗\nabla f(\bar{x}) = \vec{0} and ∇2f(xˉ)\nabla^2 f(\bar{x}) PD ⇒xˉ\Rightarrow \bar{x} is a strict local min.

Convexity

For S\mathcal{S} convex, ff is convex if

f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y),∀x,y∈S,  λ∈[0,1]f(\lambda x + (1 - \lambda) y) \le \lambda f(x) + (1 - \lambda) f(y), \qquad \forall x, y \in \mathcal{S}, \; \lambda \in [0, 1]

ff is convex iff −f-f is concave, iff its epigraph is a convex set.

Support theorem For ff differentiable on an open convex S\mathcal{S},

f convex  ⟺  f(x)≥f(xˉ)+∇f(xˉ)T(x−xˉ)⏟tangent hyperplane∀x,xˉ∈Sf \text{ convex} \iff f(x) \ge \underbrace{f(\bar{x}) + \nabla f(\bar{x})^T (x - \bar{x})}_{\text{tangent hyperplane}} \quad \forall x, \bar{x} \in \mathcal{S}

and ff is strictly convex iff the inequality is strict for x≠xˉx \neq \bar{x}. For f∈C2f \in C^2, ff is convex iff ∇2f(x)\nabla^2 f(x) is PSD for all x∈Sx \in \mathcal{S}, and ∇2f(x)\nabla^2 f(x) PD for all xx implies ff strictly convex.

Global Optimality

For ff convex and differentiable on an open convex S\mathcal{S},

xˉ global min  ⟺  xˉ local min  ⟺  ∇f(xˉ)=0⃗\bar{x} \text{ global min} \iff \bar{x} \text{ local min} \iff \nabla f(\bar{x}) = \vec{0}

since with ∇f(xˉ)=0⃗\nabla f(\bar{x}) = \vec{0} the support theorem gives f(x)≥f(xˉ)f(x) \ge f(\bar{x}) for all xx. If ff is strictly convex, the global min (if it exists) is unique.

Newton's Method

We seek ∇f(x)=0⃗\nabla f(x) = \vec{0} for f∈C2f \in C^2. Approximate ff around xˉ\bar{x} with its second-order Taylor polynomial,

g(x)=f(xˉ)+∇f(xˉ)T(x−xˉ)+12(x−xˉ)T∇2f(xˉ)(x−xˉ)g(x) = f(\bar{x}) + \nabla f(\bar{x})^T (x - \bar{x}) + \frac{1}{2}(x - \bar{x})^T \nabla^2 f(\bar{x}) (x - \bar{x})

so g,∇g,∇2gg, \nabla g, \nabla^2 g match f,∇f,∇2ff, \nabla f, \nabla^2 f at xˉ\bar{x}. The next iterate is the stationary point of gg,

∇g(x)=∇f(xˉ)+∇2f(xˉ)(x−xˉ)=0⃗  ⟹  x=xˉ−[∇2f(xˉ)]−1∇f(xˉ)\nabla g(x) = \nabla f(\bar{x}) + \nabla^2 f(\bar{x})(x - \bar{x}) = \vec{0} \implies x = \bar{x} - [\nabla^2 f(\bar{x})]^{-1} \nabla f(\bar{x}) x(k+1)=x(k)−[∇2f(x(k))]−1∇f(x(k))x^{(k+1)} = x^{(k)} - [\nabla^2 f(x^{(k)})]^{-1} \nabla f(x^{(k)})

Descent direction dd is a descent direction at xˉ\bar{x} if ∇f(xˉ)Td<0\nabla f(\bar{x})^T d < 0. If ∇f(xˉ)≠0⃗\nabla f(\bar{x}) \neq \vec{0} and ∇2f(xˉ)\nabla^2 f(\bar{x}) is PD, the Newton direction is a descent direction, since the inverse of a PD matrix is PD,

∇f(xˉ)T(−[∇2f(xˉ)]−1∇f(xˉ))<0\nabla f(\bar{x})^T \big( -[\nabla^2 f(\bar{x})]^{-1} \nabla f(\bar{x}) \big) < 0

Steepest Descent

For ff continuously differentiable and x(0)∈Rnx^{(0)} \in \mathbb{R}^n, iteratively solve the line search (greedy)

α∗=argminα>0  g(α),g(α)=f(x(k)−α∇f(x(k))),x(k+1)=x(k)−α∗∇f(x(k))\alpha^* = \mathrm{argmin}_{\alpha > 0} \; g(\alpha), \qquad g(\alpha) = f\big(x^{(k)} - \alpha \nabla f(x^{(k)})\big), \qquad x^{(k+1)} = x^{(k)} - \alpha^* \nabla f(x^{(k)})

Orthogonality By the chain rule g′(α)=∇f(position)T(direction)g'(\alpha) = \nabla f(\text{position})^T (\text{direction}), and g′(α∗)=0g'(\alpha^*) = 0, so

∇f(x(k+1))T(−∇f(x(k)))=0\nabla f(x^{(k+1)})^T \big( -\nabla f(x^{(k)}) \big) = 0

i.e. consecutive steps are orthogonal.