Optimization - Linear, Nonlinear, and Variational Methods

Table of Contents

1. Linear Programming
2. Nonlinear Optimization
3. Convex Optimization
4. Constrained Optimization
5. Duality Theory
6. Calculus of Variations
7. Optimal Control

---

Linear Programming

Standard Form

Minimize: $c^T x$ Subject to: $Ax = b, x \geq 0$

where $x \in \mathbb{R}^n$

Feasible region: Polyhedron

Fundamental Theorem

If LP has optimal solution, it occurs at vertex (extreme point).

Simplex Method

1. Start at feasible vertex 2. Move to adjacent vertex with better objective 3. Continue until optimal

Pivot operation: Replace one basic variable

Duality

Primal: $\min\{c^T x : Ax = b, x \geq 0\}$

Dual: $\max\{b^T y : A^T y \leq c\}$

Weak duality: $c^T x \geq b^T y$for feasible $x, y$

Strong duality: If primal optimal exists, then $c^T x^* = b^T y^*$

Complementary slackness: $x_i > 0 \implies (A^T y)_i = c_i$

Interior Point Methods

Karmarkar’s algorithm: Move through interior of feasible region

Polynomial time for general LPs

Transportation Problem

Minimize shipping costs

Special structure allows simpler algorithms

---

Nonlinear Optimization

Unconstrained Problems

** $\min f(x)$** where $f: \mathbb{R}^n \to \mathbb{R}$

Necessary conditions: $\nabla f(x^*) = 0$

Sufficient conditions: $\nabla f(x^*) = 0$, $\nabla^2 f(x^*)$positive definite

Gradient Descent

** $x_{k+1} = x_k - \alpha_k \nabla f(x_k)$**

where $\alpha_k$is step size

Method: Choose search direction, line search for step

Newton’s Method

** $x_{k+1} = x_k - [\nabla^2f(x_k)]^{-1} \nabla f(x_k)$**

Convergence: Quadratic near minimum

Issue: Requires Hessian computation and inversion

Modified Newton: Use approximate Hessian (BFGS, L-BFGS)

Quasi-Newton Methods

Approximate $\nabla^2f$ using gradient information

BFGS update: ($B_{k+1}$from $B_k, s_k, y_k$)

$B_{k+1} = B_k + \frac{y_k y_k^T}{y_k^T s_k} - \frac{B_k s_k s_k^T B_k}{s_k^T B_k s_k}$

L-BFGS: Limited memory version

Line Search Methods

Goldstein conditions:

$f(x_k + \alpha p_k) \leq f(x_k) + c_1 \alpha \nabla f^T p_k$ $f(x_k + \alpha p_k) \geq f(x_k) + c_2 \alpha \nabla f^T p_k$

Armijo backtracking: Start with $\alpha = 1$, reduce until satisfied

---

Convex Optimization

Convex Sets

Set C is convex if for $x, y \in C$and $\theta \in [0,1]$: $\theta x + (1-\theta)y \in C$

Examples:

• Hyperplane: {x : a^T x = b}
• Halfspace: {x : a^T x \leq b}
• Norm balls
• Intersection of convex sets

Convex Functions

** $f$is convex if** for $x, y \in \text{domain } f, \theta \in [0,1]$: $f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y)$

Characterization (twice differentiable): $\nabla^2 f(x) \succeq 0$(positive semidefinite) for all $x$

Global Optima

For convex problem $\min f(x)$subject to $x \in C$:

Local minimum $\iff$global minimum

Examples

Least squares: $\min ||Ax - b||^2$ Quadratic programming: $\min x^T Qx + c^T x$($Q \succeq 0$) Lasso: $\min ||Ax - b||^2 + \lambda||x||_1$(convex)

---

Constrained Optimization

Karush-Kuhn-Tucker Conditions

Problem: $\min f(x)$s.t. $g_i(x) \leq 0, h_j(x) = 0$

KKT conditions (necessary):

1. Stationary: $\nabla f + \sum \lambda_i \nabla g_i + \sum \mu_j \nabla h_j = 0$
2. Primal feasibility: $g_i \leq 0, h_j = 0$
3. Dual feasibility: $\lambda_i \geq 0$
4. Complementary slackness: $\lambda_i g_i = 0$

If convex, KKT conditions sufficient for optimality.

Lagrange Multipliers

For equality constraints: $\nabla f = \sum \mu_j \nabla h_j$

Interpretation: Penalty for constraint violation

Penalty Methods

Unconstrained approximation:

$\min f(x) + \mu \sum [g_i(x)^+]^2 + \mu \sum [h_j(x)]^2$

where $[t]^+ = \max(0,t)$

Increase $\mu \to$solution approaches constrained optimum

Barrier Methods

Interior point: $\min f(x) - \mu \sum \log(-g_i(x))$

satisfies $g_i(x) < 0$

Decrease $\mu \to$approach boundary

Augmented Lagrangian

Method: Add penalty to Lagrangian

ADMM (Alternating Direction Method of Multipliers): For separable problems

---

Duality Theory

Lagrangian

** $L(x, \lambda, \mu) = f(x) + \sum \lambda_i g_i(x) + \sum \mu_j h_j(x)$**

Dual Function

** $g(\lambda, \mu) = \inf_x L(x, \lambda, \mu)$**

Concave in $(\lambda, \mu)$

Dual Problem

** $\max g(\lambda, \mu)$s.t. $\lambda \geq 0$**

Always convex (even if primal not)

Weak and Strong Duality

Weak: $d^* \leq p^*$(dual $\leq$primal)

Strong: If Slater conditions hold, $d^* = p^*$

Saddle Point

** $(x^*, \lambda^*, \mu^*)$** is saddle point if:

$L(x^*, \lambda, \mu) \geq L(x^*, \lambda^*, \mu^*) \geq L(x, \lambda^*, \mu^*)$

for all $x, \lambda \geq 0, \mu$

Saddle point $\iff$optimality

---

Calculus of Variations

Fundamental Problem

Find function $y$that minimizes:

$J[y] = \int_a^b F(x, y, y') dx$

subject to $y(a) = y_a, y(b) = y_b$

Euler-Lagrange Equation

Necessary condition:

$\frac{\partial F}{\partial y} - \frac{d}{dx}\frac{\partial F}{\partial y'} = 0$

Deduce: $d/dx (F - y' \partial F/\partial y') = \partial F/\partial x$

Examples

Brachistochrone: Minimum time path Geodesics: Shortest path on surface Isoperimetric problem: Maximum area for given perimeter

Hamilton’s Principle

Action: $S = \int L dt$where $L = T - V$

Minimize S $\implies$Lagrange’s equations

Noether’s Theorem

Continuous symmetry $\implies$conserved quantity

Energy conservation: Time translation symmetry Momentum conservation: Space translation symmetry

---

Optimal Control

Control Problem

State: $x(t)$ Control: $u(t)$

Minimize: $J = \int L(x, u, t) dt$

subject to $\dot{x} = f(x, u, t), x(0) = x_0, x(T)$free or fixed

Hamiltonian

** $H(x, u, p, t) = L(x, u, t) + p^T f(x, u, t)$**

where $p$is adjoint (costate) variable

Pontryagin Minimum Principle

Optimal control $u^*$minimizes $H$:

$u^* = \arg \min_{u \in U} H(x^*, u, p^*, t)$

State equation: $\dot{x} = \partial H/\partial p$ Adjoint equation: $\dot{p} = -\partial H/\partial x$ Transversality conditions: $p(T)$determined by end constraints

Linear Quadratic Regulator (LQR)

Minimize: $J = \int [x^T Q x + u^T R u] dt$

** $\dot{x} = Ax + Bu$** (linear dynamics)

Solution: $u^* = -R^{-1}B^T P x$

where $P$ from Riccati equation

Closed-form solution possible

---

Next: [[topology|Topology]] or [[abstract-algebra|Abstract Algebra]]

---

Last updated: Comprehensive optimization reference covering linear, nonlinear, and variational problems.