Mathematical Optimization Fundamentals Cheat Sheet

Updated 2026-05-19

Next Topic: Mathematical Proof Techniques Cheat Sheet

🧠Study flashcards on this topic136 cards · spaced repetition→

Mathematical optimization is the branch of applied mathematics concerned with finding the best element from a feasible set according to a defined criterion. It underpins machine learning, operations research, economics, and engineering — any domain where resources must be allocated or decisions must be made under constraints. The key mental model is the interplay between the objective function (what you want to minimize or maximize), the feasible region (what's allowed), and the structure of the problem (convex or not, continuous or integer) — because structure determines which algorithms are guaranteed to find a global optimum and which may only find a local one.

What This Cheat Sheet Covers

This topic spans 15 focused tables and 137 indexed concepts, 136 flashcards. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.

Table 1: Linear Programming FormulationTable 2: Simplex MethodTable 3: LP DualityTable 4: Convex Sets and Convex FunctionsTable 5: Lagrange Multipliers and KKT ConditionsTable 6: Gradient-Based Optimization MethodsTable 7: Newton's Method and Quasi-Newton MethodsTable 8: Line Search MethodsTable 9: Integer ProgrammingTable 10: Interior Point MethodsTable 11: Augmented Lagrangian and ADMMTable 12: Sequential Quadratic Programming and Nonlinear Constrained OptimizationTable 13: Second-Order Optimality ConditionsTable 14: Dynamic ProgrammingTable 15: Advanced Formulations and Special Problem Classes

Quick IndexSubscribe to unlock

A jump-to index of every table row in this cheat sheet.

Mind MapSubscribe to unlock

An interactive map of every table and concept in this topic.

Table 1: Linear Programming Formulation

Linear programming (LP) provides the foundational language for optimization problems where both the objective and all constraints are linear functions of the decision variables. Understanding standard form, canonical form, and slack variables is prerequisite to every solver and algorithm that follows.

Method	Example	Description
Standard Form (LP)	$\max\ \mathbf{c}^\top \mathbf{x}$ s.t. $A\mathbf{x} \leq \mathbf{b},\ \mathbf{x} \geq 0$	• LP form with $\leq$ inequality constraints and non-negative variables • most solvers convert to this before processing
Canonical / Equality Form	$\max\ \mathbf{c}^\top \mathbf{x}$ s.t. $A\mathbf{x} = \mathbf{b},\ \mathbf{x} \geq 0$	• Each $\leq$ constraint is converted to equality by adding a slack variable $s_i \geq 0$ • required by the simplex method
Slack Variable	$a_1 x_1 + a_2 x_2 + s = b,\ s \geq 0$	• Non-negative variable added to a $\leq$ constraint to convert it to equality • $s = 0$ at the constraint boundary
Surplus Variable	$a_1 x_1 + a_2 x_2 - s = b,\ s \geq 0$	• Non-negative variable subtracted from a $\geq$ constraint to convert it to equality • used in Phase I / Big M
Objective Function	$z = 3x_1 + 5x_2$	• The linear expression to be maximized or minimized • coefficients $\mathbf{c}$ encode the value of each variable
Feasible Region	Polygon defined by $Ax \leq b,\ x \geq 0$	• The set of all variable values satisfying every constraint • for LP it is a convex polyhedron.
Vertex / Corner-Point Solution	Intersection of two constraint lines in 2-D	Optimal LP solution always occurs at a vertex (extreme point) of the feasible polyhedron when one exists.
Bounded vs Unbounded LP	Unbounded: $\max x_1$ with no upper bound on $x_1$	• LP is bounded if optimal value is finite • unbounded if the objective can increase indefinitely within the feasible region
Infeasible LP	$x \geq 5$ and $x \leq 2$ simultaneously	• No point satisfies all constraints • the feasible region is empty.
Non-negativity Constraint	$x_1, x_2 \geq 0$	• Structural requirement • free (unrestricted) variables can be split: $x = x^+ - x^-,\ x^+, x^- \geq 0$.

Table 2: Simplex Method

The simplex method is the workhorse algorithm for solving linear programs, iterating across vertices of the feasible polyhedron until optimality is confirmed. Mastering the tableau pivot mechanics and optimality conditions is essential for understanding how most LP solvers behave internally.

Method	Example	Description
Simplex Tableau	Matrix $[A \mid \mathbf{b}]$ augmented with objective row	Compact bookkeeping structure for tracking basic variables, reduced costs, and the right-hand side during pivoting.

The rest of this section is part of the full cheat sheet

Table 3: LP Duality

Every linear program has a paired dual problem whose optimal value equals the primal's under strong duality, providing both theoretical insight and practical tools like sensitivity analysis and complementary slackness.

Concept	Example	Description
Primal–Dual Pair	Primal: $\max \mathbf{c}^\top x$, s.t. $Ax \leq b, x \geq 0$ Dual: $\min \mathbf{b}^\top y$, s.t. $A^\top y \geq c, y \geq 0$	• Every LP (primal) has an associated dual LP • dualizing twice recovers the primal

The rest of this section is part of the full cheat sheet

Table 4: Convex Sets and Convex Functions

Convexity is the property that makes an optimization problem tractable: for convex problems, any local minimum is also a global minimum. Recognizing convex sets and functions — and exploiting their properties — is the foundation of modern optimization theory.

Concept	Example	Description
Convex Set	Hyperplane, half-space, polyhedron, ball	• A set $C$ where for any $x, y \in C$ and $\theta \in [0,1]$: $\theta x + (1-\theta) y \in C$ • the line segment between any two points stays inside

The rest of this section is part of the full cheat sheet

Table 1: Linear Programming Formulation

Method	Example	Description
Standard Form (LP)	$\max\ \mathbf{c}^\top \mathbf{x}$ s.t. $A\mathbf{x} \leq \mathbf{b},\ \mathbf{x} \geq 0$	• LP form with $\leq$ inequality constraints and non-negative variables • most solvers convert to this before processing
Canonical / Equality Form	$\max\ \mathbf{c}^\top \mathbf{x}$ s.t. $A\mathbf{x} = \mathbf{b},\ \mathbf{x} \geq 0$	• Each $\leq$ constraint is converted to equality by adding a slack variable $s_i \geq 0$ • required by the simplex method
Slack Variable	$a_1 x_1 + a_2 x_2 + s = b,\ s \geq 0$	• Non-negative variable added to a $\leq$ constraint to convert it to equality • $s = 0$ at the constraint boundary
Surplus Variable	$a_1 x_1 + a_2 x_2 - s = b,\ s \geq 0$	• Non-negative variable subtracted from a $\geq$ constraint to convert it to equality • used in Phase I / Big M
Objective Function	$z = 3x_1 + 5x_2$	• The linear expression to be maximized or minimized • coefficients $\mathbf{c}$ encode the value of each variable
Feasible Region	Polygon defined by $Ax \leq b,\ x \geq 0$	• The set of all variable values satisfying every constraint • for LP it is a convex polyhedron.
Vertex / Corner-Point Solution	Intersection of two constraint lines in 2-D	Optimal LP solution always occurs at a vertex (extreme point) of the feasible polyhedron when one exists.
Bounded vs Unbounded LP	Unbounded: $\max x_1$ with no upper bound on $x_1$	• LP is bounded if optimal value is finite • unbounded if the objective can increase indefinitely within the feasible region
Infeasible LP	$x \geq 5$ and $x \leq 2$ simultaneously	• No point satisfies all constraints • the feasible region is empty.
Non-negativity Constraint	$x_1, x_2 \geq 0$	• Structural requirement • free (unrestricted) variables can be split: $x = x^+ - x^-,\ x^+, x^- \geq 0$.

Table 2: Simplex Method

Method	Example	Description
Simplex Tableau	Matrix $[A \mid \mathbf{b}]$ augmented with objective row	Compact bookkeeping structure for tracking basic variables, reduced costs, and the right-hand side during pivoting.

Table 3: LP Duality

Concept	Example	Description
Primal–Dual Pair	Primal: $\max \mathbf{c}^\top x$, s.t. $Ax \leq b, x \geq 0$ Dual: $\min \mathbf{b}^\top y$, s.t. $A^\top y \geq c, y \geq 0$	• Every LP (primal) has an associated dual LP • dualizing twice recovers the primal

Table 4: Convex Sets and Convex Functions

Concept	Example	Description
Convex Set	Hyperplane, half-space, polyhedron, ball	• A set $C$ where for any $x, y \in C$ and $\theta \in [0,1]$: $\theta x + (1-\theta) y \in C$ • the line segment between any two points stays inside