Home All Subjects Progress Videos Graphics

Progress

241 / 241 subjects

Phases

15-08 — Lagrange Multipliers and Constrained Optimization

Phase: Numerical Methods for ML | Subject: 15-08 Prerequisites: 15-01-floating-point-arithmetic.md, 15-04-backpropagation-implementation.md, 15-05-numerical-linear-algebra-ml.md, 04-03-derivatives.md, 04-08-optimization.md Next subject: 15-09-convexity.md

Learning Objectives

By the end of this subject, you will be able to:

  1. Formulate constrained optimization problems with equality and inequality constraints
  2. Derive and apply the method of Lagrange multipliers for equality-constrained problems
  3. State and interpret the KKT (Karush-Kuhn-Tucker) conditions for general constrained optimization
  4. Solve constrained optimization problems analytically using Lagrange multipliers
  5. Explain the Lagrangian's role in SVM, PCA, and other ML algorithms

Core Content

The Constrained Optimization Problem

Many ML problems involve minimizing a function subject to constraints. The general form:

$$\begin{aligned} \min_{\mathbf{x} \in \mathbb{R}^n} \quad & f(\mathbf{x}) \ \text{subject to} \quad & g_i(\mathbf{x}) \leq 0, \quad i = 1, \ldots, m \ & h_j(\mathbf{x}) = 0, \quad j = 1, \ldots, p \end{aligned}$$

where $f, g_i, h_j: \mathbb{R}^n \to \mathbb{R}$ are (typically) continuously differentiable.

⚠️ CRITICAL — Without constraints, we just set $\nabla f(\mathbf{x}) = \mathbf{0}$ and solve. With constraints, the optimal point may lie on the boundary of the feasible set, where $\nabla f \neq \mathbf{0}$. The constraints introduce "forces" that balance the gradient — this is the key insight behind Lagrange multipliers.

Equality Constraints: Lagrange Multipliers

For a single equality constraint $h(\mathbf{x}) = 0$, the method of Lagrange multipliers says:

At a constrained local extremum $\mathbf{x}^*$, the gradient of $f$ must be parallel to the gradient of $h$:

$$\nabla f(\mathbf{x}^) = \lambda \, \nabla h(\mathbf{x}^)$$

for some scalar $\lambda$ (the Lagrange multiplier).

Why? Geometrically: $\nabla h(\mathbf{x}^*)$ is perpendicular to the constraint surface ${\mathbf{x} : h(\mathbf{x}) = 0}$. If $\nabla f$ had any component tangent to the surface, we could move along the surface to decrease/increase $f$. At an extremum, no such tangential component exists — $\nabla f$ must be purely normal to the surface, hence parallel to $\nabla h$.

The Lagrangian function encapsulates this:

$$\mathcal{L}(\mathbf{x}, \lambda) = f(\mathbf{x}) + \lambda \, h(\mathbf{x})$$

(some conventions use $-$; the sign of $\lambda$ flips). Setting $\nabla_{\mathbf{x}, \lambda} \mathcal{L} = \mathbf{0}$ gives:

$$\nabla_{\mathbf{x}} \mathcal{L} = \nabla f(\mathbf{x}) + \lambda \nabla h(\mathbf{x}) = \mathbf{0}, \quad \frac{\partial \mathcal{L}}{\partial \lambda} = h(\mathbf{x}) = 0$$

These $n + 1$ equations determine the $n + 1$ unknowns $\mathbf{x}^, \lambda^$.

Multiple equality constraints $h_j(\mathbf{x}) = 0$: Generalize to:

$$\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_{j=1}^p \lambda_j h_j(\mathbf{x})$$

$$\nabla f(\mathbf{x}^) + \sum_{j=1}^p \lambda_j^ \nabla h_j(\mathbf{x}^*) = \mathbf{0}$$

$\nabla f$ is a linear combination of the constraint gradients.

Inequality Constraints: KKT Conditions

When constraints are inequalities $g_i(\mathbf{x}) \leq 0$, the situation is richer. Some constraints may be active ($g_i(\mathbf{x}^) = 0$) or inactive ($g_i(\mathbf{x}^) < 0$) at the optimum.

The Lagrangian for the general problem:

$$\mathcal{L}(\mathbf{x}, \boldsymbol{\mu}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_{i=1}^m \mu_i g_i(\mathbf{x}) + \sum_{j=1}^p \lambda_j h_j(\mathbf{x})$$

The Karush-Kuhn-Tucker (KKT) conditions are necessary for a local minimum $\mathbf{x}^*$ (under mild regularity conditions like Slater's condition or LICQ):

  1. Stationarity: $\nabla f(\mathbf{x}^) + \sum_{i=1}^m \mu_i^ \nabla g_i(\mathbf{x}^) + \sum_{j=1}^p \lambda_j^ \nabla h_j(\mathbf{x}^*) = \mathbf{0}$

  2. Primal feasibility: $g_i(\mathbf{x}^) \leq 0$ for all $i$, $h_j(\mathbf{x}^) = 0$ for all $j$

  3. Dual feasibility: $\mu_i^* \geq 0$ for all $i$ (inequality multipliers are nonnegative)

  4. Complementary slackness: $\mu_i^ \, g_i(\mathbf{x}^) = 0$ for all $i$

⚠️ CRITICAL — Complementary slackness is the key to understanding active constraints. It says: for each inequality constraint, either the multiplier is zero (the constraint is inactive and doesn't affect the solution), OR the constraint is tight (active, $g_i = 0$) and the multiplier can be nonzero. You can't have both $\mu_i > 0$ and $g_i < 0$ simultaneously.

Why $\mu_i \geq 0$ for inequality constraints? Consider $g(\mathbf{x}) \leq 0$. If the constraint is active, moving into the feasible region means $g$ decreases (more negative). For the Lagrangian to be stationary, $\nabla f = -\mu \nabla g$. If $f$ decreases when we move into the feasible region, then $\nabla f$ points outward, $\nabla g$ points outward, so $\mu$ must be positive to balance. The sign convention ensures the Lagrange multiplier penalizes constraint violation in the correct direction.

Duality: The Lagrangian Dual

The primal problem is $\min_{\mathbf{x}} \sup_{\boldsymbol{\mu} \geq \mathbf{0}, \boldsymbol{\lambda}} \mathcal{L}(\mathbf{x}, \boldsymbol{\mu}, \boldsymbol{\lambda})$. The dual problem swaps the order:

$$g(\boldsymbol{\mu}, \boldsymbol{\lambda}) = \inf_{\mathbf{x}} \mathcal{L}(\mathbf{x}, \boldsymbol{\mu}, \boldsymbol{\lambda})$$

$$\max_{\boldsymbol{\mu} \geq \mathbf{0}, \boldsymbol{\lambda}} \; g(\boldsymbol{\mu}, \boldsymbol{\lambda})$$

Weak duality: $d^ \leq p^$ (dual optimum $\leq$ primal optimum). Always holds.

Strong duality: $d^ = p^$ when the problem is convex and a constraint qualification (e.g., Slater's condition) holds. This means solving the dual gives the exact primal solution.

The duality gap $p^ - d^ \geq 0$ is zero under strong duality. The dual formulation is often easier to solve — this is exploited in SVMs (kernel trick via dual) and many other ML algorithms.

The Lagrangian in ML: Support Vector Machines

The hard-margin SVM primal:

$$\min_{\mathbf{w}, b} \frac{1}{2}|\mathbf{w}|^2 \quad \text{s.t.} \quad y_i(\mathbf{w}^T \mathbf{x}_i + b) \geq 1, \; i = 1, \ldots, N$$

Rewrite as $1 - y_i(\mathbf{w}^T \mathbf{x}_i + b) \leq 0$. The Lagrangian:

$$\mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha}) = \frac{1}{2}|\mathbf{w}|^2 + \sum_{i=1}^N \alpha_i (1 - y_i(\mathbf{w}^T \mathbf{x}_i + b)), \quad \alpha_i \geq 0$$

KKT stationarity with respect to $\mathbf{w}$:

$$\frac{\partial \mathcal{L}}{\partial \mathbf{w}} = \mathbf{w} - \sum_{i=1}^N \alpha_i y_i \mathbf{x}i = \mathbf{0} \implies \mathbf{w} = \sum{i=1}^N \alpha_i y_i \mathbf{x}_i$$

The optimal $\mathbf{w}$ is a linear combination of training examples — the representer theorem in action. Only examples with $\alpha_i > 0$ (support vectors) contribute.

Substituting back gives the dual:

$$\max_{\boldsymbol{\alpha}} \sum_{i=1}^N \alpha_i - \frac{1}{2}\sum_{i,j} \alpha_i \alpha_j y_i y_j \mathbf{x}_i^T \mathbf{x}_j \quad \text{s.t.} \quad \alpha_i \geq 0, \sum_i \alpha_i y_i = 0$$

The dual depends only on inner products $\mathbf{x}_i^T \mathbf{x}_j$ — this is what enables the kernel trick.

The Lagrangian in ML: PCA as Constrained Optimization

PCA finds the direction of maximum variance. For centered data with covariance $\Sigma$:

$$\max_{\mathbf{v}} \mathbf{v}^T \Sigma \mathbf{v} \quad \text{s.t.} \quad |\mathbf{v}|^2 = 1$$

Lagrangian: $\mathcal{L}(\mathbf{v}, \lambda) = \mathbf{v}^T \Sigma \mathbf{v} + \lambda(1 - \mathbf{v}^T \mathbf{v})$.

Stationarity: $\nabla_{\mathbf{v}} \mathcal{L} = 2\Sigma \mathbf{v} - 2\lambda \mathbf{v} = \mathbf{0} \implies \Sigma \mathbf{v} = \lambda \mathbf{v}$.

The optimal $\mathbf{v}$ is an eigenvector of $\Sigma$, and $\lambda = \mathbf{v}^T \Sigma \mathbf{v}$ is the corresponding eigenvalue (the variance). The first principal component is the top eigenvector — Lagrange multipliers directly reveal the eigenvalue problem structure!

For $k$ principal components, we add orthogonality constraints $\mathbf{v}_i^T \mathbf{v}_j = 0$ for $i \neq j$, yielding the full eigendecomposition.

Key Terms

Worked Examples

Example 1: Maximum Entropy Distribution

Find the probability distribution $p_1, p_2, p_3$ on three outcomes that maximizes entropy $H = -\sum_i p_i \log p_i$ subject to $\sum_i p_i = 1$.

Solution: Lagrangian (using natural log): $\mathcal{L} = -\sum_{i=1}^3 p_i \ln p_i + \lambda(\sum_i p_i - 1)$.

Stationarity for each $p_k$:

$$\frac{\partial \mathcal{L}}{\partial p_k} = -\ln p_k - 1 + \lambda = 0 \implies \ln p_k = \lambda - 1 \implies p_k = e^{\lambda - 1}$$

All $p_k$ are equal! From $\sum p_k = 1$: $3e^{\lambda - 1} = 1 \implies e^{\lambda - 1} = 1/3$.

So $p_1 = p_2 = p_3 = 1/3$ — the uniform distribution maximizes entropy (as intuition suggests). Maximum entropy: $H = -\sum (1/3)\ln(1/3) = \ln 3$.

Note: the second-order condition (Hessian of $-p\ln p$ is negative definite) confirms this is a maximum, not a minimum.

Click for answer $p_i = 1/3$ for all $i$. The uniform distribution maximizes entropy — Lagrange multipliers formalize the intuition that, without additional constraints, the least informative distribution is the uniform one. This principle generalizes: max-entropy distributions with moment constraints yield exponential family distributions.

Example 2: Minimum-Norm Solution with Linear Constraint

Find $\mathbf{x} \in \mathbb{R}^n$ minimizing $|\mathbf{x}|^2$ subject to $\mathbf{a}^T \mathbf{x} = b$ (where $\mathbf{a} \neq \mathbf{0}$).

Solution: Lagrangian: $\mathcal{L}(\mathbf{x}, \lambda) = \frac{1}{2}|\mathbf{x}|^2 + \lambda(b - \mathbf{a}^T \mathbf{x})$.

Stationarity: $\nabla_{\mathbf{x}} \mathcal{L} = \mathbf{x} - \lambda \mathbf{a} = \mathbf{0} \implies \mathbf{x}^* = \lambda \mathbf{a}$.

Constraint: $\mathbf{a}^T \mathbf{x}^* = \lambda |\mathbf{a}|^2 = b \implies \lambda = b / |\mathbf{a}|^2$.

Therefore: $\mathbf{x}^* = \frac{b}{|\mathbf{a}|^2} \mathbf{a}$.

The minimum norm is $|\mathbf{x}^*| = |b| / |\mathbf{a}|$. Geometrically: the shortest vector to the hyperplane $\mathbf{a}^T \mathbf{x} = b$ is perpendicular to it (parallel to $\mathbf{a}$).

Click for answer $\mathbf{x}^* = \frac{b}{\|\mathbf{a}\|^2}\mathbf{a}$. This is a classic result: the projection of the origin onto the hyperplane $\mathbf{a}^T \mathbf{x} = b$. The Lagrange multiplier $\lambda = b/\|\mathbf{a}\|^2$ measures the sensitivity of the minimum norm to changes in $b$.

Example 3: KKT Conditions for a Simple Inequality Problem

$$\min_{x \in \mathbb{R}} (x - 2)^2 \quad \text{s.t.} \quad x \geq 0$$

Rewrite as $g(x) = -x \leq 0$. Solve using KKT.

Solution: Lagrangian: $\mathcal{L}(x, \mu) = (x - 2)^2 + \mu(-x), \quad \mu \geq 0$.

KKT conditions:

  1. Stationarity: $\frac{d\mathcal{L}}{dx} = 2(x-2) - \mu = 0 \implies \mu = 2(x-2)$
  2. Primal feasibility: $-x \leq 0 \implies x \geq 0$
  3. Dual feasibility: $\mu \geq 0$
  4. Complementary slackness: $\mu(-x) = 0$

Case 1: $x = 0$ (constraint active). Then $\mu = 2(0-2) = -4$. But this violates $\mu \geq 0$ — impossible.

Case 2: $\mu = 0$ (constraint inactive). Then $2(x-2) = 0 \implies x = 2$. Check: $x = 2 \geq 0$ ✓. $\mu = 0 \geq 0$ ✓. Complementary slackness: $0 \cdot (-2) = 0$ ✓.

Solution: $x^ = 2$, $f(x^) = 0$. The constraint $x \geq 0$ is inactive at the optimum — the unconstrained minimum already satisfies it.

Now consider instead: $\min (x + 1)^2$ s.t. $x \geq 0$.

KKT: $2(x+1) - \mu = 0 \implies \mu = 2(x+1)$.

If $x = 0$: $\mu = 2 \geq 0$ ✓. All KKT satisfied. $x^ = 0$, $f(x^) = 1$.

If $\mu = 0$: $x = -1$, violates $x \geq 0$. So the constraint is active — the optimum is on the boundary.

Click for answer For $\min (x-2)^2$ s.t. $x \geq 0$: $x^* = 2$ (constraint inactive). For $\min (x+1)^2$ s.t. $x \geq 0$: $x^* = 0$ (constraint active). KKT systematically handles both cases via complementary slackness — the correct active/inactive split emerges from the conditions, no guessing required.

Quiz

Q1: What does the concept of The Lagrangian function primarily refer to in this subject?

A) The definition and application of The Lagrangian function B) A computational error related to The Lagrangian function C) A visual representation of The Lagrangian function D) A historical anecdote about The Lagrangian function

Correct: A)

Q2: Which of the following is the key formula discussed in this subject?

A) \begin{aligned} \min_{\mathbf{x} \in \mathbb{R}^n} \quad & f(\mathbf{x}) \\ \text{subject to} \quad & g_i(\mathbf{x}) \leq 0, \quad i = 1, \ldots, m \\ & h_j(\mathbf{x}) = 0, \quad j = 1, \ldots, p \end{aligned} B) An unrelated formula from a different topic C) A simplified version of \begin{aligned} \min_{\math... D) The inverse operation of the formula in question

Correct: A)

Q3: What is the primary purpose of Lagrangian?

A) It is used to lagrangian in mathematical analysis B) It is used only in advanced research contexts C) It is primarily a historical notation system D) It replaces all other methods in this domain

Correct: A)

Q4: Which statement about Karush-Kuhn-Tucker (KKT) conditions is TRUE?

A) Karush-Kuhn-Tucker (KKT) conditions is a fundamental concept covered in this subject B) Karush-Kuhn-Tucker (KKT) conditions is not related to this subject C) Karush-Kuhn-Tucker (KKT) conditions is mentioned only as a historical footnote D) Karush-Kuhn-Tucker (KKT) conditions is an advanced topic beyond this subject's scope

Correct: A)

Q5: Based on the worked examples in this subject, what is the correct result?

A) A different result from a common mistake B) max-entropy distributions with moment constraints C) The inverse of the correct answer D) An unrelated numerical value

Correct: B)

Q6: How are Karush-Kuhn-Tucker (KKT) conditions and Active constraint related?

A) Karush-Kuhn-Tucker (KKT) conditions is the inverse of Active constraint B) Karush-Kuhn-Tucker (KKT) conditions and Active constraint are completely unrelated topics C) Karush-Kuhn-Tucker (KKT) conditions and Active constraint are closely related concepts D) Karush-Kuhn-Tucker (KKT) conditions is a special case of Active constraint

Correct: C)

Q7: What is a common pitfall when working with Complementary slackness?

A) A common mistake is confusing Complementary slackness with a similar concept B) Complementary slackness has no common misconceptions C) Complementary slackness is always computed the same way in all contexts D) The main error with Complementary slackness is using it when it is not needed

Correct: A)

Q8: When should you apply Constraint qualification?

A) Avoid Constraint qualification unless explicitly instructed B) Use Constraint qualification only in pure mathematics contexts C) Constraint qualification is not practically useful D) Apply Constraint qualification to solve problems in this subject's domain

Correct: D)

Practice Problems

  1. Maximize $f(x, y) = xy$ subject to $x^2 + y^2 = 1$. Interpret the result geometrically.

    Click for answer Lagrangian: $\mathcal{L} = xy + \lambda(1 - x^2 - y^2)$. Stationarity: $\frac{\partial \mathcal{L}}{\partial x} = y - 2\lambda x = 0$, $\frac{\partial \mathcal{L}}{\partial y} = x - 2\lambda y = 0$. Multiply first by $y$, second by $x$: $y^2 - 2\lambda xy = 0$, $x^2 - 2\lambda xy = 0$. Subtract: $y^2 - x^2 = 0 \implies y = \pm x$. With $x^2 + y^2 = 1$: $2x^2 = 1 \implies x = \pm 1/\sqrt{2}$, $y = \pm 1/\sqrt{2}$. Four candidates: $(\pm 1/\sqrt{2}, \pm 1/\sqrt{2})$ with $f = 1/2$, and $(\pm 1/\sqrt{2}, \mp 1/\sqrt{2})$ with $f = -1/2$. Maximum: $f = 1/2$ at $(\pm 1/\sqrt{2}, \pm 1/\sqrt{2})$. Geometrically: the product $xy$ is maximized on the unit circle when $x = y$, i.e., at 45° — the rectangle with given diagonal ($x^2 + y^2 = r^2$) has maximum area when it's a square.

  2. Use KKT to solve: $\min_{x_1, x_2} x_1^2 + x_2^2$ subject to $x_1 + x_2 \geq 1$.

    Click for answer Rewrite: $g(\mathbf{x}) = 1 - x_1 - x_2 \leq 0$. Lagrangian: $\mathcal{L} = x_1^2 + x_2^2 + \mu(1 - x_1 - x_2)$, $\mu \geq 0$. Stationarity: $2x_1 - \mu = 0$, $2x_2 - \mu = 0 \implies x_1 = x_2 = \mu/2$. Complementary slackness: $\mu(1 - x_1 - x_2) = \mu(1 - \mu) = 0$. If $\mu = 0$: $x_1 = x_2 = 0$, but $1 - 0 - 0 = 1 > 0$, violates constraint. ✗ If $\mu = 1$: $x_1 = x_2 = 1/2$. Constraint: $1 - 1/2 - 1/2 = 0$ ✓. $\mu = 1 \geq 0$ ✓. Solution: $x_1^* = x_2^* = 1/2$, $f^* = 1/2$. The constraint is active. Geometrically: the closest point on the half-plane $x_1 + x_2 \geq 1$ to the origin is its projection $(1/2, 1/2)$.

  3. Derive the dual of the hard-margin SVM for the 1D case with points $x_1 = -1$ (label $+1$) and $x_2 = +1$ (label $-1$). Solve the dual and find $\mathbf{w}$.

    Click for answer Primal: $\min_{w,b} \frac{1}{2}w^2$ s.t. $1 \cdot (w(-1) + b) \geq 1$ (for $x_1$) and $(-1) \cdot (w(1) + b) \geq 1$ (for $x_2$). Rewrite: $-w + b \geq 1$ and $-w - b \geq 1$ → $b \geq 1 + w$ and $b \leq -1 - w$. Feasible only if $1 + w \leq -1 - w \implies 2w \leq -2 \implies w \leq -1$. Minimum $w^2/2$ is at $w = -1$, then $b = 0$. Dual approach (confirming): $\alpha_1(1 - (-w + b)) + \alpha_2(1 - (-w - b))$ in Lagrangian. Stationarity for $w$: $w - \alpha_1(-1) - \alpha_2(-1) = w + \alpha_1 + \alpha_2 = 0$? Wait — let's be careful with signs. Primal constraints: $y_i(wx_i + b) \geq 1$. For $i=1$: $1 \cdot (-w + b) \geq 1 \implies -w + b - 1 \geq 0$. For $i=2$: $(-1) \cdot (w + b) \geq 1 \implies -w - b - 1 \geq 0$. Lagrangian: $\mathcal{L} = \frac{1}{2}w^2 - \alpha_1(-w+b-1) - \alpha_2(-w-b-1)$. Stationarity w.r.t $w$: $w + \alpha_1 + \alpha_2 = 0 \implies w = -(\alpha_1 + \alpha_2)$. Stationarity w.r.t $b$: $-\alpha_1 + \alpha_2 = 0 \implies \alpha_1 = \alpha_2$. Dual: substitute $w$, $b$ back. After algebra: $\max 2\alpha - \frac{1}{2}(2\alpha)^2 = 2\alpha - 2\alpha^2$, $\alpha \geq 0$. Maximum at $\alpha = 1/2$. So $\alpha_1 = \alpha_2 = 1/2$, $w = -(\alpha_1 + \alpha_2) = -1$, $b$ is found from complementary slackness: $b = 0$. Both points are support vectors ($\alpha_i > 0$). The separating hyperplane is $x = 0$.

  4. Show that the Lagrangian dual of a convex optimization problem provides a lower bound on the primal optimum, even without strong duality.

    Click for answer For any $\mathbf{x}$ feasible in the primal and any $\boldsymbol{\mu} \geq \mathbf{0}$, $\boldsymbol{\lambda}$: $g(\boldsymbol{\mu}, \boldsymbol{\lambda}) = \inf_{\mathbf{z}} \mathcal{L}(\mathbf{z}, \boldsymbol{\mu}, \boldsymbol{\lambda}) \leq \mathcal{L}(\mathbf{x}, \boldsymbol{\mu}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \sum \mu_i g_i(\mathbf{x}) + \sum \lambda_j h_j(\mathbf{x}) \leq f(\mathbf{x})$. The last inequality uses: $\mu_i \geq 0$, $g_i(\mathbf{x}) \leq 0 \implies \mu_i g_i(\mathbf{x}) \leq 0$, and $h_j(\mathbf{x}) = 0$. So $g(\boldsymbol{\mu}, \boldsymbol{\lambda}) \leq f(\mathbf{x})$ for any primal-feasible $\mathbf{x}$ and dual-feasible $(\boldsymbol{\mu}, \boldsymbol{\lambda})$. Taking supremum over dual variables: $d^* \leq p^*$. This is weak duality — always holds, no convexity required.

  5. Solve $\min_{x,y} e^x + e^y$ subject to $x + y = 1$. Verify second-order conditions.

    Click for answer Lagrangian: $\mathcal{L} = e^x + e^y + \lambda(x + y - 1)$. Stationarity: $\frac{\partial \mathcal{L}}{\partial x} = e^x + \lambda = 0 \implies \lambda = -e^x$. $\frac{\partial \mathcal{L}}{\partial y} = e^y + \lambda = 0 \implies \lambda = -e^y$. So $e^x = e^y \implies x = y$. With $x + y = 1$: $x = y = 1/2$. $\lambda = -e^{1/2} = -\sqrt{e}$. Second-order: bordered Hessian $H = \begin{pmatrix} e^x & 0 \\ 0 & e^y \end{pmatrix}$ at $(1/2, 1/2)$ has positive eigenvalues ($\sqrt{e} > 0$). Tangent space to constraint is $\mathbf{d} = (1, -1)$, and $\mathbf{d}^T H \mathbf{d} = e^x + e^y = 2\sqrt{e} > 0$. This confirms a minimum. $f_{\min} = 2e^{1/2} = 2\sqrt{e} \approx 3.297$.

Summary

Key takeaways:

Pitfalls

Next Steps

Next up: 15-09-convexity.md — convex sets, convex functions, Jensen's inequality, and why convexity guarantees that any local minimum is a global minimum (and why this matters for optimization).