Skip to content

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.

12 chapters · 28 sectionsEN · 繁 · 简
My course notes

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.

Open this course in the knowledge map

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.

Open this course in the knowledge map

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.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

  1. 2.1

    Lagrange duality and KKT certificates

    Dual lower bounds and constrained optimality certificates.

  2. 2.2

    Farkas' alternative and linearized optimality

    Derive a certificate of linear infeasibility and connect linearized descent to multiplier conditions.

  3. 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

  1. 3.1

    Descent, conjugate directions, and BFGS

    Line searches, conjugate directions, and inverse BFGS updates.

  2. 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

  1. 4.1

    Local optimality and constraint qualifications

    Feasible and critical directions, multiplier qualifications, and second-order conditions.

  2. 4.2

    Constraint qualification and stable multipliers

    Use feasible directions to understand MFCQ, KKT multipliers, and their boundedness.

  3. 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

  1. 5.1

    Separation, subgradients, and strong duality

    Separation and a perturbation proof of Slater duality with sensitivity.

  2. 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.

  3. 5.3

    Recession directions and existence of minimizers

    Use closed convex geometry to distinguish escape directions, bounded level sets, attainment, and uniqueness.

  4. 5.4

    Fenchel conjugacy and dual certificates

    Conjugates, Fenchel equality and equality-constrained dual certificates.

  5. 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

  1. 6.1

    Line searches, convergence, and Newton's method

    Armijo and Wolfe convergence and local Newton convergence.

  2. 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

  1. 7.1

    Conjugate gradient and quasi-Newton updates

    CG recurrences, BFGS curvature, and qualified convergence results.

  2. 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.

  3. 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.

  4. 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

  1. 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

  1. 9.1

    Soft thresholding as a proximal map

    Use subgradients to derive the threshold rule and prove stability.

  2. 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

  1. 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.

  2. 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

  1. 11.1

    Exact penalties and augmented Lagrangians

    Use dual multipliers to prove exactness and derive an equality-constrained augmented-Lagrangian algorithm.

  2. 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

  1. 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.

Vercel visit statistics and public-page performance measurements each require separate consent. Neither is needed to use the website.

Website function storage (used when needed)

Security, sign-in and your chosen preferences use storage when needed. This is separate from optional statistics.

Withdrawing stops future statistics. The page reloads if analytics code needs unloading. It does not delete data already sent.

Read Cookie and storage details