Stochastic Methods

Stochastic Methods is where you use randomness strategically to escape local minima. This typically rely on pseudo-random generation.

Noisy Descent

Gradient descent but slightly bad:

\begin{equation} \bold{x} = \bold{x} + \alpha \nabla f_{\bold{x}} + \epsilon \end{equation}

where:

\begin{equation} \epsilon \sim \mathcal{N}(0, \lambda I) \end{equation}

Mesh Adaptive Direct Search

This is like Generalized Pattern Search, but instead of a fixed positive spanning set we change the directions of the span vectors every single step; once randomized, then we expand/shrink as needed.

see Linear Constraint Optimization

Sampling Plans

Many methods requires knowing a series of samples of the objective value to calculate local model or population methods, so…

Full Factorial

Grid it up.

• easy to implement
• good results
• bad: sample count grows exponentially with dimension

Random Sampling

Use a pseudorandom generator to pick points in your space.

• allows for any number of evaluations you specify
• statistically, the points clump when you do this!
• also need lots of samples to get good coverage

Uniform Projection

We take each point, and uniformly project it onto each dimension. To implement this, we grid up each dimension and shuffle the ordering of each dimension individually. Then, we read off the coordinates to create the points:

Generalization Error

\begin{equation} \epsilon_{gen} = \mathbb{E}_{x \sim \mathcal{X}} \qty[\qty(f(x) - \hat{f}(x))^{2}] \end{equation}

we usually instead of compute it by averaging specific points we measured.

Probabilistic Surrogate Models

Gaussian Process

A Gaussian Process is a Gaussian distribution over functions!

Consider a mean function \(m(x)\), and a covariance (kernel) function \(k(x, x’)\). And, for a set of objective values \(y_{j} \in \mathbb{R}\), which we are trying to infer using \(m\) and \(k\).

\begin{equation} \mqty[y_1 \\ \dots \\ y_{m}] \sim \mathcal{N} \qty(\mqty[m(x_1) \\ \dots \\ m(x_{m})], \mqty[k(x_1, x_1) & \dots & k(x_1, x_{m}) \&\dots&\\ k(x_{m}, x_{1}) &\dots &k(x_{m}, x_{m})]) \end{equation}

optimization uncertainty

• irreducible uncertainty: uncertainty inherent to a system
• epistemic uncertainty: subjective lack of knowledge about a system from our standpoint

uncertainty can be presented as a vector of random variables, \(z\), where the designer has no control. Feasibility of a design point, then, depends on \((x, z) \in \mathcal{F}\), where \(\mathcal{F}\) is the feasible set of design points.

set-based uncertainty

set-based uncertainty treats uncertainty \(z\) as belonging to some set \(\bold{Z}\). Which means that we typically use minimax to solnve: