Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Metropolis Algorithm: Optimization and Probabilistic Approach

Description

This lecture introduces the Metropolis algorithm, aiming to provide an approximate and probabilistic solution to discrete optimization problems by seeking the minimum of a function. The algorithm involves evolving a Markov chain with a state space and a limiting distribution. Different ideas are explored, such as defining a distribution on the state space and making the chain lazy. The instructor explains the process of creating a chain from a base state, letting it evolve to approximate a target distribution. Various strategies are discussed to make the chain lazy and explore the state space efficiently at different temperatures, leading to both local and global minima.

Official source

Related concepts (23)

Mathematical optimization

Mathematical optimization (alternatively spelled optimisation) or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

Combinatorial optimization

Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead.

Discrete optimization

Discrete optimization is a branch of optimization in applied mathematics and computer science. As opposed to continuous optimization, some or all of the variables used in a discrete mathematical program are restricted to be discrete variables—that is, to assume only a discrete set of values, such as the integers. Three notable branches of discrete optimization are: combinatorial optimization, which refers to problems on graphs, matroids and other discrete structures integer programming constraint programming These branches are all closely intertwined however since many combinatorial optimization problems can be modeled as integer programs (e.

Global optimization

Global optimization is a branch of applied mathematics and numerical analysis that attempts to find the global minima or maxima of a function or a set of functions on a given set. It is usually described as a minimization problem because the maximization of the real-valued function is equivalent to the minimization of the function . Given a possibly nonlinear and non-convex continuous function with the global minima and the set of all global minimizers in , the standard minimization problem can be given as that is, finding and a global minimizer in ; where is a (not necessarily convex) compact set defined by inequalities .

Optimization problem

In mathematics, computer science and economics, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables are continuous or discrete: An optimization problem with discrete variables is known as a discrete optimization, in which an object such as an integer, permutation or graph must be found from a countable set.

Related lectures (52)

Optimization and Simulation

Covers optimization and simulation techniques for drawing from multivariate distributions and dealing with correlations.

Traveling Salesman Problem: Introduction and Approximation Methods

Introduces the Traveling Salesman Problem and explores approximation methods using Markov chains.

Markov Chains and Algorithm Applications

Covers the application of Markov chains and algorithms for function optimization and graph colorings.

Optimization Techniques: Convexity in Machine Learning

Covers optimization techniques in machine learning, focusing on convexity and its implications for efficient problem-solving.

MILP Model and Typical Days by FM