MATH4230
Optimization Theory
Convexity and optimality conditions, Lagrange duality and KKT conditions, descent, Newton and quasi-Newton methods, proximal and projected methods, penalties and interior-point methods.
Your progress
0/ 28 sections marked complete
Next section: Convexity and optimality
Completion marks are saved in this browser.
This course in the web
In the MATH4230 notes
- Theorem cards
- 79
- Definitions
- 35
- Counterexamples
- 30
- Concept lenses
- 17
- Histories of ideas
- 0
- Proof X-rays
- 31
No concept lens from this course is recorded in the web yet.
Counts cover the 28 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
In the webTheorem cards 79 · Definitions 35 · Counterexamples 30 · Concept lenses 17 · Proof X-rays 31
No concept lens from this course is recorded in the web yet.
Counts cover the 28 public sections of this course and what is written in them, not recorded connections. 0 of these sections are indexed into the web in detail so far.
Chapter 1 · 1 section
Convexity and optimality
Convex sets, supporting planes, and local and global minima.
Theorems 3 · Definitions 3Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 1.1
Convexity and optimality
Convex sets, supporting planes, and local and global minima.
Chapter 2 · 3 sections
Lagrange duality and KKT certificates
Dual lower bounds and constrained optimality certificates.
Theorems 9 · Definitions 3Counterexamples 3Lenses 1Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 2.1
Lagrange duality and KKT certificates
Dual lower bounds and constrained optimality certificates.
- 2.2
Farkas' alternative and linearized optimality
Derive a certificate of linear infeasibility and connect linearized descent to multiplier conditions.
- 2.3
Local sensitivity and the multiplier
Derive how an equality-constrained optimum and its value respond to a changing right-hand side.
Chapter 3 · 2 sections
Descent, conjugate directions, and BFGS
Line searches, conjugate directions, and inverse BFGS updates.
Theorems 4 · Definitions 3Counterexamples 2Lenses 1Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 3.1
Descent, conjugate directions, and BFGS
Line searches, conjugate directions, and inverse BFGS updates.
- 3.2
Exact steepest descent on a quadratic
Prove the sharp spectral decrease bound and see why exact line searches can still zigzag.
Chapter 4 · 3 sections
Local optimality and constraint qualifications
Feasible and critical directions, multiplier qualifications, and second-order conditions.
Theorems 7 · Definitions 5Counterexamples 3Lenses 1Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 4.1
Local optimality and constraint qualifications
Feasible and critical directions, multiplier qualifications, and second-order conditions.
- 4.2
Constraint qualification and stable multipliers
Use feasible directions to understand MFCQ, KKT multipliers, and their boundedness.
- 4.3
Equality-constrained quadratics and reduced Hessians
Use feasible directions to decide existence, uniqueness and optimality in a quadratic problem.
Chapter 5 · 5 sections
Separation, subgradients, and strong duality
Separation and a perturbation proof of Slater duality with sensitivity.
Theorems 17 · Definitions 2Counterexamples 7Lenses 4Proof X-rays 5
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 5.1
Separation, subgradients, and strong duality
Separation and a perturbation proof of Slater duality with sensitivity.
- 5.2
Subgradient calculus and projected subgradient steps
Compute supporting slopes with qualified rules and prove a best-iterate and averaged-point rate for nonsmooth convex minimization.
- 5.3
Recession directions and existence of minimizers
Use closed convex geometry to distinguish escape directions, bounded level sets, attainment, and uniqueness.
- 5.4
Fenchel conjugacy and dual certificates
Conjugates, Fenchel equality and equality-constrained dual certificates.
- 5.5
Biconjugacy and closed convex envelopes
Recover a closed convex function from its affine minorants and understand what changes when the hypotheses fail.
Chapter 6 · 2 sections
Line searches, convergence, and Newton's method
Armijo and Wolfe convergence and local Newton convergence.
Theorems 8 · Definitions 4Counterexamples 2Lenses 2Proof X-rays 3
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 6.1
Line searches, convergence, and Newton's method
Armijo and Wolfe convergence and local Newton convergence.
- 6.2
Strong Wolfe bracketing and zoom
Build an oriented line-search bracket, prove finite exact-arithmetic termination, and distinguish mathematical acceptance from numerical stopping.
Chapter 7 · 4 sections
Conjugate gradient and quasi-Newton updates
CG recurrences, BFGS curvature, and qualified convergence results.
Theorems 10 · Definitions 5Counterexamples 4Proof X-rays 5
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 7.1
Conjugate gradient and quasi-Newton updates
CG recurrences, BFGS curvature, and qualified convergence results.
- 7.2
Damped and limited-memory BFGS
Preserve useful curvature in a quasi-Newton update and apply a sequence of inverse updates without storing full matrices.
- 7.3
Nonlinear conjugate gradients and descent
Build Fletcher–Reeves directions, distinguish exact quadratic conjugacy from nonlinear descent, and prove a strong-Wolfe descent bound.
- 7.4
The DFP inverse-Hessian update
Derive the DFP update, prove its curvature properties and apply it to a quadratic.
Chapter 8 · 1 section
8. Projected methods
Prove projected-gradient descent for a smooth convex objective.
Theorems 3 · Definitions 1Counterexamples 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 8.1
Projected gradient for smooth convex objectives
Derive a projection descent inequality and a finite-iteration objective bound.
Chapter 9 · 2 sections
Proximal methods
Derive soft thresholding and its nonexpansiveness.
Theorems 6 · Definitions 3Counterexamples 2Lenses 1Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 9.1
Soft thresholding as a proximal map
Use subgradients to derive the threshold rule and prove stability.
- 9.2
The proximal gradient method
Minimize a smooth convex function plus a simple convex penalty by alternating a gradient step with a proximal map, and prove an O(1/k) objective bound.
Chapter 10 · 2 sections
Trust-region models and first-order convergence
Quadratic model certificates, Cauchy decrease and a safeguarded global stationarity theorem.
Theorems 6 · Definitions 2Counterexamples 2Lenses 3Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 10.1
Trust-region models and first-order convergence
Solve a quadratic model on a ball, derive Cauchy decrease, and prove a bounded-model convergence result.
- 10.2
Cauchy points and truncated conjugate gradient
Construct finite trust-region model solvers, prove sufficient decrease, and interpret interior and boundary residual certificates.
Chapter 11 · 2 sections
Exact penalties and augmented Lagrangians
Exact equality penalties and an augmented-Lagrangian proximal-dual convergence proof.
Theorems 4 · Definitions 2Counterexamples 2Lenses 2Proof X-rays 2
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 11.1
Exact penalties and augmented Lagrangians
Use dual multipliers to prove exactness and derive an equality-constrained augmented-Lagrangian algorithm.
- 11.2
Inequality augmented Lagrangians and projected multipliers
Derive the positive-part augmented Lagrangian, its proximal dual step, and exact convergence with explicit attainment assumptions.
Chapter 12 · 1 section
Barrier and interior-point methods
The logarithmic barrier, the central path and the certified duality gap m/t.
Theorems 2 · Definitions 2Counterexamples 1Lenses 1Proof X-rays 1
Chapter outline →See this chapter on the web →Not yet indexed in the web
- 12.1
The logarithmic barrier method and the central path
Replace inequality constraints by a logarithmic barrier, follow the central path, and certify a duality gap of at most m/t.