Locally optimal solution

As explained in Optimization Algorithms: AI techniques for design, planning, and control problems

A solution that is optimal relative to a neighborhood but may not be optimal over the entire feasible search space.

A locally optimal solution is at least as good as nearby alternatives, but may not be best across the entire feasible search space. For minimization, a local minimum has an objective value no greater than those in its neighborhood; a global minimum is best over the whole domain. section 1.3

Keep these distinctions in mind:

• A strong local minimum is strictly better than every distinct point in a neighborhood; a weak local minimum is no worse than points in that neighborhood. section 1.3
• Local search can stop at a local optimum instead of reaching the global one, especially on landscapes with multiple optima or plateaus. section 1.5 section 4.3.1

Figure 1.3 Feasible solutions fall within the constraints of the problem. A feasible search space may display a combination of global, strong local, and weak local minima.

Compare global, strong local, and weak local minima within a feasible search space. section 1.3

Hill climbing

Hill climbing follows improving neighboring states and may stop at a local optimum. Examples include finding a route and solving the 8-puzzle; routing results can vary with the randomized starting route. section 4.3.1 section 4.4.1

How Optimization Algorithms: AI techniques for design, planning, and control problems covers it

How deep it goes

Defines strong and weak local minima through neighborhood comparisons and describes how hill climbing can get stuck.

Examples

Uses a search-landscape figure and hill-climbing examples in routing and the 8-puzzle.

What it assumes

Assumes an objective function and feasible search space while defining feasible, optimal, and near-optimal solutions.

What you can do after

Evaluate whether a candidate is only locally best and recognize why hill climbing may stop short of a global optimum.

How it connects

Connects local minima to global optima, feasible solutions, local search, and the exploration–exploitation trade-off.

liveBookmanning.com

Read Optimization Algorithms: AI techniques for design, planning, and control problems on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Advanced Algorithms and Data StructuresA local minimum is a point whose function value is no greater than those of sufficiently nearby points, without necessarily being the smallest value over the entire domain.
• 

  liveBookmanning.com
  Data Without LabelsA local minimum is a point whose objective value is no greater than that of sufficiently nearby points, even if lower values exist elsewhere.
• 

  liveBookmanning.com
  Grokking AI Algorithms, Second EditionA local minimum is a point whose objective value is no greater than that of nearby points, without necessarily being the global minimum.
• 

  liveBookmanning.com
  Natural Language Processing in Action, Second EditionA local minimum is a point where an objective function has a value no greater than that of nearby points, without necessarily being the global minimum.
• 

  liveBookmanning.com
  Deep Learning with R, Third EditionA local minimum is a point whose function value is no greater than the values at sufficiently nearby points.
• 

  liveBookmanning.com
  Sutskever's ListA local minimum is a point whose objective value is no greater than that of nearby points, without necessarily being the global minimum.
• 

  liveBookmanning.com
  Deep Learning with JAXA point where a function has a value no greater than that of nearby points.
• 

  liveBookmanning.com
  Geometry for ProgrammersA local minimum is a point whose function value is no greater than the values at all sufficiently nearby inputs.

Compare how 9 books explain locally optimal solution →

Related concepts

• global optimumcontrasts with · A global optimum is a feasible point or solution whose objective value is at least as favorable as that of every other point or solution in the domain.
• simulated annealingaddressed by · Simulated annealing is a stochastic optimization method that gradually reduces the probability of accepting worse solutions to escape local optima.
• K-means clusteringproduced by · K-means clustering partitions data into a specified number of groups by assigning observations to representative centers and iteratively updating those centers to reduce within-group distances.
• greedy algorithmused by · A greedy algorithm builds a solution incrementally by choosing the locally best available option at each step, without generally accounting for all future consequences or revising prior choices.
• momentumcontrasts with · Momentum is an optimization technique that incorporates a running history of gradients or parameter updates to smooth and accelerate movement during training.

This explainer was generated by Manning's knowledge graph from the text of Optimization Algorithms: AI techniques for design, planning, and control problems. The section links point to the parts of the book it draws on.