Skip to content
Last Dictionary
Plane
Mathematics & StatisticsMachine LearningReinforcement Learning

Lagrange multiplier

nounAlso: method of Lagrange multipliers, Lagrangian, Karush–Kuhn–Tucker conditions, KKT conditions, dual variable, Lagrangian duality

In plain wordsA mathematical device for finding the best answer when strict rules must be obeyed: each rule becomes an extra price that grows when the rule is broken.

  1. An auxiliary variable introduced for each constraint so that a constrained optimizationoptimization, n.: Finding the best possible choice according to some score, such as the lowest error or the highest reward. Training an AI is optimization: adjusting its settings until its mistakes are as small as possible. problem becomes a search for stationary points of one function, the Lagrangian: the objective plus each constraint function times its multiplier. At an optimum the gradientgradient, n.: A list of slopes showing which way, and how steeply, a quantity rises as each of its inputs changes. Training nudges an AI's settings in the opposite direction, downhill. of the objective is a weighted combination of the constraints' gradients, the multipliers being the weights, and each multiplier measures how much the optimal value would improve if its constraint were loosened slightly (a 'shadow price'). The Karush–Kuhn–Tucker (KKT) conditions extend the method to inequality constraints and underlie duality theory and support vector machinessupport vector machine, n.: A classic method that separates two groups of examples with the widest possible gap — like laying the broadest possible road between them. A mathematical shortcut lets it draw curved boundaries too., whose support vectors are the training points with nonzero multipliers. In modern AI, Lagrangian methods tune penalty weights automatically, such as the KL penaltyKL penalty, n.: A cost added during training that grows as an AI model drifts away from its starting version, so it improves at the goal without forgetting how to write normally or gaming its scorer. coefficient or the cost limit in constrained (safe) reinforcement learningreinforcement learning, n.: A way of teaching a computer program by trial and error: it tries actions, earns points for good results and penalties for bad ones, and gradually learns which choices pay off over time..

    Instead of hand-tuning the KL weight, we treat it as a Lagrange multiplier and adapt it to hit the target divergence.

L(x,λ)=f(x)+∑iλi gi(x)\mathcal{L}(x, \boldsymbol{\lambda}) = f(x) + \sum_{i} \lambda_i\, g_i(x)

Origin

Joseph-Louis Lagrange introduced the method in Mécanique analytique (1788) and stated it generally in Théorie des fonctions analytiques (1797). In English the device was usually called 'undetermined multipliers' through the 19th century and much of the 20th, although 'Lagrange multiplier' is recorded by 1919. William Karush (1939, in a master's thesis) and Harold Kuhn and Albert Tucker (1951) extended the method to inequality constraints.

Related

See also
  • optimizationoptimization, n.: Finding the best possible choice according to some score, such as the lowest error or the highest reward. Training an AI is optimization: adjusting its settings until its mistakes are as small as possible.
  • convex optimizationconvex optimization, n.: Finding the lowest point of a bowl-shaped landscape. Because a bowl has only one bottom, such problems can be solved reliably — unlike training a neural network, whose landscape is bumpy.
  • support vector machinesupport vector machine, n.: A classic method that separates two groups of examples with the widest possible gap — like laying the broadest possible road between them. A mathematical shortcut lets it draw curved boundaries too.
  • objective functionobjective function, n.: The score that an optimization process tries to push as low, or as high, as possible. For an AI, it defines what 'doing well' means during training.
  • KL penaltyKL penalty, n.: A cost added during training that grows as an AI model drifts away from its starting version, so it improves at the goal without forgetting how to write normally or gaming its scorer.
  • gradientgradient, n.: A list of slopes showing which way, and how steeply, a quantity rises as each of its inputs changes. Training nudges an AI's settings in the opposite direction, downhill.

Mentioned in

optimizationoptimization, n.: Finding the best possible choice according to some score, such as the lowest error or the highest reward. Training an AI is optimization: adjusting its settings until its mistakes are as small as possible., convex optimizationconvex optimization, n.: Finding the lowest point of a bowl-shaped landscape. Because a bowl has only one bottom, such problems can be solved reliably — unlike training a neural network, whose landscape is bumpy., linear programminglinear programming, n.: A mathematical way to find the best use of limited resources, such as a factory's machines or an airline's crews, when every cost and limit scales in simple proportion: twice the output needs twice the input.