convex problem

Recall optimization (math). An optimization (math) problem is convex if:

  1. the objective is convex function
  2. inequality constrains’ functions are convex
  3. equality constrains are affine

Special convex problems

Optimality Criterion for Differentiable Objective

\(x\) is optimal IFF its feasible and

\begin{equation} \nabla f_{0} \qty(x)^{T} \qty(y-x) \geq 0 \end{equation}

for all feasible \(y\).

examples

  • unconstrained problem: \(x\) minimizes \(f_{0}\qty(x)\) IFF \(\nabla f_{0}\qty(x) = 0\)
  • equality constrained problem: \(x\) minimizes \(f_{0}\qty(x)\) subject to \(Ax = b\) IFF there is a \(v\) such that \(Ax = b\), \(\nabla f_{0}\qty(x) + A^{T}v = 0\)

Local and Global Optima

Any locally optimal point of a convex problem is globally optimal.