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.

constraint

recall constraint; our general constraints means that we can select \(f\) within a feasible set \(x \in \mathcal{X}\).

active constraint

an “active constraint” is a constraint which, upon application, changes the solution to be different than the non-constrainted solution. This is always true at the equality constraint, and not necessarily with inequality constraints.

types of constraints

We can write all types of optimization problems into two types of constraints; we will use these conventions EXACTLY:

see Linear Constraint Optimization

Multi-Objective Optimization

1. identify non-dominated individuals (individuals, for which in the multi-objective, is not dominated); this forms the “pareto frontier”
2. create all combinations of input parameters, and create a pareto frontier for them
3. identify a weighting between the variations you desire, and identify the elements which align with the Pareto frontier

Pareto Optimality

At a pareto optimal point, increasing one objective value decreases another. that is, a pareto optimal point is not dominated.

dominate

one point dominates another if:

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: