Optimisation: formulas
Pick a formula to see it explained with worked examples and a solver that shows every step.
About this topic
Optimisation is finding the best choice, like the lowest cost or the biggest result, when you have rules to follow. On this page you will find 11 pages, such as Soft-thresholding (LASSO), Gradient descent rate (strongly convex) and Linear programming duality.
On every page you get worked examples, the common slips to avoid and a solver that shows the working. A friendly first stop is Soft-thresholding (LASSO), or go back to Numerical methods and optimisation.
Formulas in this topic
- Lagrangian dualityFor the problem of minimising f(x) subject to h(x)≤0, the Lagrangian is L(x,λ)=f(x)+λh(x), and the dual…
- Soft-thresholding (LASSO)The soft-thresholding function Sλ(z)=sign(z)(∣z∣−λ)+ shrinks z towards 0 by λ, and sets it to 0 if ∣z∣≤λ.…
- Conjugate gradient stepIn the conjugate gradient method for Ax=b (with A symmetric positive definite) the step length along the…
- Gradient descent rate (strongly convex)For a function that is μ-strongly convex with L-Lipschitz gradient, gradient descent with step 1/L satisfies…
- Gradient descentGradient descent minimises f by moving against the gradient: xk+1=xk−α∇f(xk), where α>0 is the step size…
- Newton’s method for optimisationNewton's method for minimisation updates xk+1=xk−H−1∇f(xk), where H is the Hessian. In one variable:…
- Convex functionA function is convex if f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y) for λ∈[0,1]: the chord lies on or above the graph. For…
- KKT conditionsFor minimising f subject to gi≤0, the KKT conditions at a minimum are ∇f+∑λi∇gi=0, λi≥0, and…
- Linear programming dualityThe primal problem max{cTx:Ax≤b, x≥0} has the dual min{bTy:ATy≥c, y≥0}. When both are feasible their optimal…
- Simplex pivotIn a simplex step the entering column is the one with the most negative entry in the objective row (largest…
- Linear programming: maximise or minimiseLinear programming finds the best value of a quantity, such as profit or cost, when there are limits on what…
Optimisation questions
What is a minimum?
It is the lowest value something can take.
Can I try my own numbers?
Yes. Open any page, type your own question into the solver and it works it out step by step.