Courses / Mathematics / Optimization: models, certificates and algorithms Mathematics · unit version 1 Optimization: models, certificates and algorithms Twenty-seven lessons derive linear and nonlinear optimization methods, their guarantees and their failure modes. Exact certificates are separated from numerical stopping evidence, and continuous relaxations from integer decisions. Independent modeling, mixed assessment and proof review remain separate requirements; publication does not establish universal course equivalence.
Open any lesson. Completion records participation; automatic practice checks and human judgment of written arguments are separate. This unit retains its own versioned requirements.
Readiness and preparation Check your starting point Try these short questions on paper, then compare your reasoning. They are optional self-checks, not a placement score or a navigation requirement. Use a targeted review when useful and return with your browser’s Back control.
Does a zero gradient prove a minimum? Optimality conditions have necessary and sufficient forms.
Compare reasoning and find a refresher No. It is a necessary condition for an unconstrained differentiable interior local extremum, but saddles and maxima can also have zero gradient. Additional curvature or convexity conditions are needed.
Review gradients and local approximation
Why does a continuous function on a compact nonempty feasible set attain its minimum? A solver needs a well-posed mathematical target before an algorithm is chosen.
Compare reasoning and find a refresher The extreme-value theorem guarantees attainment. On an open or unbounded feasible set the infimum may be unattained or infinite; those cases need separate analysis.
Review attainment of extrema
How does a matrix describe simultaneous linear resource constraints? Linear programs and their duals use rows for constraints and columns for variables.
Compare reasoning and find a refresher The ith component of Ax is the dot product of row i with x. In Ax≤b every row inequality must hold separately. Aᵀ combines multipliers across rows to compare coefficients of each variable.
Review systems and matrix rows
Loading saved mathematics work…
Optimization: certify decisions and audit algorithms
The mixed assessment has separate response history and review criteria; it does not change lesson participation records.
Optimization investigation: build, break and defend a certificate
Sustained investigation with separate transfer evidence, saved revisions and human review. It does not change lesson participation requirements.
Lesson sequence Each linked lesson opens on its own page. Expand its details here when you want to check the objectives before choosing.
Lesson details and objectives Specify objectives, feasible sets and attainment before selecting an algorithm.
Formulate a constrained decision problem. Distinguish an infimum from an attained minimum. Apply compactness or coercivity to prove existence. 6 practice tasks.
Lesson details and objectives Prove convex closure rules and the projection variational inequality.
Verify convex sets by the segment definition. Prove existence and uniqueness of Euclidean projection. Use a projection inequality as a certificate. 6 practice tasks.
Lesson details and objectives Connect convexity, subgradients and positive-semidefinite curvature.
Prove first-order convex inequalities. Use Hessians to check smooth convexity. Separate strict and strong convexity. 6 practice tasks.
Lesson details and objectives Derive necessary and sufficient local conditions.
Prove interior first-order necessity. Classify nondegenerate Hessians. Explain inconclusive semidefinite cases. 6 practice tasks.
Lesson details and objectives Identify feasible faces, finite optima and improving rays.
Formulate an LP with a consistent sign convention. Solve a two-variable LP geometrically. Distinguish unbounded feasibility from unbounded objective. 6 practice tasks.
Lesson details and objectives Prove the standard-form vertex criterion.
Construct a basis in equality standard form. Prove vertex and basic-feasible equivalence. Recognize degenerate bases. 6 practice tasks.
Lesson details and objectives Derive reduced costs and the minimum-ratio step.
Compute a simplex direction from a basis. Apply the ratio test with correct signs. Read optimality or unboundedness certificates. 6 practice tasks.
Lesson details and objectives Use artificial variables and understand zero-length pivots.
Construct a Phase I feasibility problem. Interpret its optimum correctly. Explain cycling and an anti-cycling rule. 6 practice tasks.
Lesson details and objectives Prove the finite-dimensional alternative behind LP duality.
State a consistent Farkas sign convention. Verify infeasibility certificates. Explain the closed-cone separation mechanism. 6 practice tasks.
Lesson details and objectives Derive weak duality and a finite-dimensional strong-duality proof mechanism.
Construct the dual with consistent signs. Prove weak duality. Explain why a finite primal optimum has a dual certificate. 6 practice tasks.
Lesson details and objectives Use primal and dual slacks to certify an optimum.
Derive the gap decomposition. Apply complementary slackness in both directions. Interpret positive multipliers without reversing implications. 6 practice tasks.
Lesson details and objectives Derive value bounds and basis-preserving ranges.
Use dual solutions as global parameter bounds. Compute a basis-feasibility interval. Identify nondifferentiable value functions. 6 practice tasks.
Lesson details and objectives Derive a central-cut ellipsoid update and qualify polynomial-time claims.
Verify a separating cut. Derive the enclosing central-cut ellipsoid. State the precision and oracle assumptions behind complexity. 6 practice tasks.
Lesson details and objectives Derive descent and convergence bounds rather than trusting a trace.
Prove the descent lemma. Choose a step from a Lipschitz-gradient bound. Distinguish stationarity and global convergence. 6 practice tasks.
Lesson details and objectives Prove backtracking termination and state global convergence conditions.
Apply Armijo backtracking. Prove finite acceptance for descent directions. Identify what a decrease test does not guarantee. 6 practice tasks.
Lesson details and objectives Analyze Newton step s and safeguarded Hessian approximations.
Compute Newton directions by a linear solve. State local quadratic-convergence hypotheses. Explain damping and positive-definite updates. 6 practice tasks.
Lesson details and objectives Connect constrained stationarity to the implicit-function theorem.
Identify tangent and normal spaces. Derive Lagrange necessity under full rank. Solve and verify an equality-constrained problem. 6 practice tasks.
Lesson details and objectives Use active sets, sign conventions and a qualification counterexample.
Write KKT conditions for minimization. State a sufficient constraint qualification. Prove convex KKT sufficiency. 6 practice tasks.
Lesson details and objectives Use the Lagrangian Hessian rather than the objective Hessian alone.
Derive tangent-space second-order tests. Define critical directions for inequalities. Recognize degeneracy in constrained tests. 6 practice tasks.
Lesson details and objectives Derive dual functions, strong-duality conditions and nonattainment examples.
Compute a dual function by infimization. Prove weak duality for minimization. State Slater with its relevant domain conditions. 8 practice tasks.
Lesson details and objectives Derive the logarithmic central path and its duality-gap interpretation.
Compute barrier gradients and Hessians. Explain feasible damped Newton step s. Derive the m/t gap under exact centrality. 6 practice tasks.
Lesson details and objectives Use trace geometry and matrix-value d primal–dual certificates.
Check the PSD cone in small matrices. Derive an SDP dual and weak-duality gap. Distinguish rank constraints from convex relaxation. 6 practice tasks.
Lesson details and objectives Derive projection and proximal optimality relations.
Compute projected-gradient step s. Derive soft thresholding. State convergence assumptions for composite convex methods. 6 practice tasks.
Lesson details and objectives Compare integer feasibility with the relaxed polyhedron.
Construct a valid relaxation. Use its objective as a bound. Diagnose rounding and integrality gaps. 6 practice tasks.
Lesson details and objectives Track incumbent value s, node bounds and exhaustive coverage.
Branch into an exhaustive disjoint split. Prune nodes using valid bounds. Report a certified remaining gap. 6 practice tasks.
Lesson details and objectives Analyze domination, weighted sum s and unsupported efficient points.
Define Pareto efficiency precisely. Prove positive-weight optima are efficient. Identify limits of weighted scalarization. 6 practice tasks.
Lesson details and objectives Derive robust counterparts and distinguish guarantees from calibration.
Convert box uncertainty into a deterministic constraint. Use norm support functions. Separate robust feasibility from probabilistic coverage. 6 practice tasks.
Learn