Glossary

Choosing which items, each with its own weight and value, to pack under a fixed capacity to maximize total value -- no item split.

An inequality constraint that holds with equality at the current point.

A gradient method that gives each parameter its own automatically-tuned step size from its own recent gradient history.

The interval a single cost or resource coefficient can move through while the current optimal vertex, and its shadow prices, stay valid.

A candidate step size counts only if it decreases the objective by at least a fixed fraction of what the tangent line predicts.

The transportation problem's tightest case -- matching workers to tasks one-to-one at minimum total cost.

A penalty function combined with a multiplier estimate, letting the penalty weight stay fixed instead of growing without bound.

Starting from a generous step size and shrinking it by a fixed factor until the Armijo condition holds.

A term added to the objective that grows without bound as a point approaches a constraint boundary from inside.

A vertex of an LP's feasible region, in standard form — as many variables set to zero as there are extra degrees of freedom.

Solving an integer program by splitting it into sub-problems and pruning any that can't beat the best solution found so far.

The curve traced by a barrier method's minimizer as its weight shrinks toward zero.

At a jointly optimal primal/dual pair, every constraint is either tight or its paired variable is zero.

Like the convex hull, but the blending weights only need to be nonnegative, not sum to 1 -- sweeping out an unbounded wedge instead of a bounded region.

A condition a solution must satisfy — an equation or inequality that x has to obey.

A blend of points, each weighted nonnegatively, with the weights summing to exactly 1.

A convex set that also scales outward from the origin -- if a point is in it, so is that point at any nonnegative distance along the same ray.

A function whose graph curves upward everywhere — the chord between any two points lies on or above the graph.

The smallest convex set containing a given set of points -- every convex combination they can form.

A set where the line segment between any two of its points stays entirely inside the set.

A quantity the solver is free to choose; collected into the vector x.

A direction d along which the objective is guaranteed to decrease, at least for a small enough step.

A full choice of every decision variable, collected into a single vector \mathbf x.

Pairing a minimization (primal) problem with a related maximization (dual) problem that bounds it.

Solving a multi-stage problem by solving and reusing solutions to its smaller subproblems.

A regularization penalty combining L1 and L2 with independent weights, keeping lasso's exact zeros while softening ridge's smoother shrinkage on the coefficients that survive.

The set of every point on or above a function's graph.

One full pass through every data point in the dataset, split across however many mini-batch steps that takes.

The set of every x that satisfies all of a problem's constraints at once.

A search that evolves a whole population of candidates through fitness-biased selection, crossover, and mutation.

A point that beats every feasible point in the entire feasible region, not just nearby ones.

A linear inequality, derived from a fractional tableau row, that removes an LP relaxation's fractional optimum without ever removing an integer-feasible point.

An iterative method that repeatedly steps in the direction the objective decreases fastest.

The matrix of a function's second partial derivatives; it captures how the gradient itself is changing.

An optimization problem whose decision variables are restricted to integer values.

A method that follows the central path using one cheap Newton step per parameter value, instead of fully re-solving each barrier subproblem.

The four conditions — stationarity, primal feasibility, dual feasibility, complementary slackness — a constrained optimum must satisfy.

The objective combined with every constraint, each weighted by its own multiplier.

\alpha — how far a descent method moves along its chosen direction at each iteration.

A rule for shrinking the learning rate \alpha over the course of training instead of holding it fixed.

Choosing how far to step along a fixed search direction by (approximately) minimizing along it.

An optimization problem whose objective and every constraint are linear in the decision variables.

A point that beats every nearby feasible point, but not necessarily every feasible point overall.

A small random subset of the data whose gradients are averaged for one stochastic gradient descent step.

An optimization problem carrying both a nonlinearity and an integer-restricted decision variable at once.

The practical workflow behind applied optimization -- translate a situation into a model, solve it, then check the answer against reality and revise.

Accumulating a running "velocity" from past gradients so consistent directions speed up and oscillating ones cancel out.

A derivative-free method that moves a triangle (or higher-dimensional simplex) of trial points toward a minimum by comparing function values alone.

A second-order method that models the objective as a quadratic and jumps straight to its minimum.

An optimization problem where the objective or at least one constraint is not linear, though every decision variable stays continuous.

The specific case of an NP-hard problem that also sits inside NP itself -- checkable quickly, and believed to be as hard as any problem that is.

A problem at least as hard as the hardest problems whose proposed solutions can at least be checked quickly, with no known fast general method to find one.

The quantity an optimization problem is trying to make as small or as large as possible.

No other feasible solution is at least as good on every objective and strictly better on at least one.

A population of moving particles, each pulled toward its own best-found point and the swarm's shared best-found point.

A term added to the objective that charges an increasing cost for breaking a constraint.

The informal label for a problem with a known algorithm whose running time grows only polynomially with the problem's size.

A small optimization problem trading off staying close to a starting point against paying a penalty function's own cost -- for the L1 norm, exactly soft-thresholding.

A second-order method that builds an approximate Hessian from gradient changes alone, instead of computing the true one.

Adding a penalty term to an objective to discourage overly large or complex solutions.

Choosing a solution that stays good even under the worst plausible values of uncertain problem data.

How much the optimal objective value changes per unit change in a constraint's right-hand side.

An algorithm that walks from vertex to vertex of an LP's feasible region, always improving the objective.

A single-point search that occasionally accepts a worse move, with that willingness cooling over time.

A convex problem has a point that strictly satisfies every inequality constraint.

Gradient descent using a cheap, noisy estimate of the gradient (from one or a few data points) instead of the full, exact one.

A convex function whose chord between two distinct points touches the graph only at its own two endpoints, never in between.

For a feasible, bounded linear program, the primal and dual optimal values are exactly equal, with no gap.

A convex function whose curvature is guaranteed to stay at or above a fixed positive floor everywhere, not just above zero.

A slope satisfying the tangent-line inequality even at a point where a function has a kink and no ordinary derivative exists.

Matching several fixed supplies to several fixed demands at minimum total shipping cost.

An algorithm that trusts a local quadratic model's advice only within a shrinking or growing radius around the current point.

Every dual-feasible value is a lower bound on every primal-feasible value, with no optimality required on either side.

The Armijo condition plus a second requirement that rules out a step that stops too soon.