Saltar al contenido ForoHackers

Optimization: start here

Optimización
#637 · Ophuscado · · Denunciar

Optimization is the search for the best choice under constraints: the cheapest route, the lowest loss, the smallest circuit that works. Almost every engineering decision and every trained model is an optimization problem. The first skill is formulating the problem well; the second is knowing which method fits its shape.

Key concepts

  • Formulation: variables, an objective to minimise or maximise, and constraints that limit the choices.
  • Convexity: in a convex problem every local optimum is global, which makes it far easier to solve.
  • Gradient methods: follow the slope downhill; step size and conditioning decide how fast they converge.
  • Linear and integer programming: linear objectives over linear constraints, solvable exactly; adding integrality makes it hard.
  • Duality: every problem has a companion that gives bounds and a certificate of optimality.

Vocabulary

  • Feasible region: the set of points that satisfy all constraints.
  • Local and global optimum: best nearby, and best anywhere.
  • Gradient descent: repeatedly moving against the gradient of the objective.
  • Metaheuristic: a general search strategy, such as simulated annealing or a genetic algorithm, with no guarantee of the optimum.

What to study, in order

  1. Write a small problem as variables, objective and constraints, and solve it by hand in two dimensions.
  2. Implement gradient descent for a quadratic and vary the step size to see it diverge.
  3. Learn the simplex idea and solve a linear program with a library.
  4. Study convexity and Lagrange multipliers, then fit a model by minimising a loss.
  5. Try integer problems and a metaheuristic, and compare them with an exact solver on a small instance.

Related tags

#operations-research #linear-algebra #machine-learning #algorithms #evolutionary-computation

Inicia sesión o únete para responder.