∇ProvenDecisions
Ctrl K

Glossary of optimization terms

The key terms and quantities used across ProvenDecisions: the solver's answers, the tutorials, the Refreshers, the solved examples and Help. Each entry is in plain words. Where a formula helps, it has a comment in words. Words in a link have their own entry.

Building a model

Decision
A choice you control and want to make well, such as how many loaves to bake, which route to take or how much money to put in each fund. An optimization problem asks for the best set of decisions. In the math, each decision becomes a decision variable.
Decision variable
A quantity the solver chooses, standing for one decision; for example x = loaves of bread baked per day. A variable has a unit (loaves, kg, $, hours) and a domain. "Variable" on this site always means a decision variable.
Domain
The values a variable may take: any real number, only nonnegative numbers (x >= 0), whole numbers (integer variable) or only 0 and 1 (binary variable).
Parameter
A number in the problem that is given, not chosen, such as a price, a demand or an oven's hours. Changing a parameter changes the problem, not the decisions directly; sensitivity analysis asks what happens when it does.
Set and index
A set lists like things (products, factories, days); an index such as i runs over a set, so one formula like x_i covers every product at once.
Objective
The goal: one quantity to maximize (profit, area, flow) or minimize (cost, time, error). Written as a formula in the variables, called the objective function.
Objective value
The number the objective formula gives for a particular choice of the variables. The optimal value is the best objective value possible.
Constraint
A rule every acceptable answer must obey, written as an equation (=) or an inequality (<=, >=); for example "oven hours used <= oven hours available".
Bound
A constraint on one variable alone, such as 0 <= x <= 10. (In solving, "bound" also means a limit on the optimal value: see lower bound and upper bound.)
Right-hand side
The given number on the right of a constraint, usually a limit or a requirement (hours available, units demanded). Shadow prices measure the value of raising it.
Formulation (model)
The problem written in math: variables, objective and constraints. ProvenDecisions shows the formulation it built so you can check it before trusting the answer.
Feasible point
A choice of all the variables that obeys every constraint. It may not be the best, but it is allowed.
Feasible region (feasible set)
All the feasible points together. With two variables it can be drawn as a shape in the plane; the Graph screen draws it.
Infeasible
No choice obeys all the constraints at once, so the problem has no answer; for example x >= 5 and x <= 3. Usually a typo or a rule that is too strict.
Unbounded
The objective can improve forever while staying feasible, so no best answer exists; usually a missing limit, such as no cap on production.
Optimal solution (optimum)
A feasible point with the best objective value of all feasible points. A problem can have one, several (ties) or none.
Optimal value
The objective value at an optimal solution: the best that can be achieved.
Units
What each number measures (km, $, hours, kg). Every variable, parameter and constraint should have one; mixing units in one constraint (hours plus kg) is a sign of a modelling error.

Kinds of variables and modelling tricks

Continuous variable
A variable that may take any real value in its domain, including fractions, such as 2.5 tonnes.
Integer variable
A variable restricted to whole numbers, for things that cannot be split, such as trucks or people.
Binary variable
An integer variable that can only be 0 or 1: a yes-or-no decision such as "open this warehouse" (1) or not (0).
Linking constraint
A constraint that ties a yes-or-no decision to an amount, for example "ship from a warehouse only if it is open": x <= M*y with y binary.
Big-M
The large constant M in a linking constraint. It must be at least as big as the largest value the amount can really take, and no bigger than needed: a smaller valid M gives a tighter relaxation and a faster, more reliable solve.
Linearization
Rewriting a nonlinear piece (a product of binaries, a maximum, an absolute value) as linear constraints with the same meaning, so the problem stays a linear program or integer program.
Piecewise-linear approximation
Replacing a curve by straight segments. It turns a hard problem into a linear or integer one, at the price of an approximation error that should be stated with the answer.

Kinds of problems

Optimization problem
Choose the decision variables to make the objective as good as possible while obeying the constraints.
Problem class
The kind of problem, decided by the shapes of the objective, the constraints and the variables (linear, quadratic, convex, integer and so on). The class decides which solver can be used and how strong a proof of optimality is possible. The Problem classes screen lists them.
Linear program (LP)
Objective and constraints are all linear (sums of numbers times variables) and the variables are continuous. LPs can be solved exactly and their answers proven optimal with duality.
Integer program (IP, MILP)
A linear program in which some or all variables must be whole numbers. MILP means mixed-integer linear program: some integer, some continuous variables.
Quadratic program (QP)
A linear-constrained problem whose objective also has squares or products of variables, such as the variance in a portfolio. Convex when the quadratic part curves upward (for minimization).
Convex optimization problem
Minimize a convex function over a convex set (or maximize a concave one). Every local optimum is then a global optimum, which is why these problems can be solved reliably.
Conic program
A convex problem whose constraints say that some vectors lie in cones; it covers LPs, second-order cone programs and semidefinite programs in one form.
Second-order cone program (SOCP)
A conic program with constraints of the form "this length is at most that linear quantity", ||A x + b|| <= c^T x + d (the norm is a Euclidean length). Used for distances, robust limits and some risk measures.
Semidefinite program (SDP)
A conic program in which a symmetric matrix built from the variables must be positive semidefinite. Used for ellipses and strong relaxations of nonconvex problems.
Geometric program (GP)
A problem built from monomials and posynomials of positive variables. It looks nonconvex but becomes convex after taking logarithms.
Monomial
A positive constant times a product of positive variables raised to real powers, such as 3 x^2 y^-1.
Posynomial
A sum of monomials, such as x y + 2 x^0.5.
Nonlinear program (NLP)
A problem with at least one nonlinear objective or constraint.
Nonconvex problem
A problem that is not convex. It may have several local optima, so a solver's answer may not be the best one; ProvenDecisions labels such answers as not proven optimal and shows a bound and gap where it can.
Multi-objective problem
A problem with two or more goals that pull against each other, such as low cost and low risk. See Pareto optimal.
Complexity level
ProvenDecisions' scale from 1 to 10 for how hard a problem is to formulate and solve, from small linear programs (low levels) to problems with uncertainty or several stages (levels 8 to 10). Levels 1 to 6 are fully covered, level 7 (nonconvex, multi-objective) in part, and levels 8 to 10 not yet; the app says so and can offer a labelled simpler version.

Classic models

Product-mix problem
Choose how much of each product to make to earn the most from limited resources (machine hours, labour, materials). The usual first linear program.
Diet and blending problem
Choose amounts of ingredients to meet nutrient or quality requirements at the lowest cost.
Knapsack problem
Choose items, each with a value and a weight, to get the most value without exceeding a capacity. A basic integer program with binary variables.
Transportation problem
Ship goods from supplies to demands at the lowest total shipping cost without exceeding any supply.
Assignment problem
Pair workers with jobs, one each, at the lowest total cost.
Network flow
Goods move along the arcs of a network of nodes. Flow conservation holds at ordinary nodes and each arc has a capacity.
Flow conservation
At an ordinary node, flow in equals flow out: nothing is created or lost.
Shortest path
The cheapest or shortest route from one node of a network to another.
Maximum flow and minimum cut
The most that can flow from a source to a sink through capacitated arcs; it equals the smallest total capacity of arcs whose removal cuts the source off from the sink.
Facility location
Decide which sites to open (fixed cost per site) and how to serve customers from them.
Multi-period production and inventory
Plan production over several periods; the inventory balance links them: stock at the end of a period = stock at the start + production − demand.
Portfolio optimization
Choose how much to invest in each asset to balance expected return against risk, usually measured by the variance of the return. A quadratic program.
Least squares
Fit a model to data by choosing parameters that make the sum of squared residuals as small as possible.

Convexity and kinds of optima

Convex set
A set that contains the whole straight segment between any two of its points. A disc is convex; a ring is not, because a segment can cross the hole.
Convex function
A function whose graph never lies above the straight segment joining two of its points; equivalently, it lies above every tangent line. It bends upward like a bowl.
Concave function
A function whose negative is convex: it bends downward like a dome. Maximizing a concave function over a convex set is a convex problem.
Strictly convex function
A convex function with no flat stretches; it has at most one minimum point.
Local optimum
A feasible point that is the best among nearby feasible points, but maybe not overall. Labelled "locally optimal" or "not proven optimal".
Global optimum
A feasible point that is the best among all feasible points.
Vertex (corner point)
A corner of a feasible region bounded by straight lines or flat faces. If a linear program has an optimal solution and its feasible region has corners (for example when every variable is nonnegative), one optimal solution is at a corner.
Inflection point
A point where a curve changes from bending up to bending down or back; the second derivative changes sign there.

Calculus for optimization (the Refreshers)

Derivative
The slope of a function's graph at a point: how fast the value changes per unit change in the input. Written f'(x).
Second derivative
The derivative of the derivative, f''(x): how fast the slope changes, so whether the graph bends up (f'' > 0) or down (f'' < 0).
Partial derivative
For a function of several variables, the derivative with respect to one variable while the others are held fixed.
Gradient
The column of all partial derivatives, written ∇f. It points in the direction of steepest increase; its negative points steepest downhill.
Directional derivative
The rate of change of a function when you move in a chosen direction: the gradient dotted with the unit direction.
Hessian
The symmetric table (matrix) of all second partial derivatives. It describes how the function bends in every direction.
Critical point (stationary point)
A point where the derivative (or every partial derivative, so the gradient) is zero: the graph is flat there. Every interior minimum or maximum of a smooth function is a critical point, but not every critical point is one.
First-derivative test
Classify a critical point by the sign of f' on either side: falling then rising is a minimum, rising then falling a maximum, no change of sign neither.
Second-derivative test
At a critical point, f'' > 0 means a local minimum, f'' < 0 a local maximum, and f'' = 0 gives no conclusion. With several variables the test uses the Hessian's eigenvalues.
Closed-interval method
To find the largest and smallest values of a continuous function on [a, b], compare its values at the critical points inside and at the two ends.
Saddle point
A critical point that is a minimum along some directions and a maximum along others, like the middle of a horse's saddle; its Hessian has eigenvalues of both signs.
Eigenvalue
For a symmetric matrix such as the Hessian, a number that gives the curvature along one special direction (its eigenvector). The signs of the eigenvalues say whether a critical point is a valley, a peak or a saddle.
Positive definite
A symmetric matrix whose eigenvalues are all positive. A positive definite Hessian at a critical point means a strict local minimum; everywhere, it means a strictly convex function.
Positive semidefinite
A symmetric matrix whose eigenvalues are all zero or positive. A function whose Hessian is positive semidefinite everywhere is convex.
Indefinite
A symmetric matrix with both positive and negative eigenvalues; at a critical point it means a saddle.
Taylor approximation
Replacing a function near a point by a simple polynomial: the tangent line (first order) or the tangent parabola (second order), good for small steps.
Newton step
Jump to the minimum of the second-order Taylor approximation: in one variable, step −f'(x) / f''(x). Fast near a minimum when the function bends upward.
Gradient step
Move a little way downhill: x − t ∇f(x), where t is the step length.

Optimality conditions and duality

Lagrangian
The objective plus each constraint multiplied by its own price (its Lagrange multiplier). Optimality conditions and the dual problem are built from it.
Lagrange multiplier
The price attached to a constraint in the Lagrangian. At an optimum it equals the change in the optimal value per unit increase in that constraint's right-hand side, the same thing as a shadow price.
KKT conditions
The Karush–Kuhn–Tucker conditions: the checks that identify an optimum of a smooth constrained problem. Four parts: stationarity, primal feasibility, dual feasibility and complementary slackness. For a convex problem they prove a global optimum; for a nonconvex one they only show a candidate (a KKT point).
Stationarity
The KKT part saying the objective's gradient is balanced by the constraints' gradients weighted by the multipliers: at the optimum, no allowed direction improves the objective.
Primal feasibility
The KKT part saying the point obeys every constraint.
Dual feasibility
The KKT part saying each inequality's multiplier has the right sign (it cannot reward breaking a limit).
Complementary slackness
For each inequality, either the constraint is active or its multiplier is zero: a limit that is not used up is worth nothing at the margin.
Primal problem
The original problem, as you wrote it. Used when talking about its dual problem.
Dual problem
A companion problem built from the primal, whose variables are prices for the constraints. Any feasible dual point gives a bound on the primal's optimal value.
Duality
The relation between a problem and its dual problem; the basis of the proof that an answer is optimal.
Weak duality
The dual's value is never better than the primal's: for minimization, every dual feasible value is a lower bound. It always holds.
Strong duality
The best dual value equals the best primal value, so there is no duality gap. It holds for linear programs with an optimal solution and for most convex problems; it is what makes "Exactly proven optimal" possible.
Duality gap
The difference between the primal's and the dual's values. Zero gap at a pair of feasible points proves both are optimal.
Dual certificate
The prices (dual values) that prove optimality: weighting the constraints by them gives a bound that the answer reaches. ProvenDecisions shows it in the step "Why this is optimal".
Shadow price (dual value)
How much the optimal value changes if a constraint's right-hand side grows by one unit, for example the extra profit from one more oven hour. Valid for small changes.
Reduced cost
For a variable at zero in a linear program's answer, how much its objective coefficient must improve before it is worth using.
Slack
How much of a <= limit is left unused at the answer: right-hand side minus the amount used.
Surplus
How far a >= requirement is exceeded at the answer: amount achieved minus right-hand side.
Active constraint (binding constraint)
A constraint that holds with equality at the answer (zero slack): it is what stops the objective from improving further.
Sensitivity analysis
How the answer and the optimal value change when parameters change: shadow prices, reduced costs and the ranges over which they stay valid.
What-if analysis
Re-solving with a changed parameter (more labour, a different price) to see the new answer.
Marginal value
The value of one more unit of something, such as a resource; for a constraint it is the shadow price.

Solving integer and nonconvex problems

Relaxation
An easier problem made by loosening some rules, for example letting integer variables take fractional values. Its optimal value bounds the original problem's: no better answer is possible.
LP relaxation
The linear program obtained from an integer program by dropping the whole-number requirement.
Convex relaxation
A convex problem whose feasible region contains a nonconvex problem's; its optimal value is a bound, found reliably.
McCormick relaxation
The tightest linear bounds on a product of two bounded variables; a common way to relax a nonconvex product.
Lower bound and upper bound
Limits on the optimal value. For minimization, a relaxation or a dual gives a lower bound (nothing can be better) and any feasible point gives an upper bound (it is achievable); for maximization the roles swap.
Incumbent
The best feasible answer found so far during a search.
Branch and bound
The standard method for integer programs: split the problem on a fractional variable into smaller problems, bound each with its relaxation, and discard ("prune") any whose bound cannot beat the incumbent.
Gap
The difference between the best answer found and the best bound, often as a percentage. A zero gap proves the answer is optimal; a small gap proves it is within that much of optimal.
MIP gap (optimality gap)
The gap for a mixed-integer program. ProvenDecisions reports it with every integer answer; "Optimal within gap tolerance" means the gap is below the solver's tolerance.

Several goals

Pareto optimal
An answer for which no goal can be improved without making another goal worse. There are usually many; together they form the trade-off curve.
Trade-off curve (Pareto front)
All the Pareto optimal answers, plotted goal against goal.
Efficient frontier
The trade-off curve between expected return and risk in portfolio optimization.
Weighted sum
Combine goals into one objective with weights that say how much each matters, then solve once per choice of weights.
Epsilon-constraint method
Keep one goal as the objective and turn the others into constraints ("at most ε on goal 1"); changing ε traces the trade-off curve.

Data fitting

Residual
The difference between an observed value and the model's prediction for it.
Regularization
Adding a penalty on the size of the fitted parameters to the fitting objective, to avoid fitting noise.
Ridge regression
Least squares plus a penalty on the sum of squared parameters (L2); shrinks all parameters smoothly.
Lasso
Least squares plus a penalty on the sum of absolute values of the parameters (L1); sets some parameters exactly to zero.
Maximum likelihood
Choose a model's parameters to make the observed data most probable.
Logistic regression
A model for yes-or-no outcomes whose parameters are fitted by maximum likelihood; a convex optimization problem.

Decisions over time

Dynamic programming
Solve a decision made in stages by working out the best choice from each possible situation, one stage at a time.
Stage and state
A stage is one step in time; the state is what you need to know at that step to decide (stock on hand, money left).
Value function
The best total result achievable from a given state onward.
Bellman equation
The rule linking value functions: the best value now = the best over today's choices of (today's result + the value of the state it leads to).
Backward induction
Solve the Bellman equation from the last stage back to the first.

Solvers and checks

Solver
A program that finds an optimal solution (or proves there is none) for a problem of a given class. Every number in a ProvenDecisions answer comes from a solver or the math kernel, never from a guess.
Math kernel
The exact-math part of ProvenDecisions (SymPy and NumPy): derivatives, exact fractions, checks of feasibility and optimality conditions.
Modelling layer
Software that turns a formulation into the form a solver reads. ProvenDecisions uses cvxpy, which also checks that a model is convex.
HiGHS
A free solver for linear and mixed-integer linear programs (and convex quadratic programs).
Clarabel
A free interior-point solver for convex conic problems (LP, QP, SOCP, SDP and exponential cones).
OSQP
A free solver for convex quadratic programs.
SCS
A free solver for large convex conic problems; fast, with moderate accuracy.
SCIP
A free solver for mixed-integer problems.
SciPy
A free scientific library for Python; ProvenDecisions uses its local solvers for smooth nonconvex problems.
SymPy
A free library for exact, symbolic math; ProvenDecisions uses it for derivatives and exact checks, and to compute every number in the Refreshers.
Solver status
What the solver reports: optimal, infeasible, unbounded, or stopped (for example at a time limit). A status alone is not a proof; ProvenDecisions adds its own checks.
Tolerance
How small an error is treated as zero, because computers round. A constraint off by less than the tolerance counts as satisfied; answers are correct to about that accuracy.
Feasibility check
Putting the answer back into every constraint to confirm it obeys them all; shown in the Answer step.
Verification
The checks after every solve: solver status, feasibility of every constraint, whole-number variables really whole, and an independent optimality check (the dual for a linear program, the KKT conditions for a smooth problem). An answer that fails is marked "Not verified".
Exactly proven optimal
The strongest label: a linear program whose dual certificate was re-checked in exact fractions, not rounded decimals.
Optimal, numerically checked
The optimality conditions or the dual check hold to many decimal places, but no exact proof was produced.
Optimal within gap tolerance
A whole-number problem whose search proved the answer is best within a tiny tolerance.
Optimal per solver
The solver reports optimal and no independent check applied.
Not proven optimal
A local optimum, limited solver accuracy or a nonconvex problem; a better answer may exist, and the app says so.

On this website

Walkthrough
The step-by-step explanation with every answer: the decisions, goal and rules in words, then (at higher depths) the math, the code, the solver and how to read the result.
Walkthrough depth
How much detail the walkthrough shows, from 1 (the answer and a one-line formulation) to 10 (the full derivation); the default is 3.
How we named your variables
For a word problem, the list that says which letter or name stands for which decision, with its unit. You can choose the names yourself.
Workspace
The screen for typing and running models directly, like a small MATLAB or Mathematica window, with a figure for two-variable problems.
Refreshers
Short calculus refreshers in one, two and three variables, aimed at the ideas optimization uses; free.
Solved examples
Worked problems with their formulation, verified answer and walkthrough.
Hodos
The in-app assistant on paid plans: it answers questions about ProvenDecisions and the problem you are looking at, from the Help articles and the solved examples, with links.

Try ProvenDecisions free: type, photograph or say an optimization problem; every answer is checked by a solver.

What do you want to optimize?

Type the math, describe it in words, snap a photo or say it. ProvenDecisions builds the model, solves it, checks it and walks you through it.

One constraint per line, or separated by commas. Add integer: x, y or binary: z for whole-number decisions. LaTeX works too.

Try: