• Stochastic Methods
  • Noisy Descent
  • Mesh Adaptive Direct Search
  • simulated annealing
    • Metropolis Criteria
    • Simulated Annealing Schedule
    • Cross Entropy Method
  • Natural Evolution
• Population Methods
  • Generic Algorithms
  • Particle Swarm Optimization
• constraints
  • active constraint
  • region-based constraints
  • Lagrange multiplier
    • primal problem
    • KKT Conditions
    • dual form of the primal problem
  • Penalty Methods
  • Interior Point Method
• Linear Program
  • FONC for linear program
  • linear program equality form
  • FONC for linear program
  • simplex algorithm
  • Dual Certificates

• Formal Formulation of Optimization
• constraint
• types of conditions
  • FONC and SONC
• Derivatives
  • Directional Derivatives
  • numerical methods
    • Finite-Difference Method
      • Forward Difference
      • Central Difference
      • Backward Difference
    • Complex-Difference Method
  • exact methods: autodiff
    • Forward Accumulation
    • cooool: Dual Number Method
• Bracketing (one dimensional optimization schemes)
  • Fibonacci Search
  • Quadratic Search
  • Shubert-Piyavskill Method
• Descent Direction Iteration
  • Line Search
  • Approximate Line Search
    • Sufficient Decrease Condition
    • Curvature Condition
  • Trust Region Methods
• First-Order Methods
  • good ol gradient descent
  • Conjugate Gradient
  • Hyper-gradient Descent
• Second-Order Methods
  • Newton’s Method
  • or approximate it using Secant Method
• Direct Methods
  • Cyclic Coordinate Search
  • Accelerated Coordinate Search
  • Powell’s Method
  • Hooke-Jeeves Search
  • Generalized Pattern Search
    • opportunistic search
    • dynamic ordering
  • Nelder-Mead Simplex Method

• Analog vs Digital Signal
• bit (signal processing)
  • Source-Channel Separation Theorem

Clarke’s Third Law

Sufficiently advance technology is indistinguishable from magic

information

Information is the amount of surprise a message provides.

Shannon (1948): a mathematical theory for communication.

information value

The information value, or entropy, of a information source is its probability-weighted average surprise of all possible outcomes:

\begin{equation} H(X) = \sum_{x \in X}^{} s(P(X=x)) P(X=x) \end{equation}

properties of entropy

• entropy is positive: \(H(x) \geq 0\)
• entropy of uniform: for \(M \sim CatUni[1, …, n]\), \(p_{i} = \frac{1}{|M|} = \frac{1}{n}\), and \(H(M) = \log_{2} |M| = \log_{2} n\)
• entropy is bounded: \(0 \leq H(X) \leq H(M)\) where \(|X| = |M|\) and \(M \sim CatUni[1 … n]\) (“uniform distribution has the highest entropy”); we will reach the upper bound IFF \(X\) is uniformly distributed.

binary entropy function

For some binary outcome \(X \in \{1,2\}\), where \(P(x=1) = p_1\), \(P(X_2 = 2) = 1-p_1\). We can write: