1. Projected Gradient Descent on Convex Sets

For constrained problem $\min_{\mathbf{x} \in \mathcal{C}} f(\mathbf{x})$ where $\mathcal{C} \subset \mathbb{R}^n$ is closed and convex, Projected Gradient Descent (PGD) iterates:

$$\mathbf{x}_{k+1} = \Pi_{\mathcal{C}}\left( \mathbf{x}_k - \alpha_k \nabla f(\mathbf{x}_k) \right)$$

where $\Pi_{\mathcal{C}}(\mathbf{y}) = \arg\min_{\mathbf{x} \in \mathcal{C}} \|\mathbf{x} - \mathbf{y}\|_2$ is the Euclidean projection operator onto $\mathcal{C}$.

2. Augmented Lagrangian Method (Method of Multipliers)

To solve equality-constrained problems $\min f(\mathbf{x}) \text{ s.t. } h_i(\mathbf{x}) = 0$, standard penalty methods ($\min f(\mathbf{x}) + \frac{\rho}{2}\|h(\mathbf{x})\|_2^2$) require $\rho \to \infty$, causing ill-conditioned Hessians.

The Augmented Lagrangian Method (ALM) combines Lagrangian duality with quadratic penalty terms:

$$\mathcal{L}_{\rho}(\mathbf{x}, \boldsymbol{\nu}) = f(\mathbf{x}) + \boldsymbol{\nu}^T \mathbf{h}(\mathbf{x}) + \frac{\rho}{2} \|\mathbf{h}(\mathbf{x})\|_2^2$$

Primal-Dual ALM Updates

  1. Primal Minimization: $\mathbf{x}_{k+1} = \arg\min_{\mathbf{x}} \mathcal{L}_{\rho_k}(\mathbf{x}, \boldsymbol{\nu}_k)$.
  2. Dual Multiplier Ascent: $\boldsymbol{\nu}_{k+1} = \boldsymbol{\nu}_k + \rho_k \mathbf{h}(\mathbf{x}_{k+1})$.

3. Primal-Dual Interior-Point Logarithmic Barrier Methods

For inequality constraints $f_i(\mathbf{x}) \le 0$, Interior-Point Methods replace hard boundary walls with smooth logarithmic barrier functions:

$$\Phi_t(\mathbf{x}) = t f_0(\mathbf{x}) - \sum_{i=1}^m \log\left( -f_i(\mathbf{x}) \right)$$

As barrier parameter $t \to \infty$, the central path $\mathbf{x}^*(t) = \arg\min_{\mathbf{x}} \Phi_t(\mathbf{x})$ converges uniformly to the exact constrained optimal point $\mathbf{x}^*$ with duality gap $\le \frac{m}{t}$.

4. Python Verification: Logarithmic Barrier Central Path Convergence

import numpy as np
from scipy.optimize import minimize

def verify_log_barrier_central_path():
    """Demonstrates central path convergence of log barrier method on constrained quadratic."""
    # min x^2 + y^2 s.t. x + y >= 2 -> exact solution (1, 1), f* = 2.0
    def barrier_obj(z, t):
        slack = z[0] + z[1] - 2.0
        if slack <= 0:
            return float('inf')
        return t * (z[0]**2 + z[1]**2) - np.log(slack)

    current_z = np.array([2.0, 2.0])  # Strictly feasible initial point
    t_values = [1.0, 10.0, 100.0, 1000.0, 10000.0]
    
    for t in t_values:
        res = minimize(barrier_obj, current_z, args=(t,), method='BFGS')
        current_z = res.x
        duality_gap_bound = 1.0 / t
        print(f"Barrier t={t:7.1f} | Point: {np.round(current_z, 5)} | Duality Gap <= {duality_gap_bound:.1e}")

if __name__ == "__main__":
    verify_log_barrier_central_path()