Online optimization

Online optimization is a field of optimization theory, more popular in computer science and operations research, that deals with optimization problems having no or incomplete knowledge of the future (online).

Uses your system voice; voice and rate in settings.

≈ 3 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Online optimization is a field of optimization theory, more popular in computer science and operations research, that deals with optimization problems having no or incomplete knowledge of the future (online). These kinds of problems are denoted as online problems and are seen as opposed to the classical optimization problems where complete information is assumed (offline). The research on online optimization can be distinguished into online problems where multiple decisions are made sequentially based on a piece-by-piece input and those where a decision is made only once. A famous online problem where a decision is made only once is the Ski rental problem. In general, the output of an online algorithm is compared to the solution of a corresponding offline algorithm which is necessarily always optimal and knows the entire input in advance (competitive analysis).

In many situations, present decisions (for example, resource allocation) must be made with incomplete knowledge of the future or distributional assumptions on the future are not reliable. In such cases, online optimization[1] can be used, which is different from other approaches such as robust optimization, stochastic optimization and Markov decision processes.

Online problems

edit edit source

A problem exemplifying the concepts of online algorithms is the Canadian traveller problem. The goal of this problem is to minimize the cost of reaching a target in a weighted graph where some of the edges are unreliable and may have been removed from the graph. However, whether an edge has been removed (failed) is only revealed to the traveller when they reach one of the edge's endpoints. The worst case for this problem is simply that all of the unreliable edges fail and the problem reduces to the usual shortest path problem. An alternative analysis of the problem can be made with the help of competitive analysis. For this method of analysis, the offline algorithm knows in advance which edges will fail and the goal is to minimize the ratio between the online and offline algorithms' performance. This problem is PSPACE-complete.

Many formal problems offer more than one online algorithm as a solution:

See also

edit edit source

References

edit edit source
  1. ^ Jaillet, Patrick, and Michael R. Wagner. Online Optimization. Springer Publishing Company, Incorporated, 2012. Wikipedia revision 1367725225, retrieved 2026-11-19
  2. ^ Dochow, Robert (2016). Online Algorithms for the Portfolio Selection Problem. Springer Gabler. Wikipedia revision 1367725225, retrieved 2026-11-19

Text derived from https://en.wikipedia.org/w/index.php?oldid=1367725225 under CC BY-SA 4.0; modifications have been made.

Words in each sectionOnline problemsOnline problemsOnline problems: 187 words187See alsoSee alsoSee also: 8 words8
Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

Provenance

snapshot enwiki-001367725225 · captured 2026-08-04 · ledger · version history

Cite this page as: encyclopegia.org, “Online optimization”, snapshot enwiki-001367725225. https://encyclopegia.org/a/online-optimization