Understanding Duality in Convex Optimization and the Interior‑Point Method

Introduction

In convex optimization, duality provides a powerful way to transform a constrained problem into a different problem that is often easier to analyze or solve. This article follows the video transcript step‑by‑step, illustrating the concepts with a ship‑steering example, introducing penalty functions, deriving the dual (Lagrangian) formulation, presenting the Karush‑Kuhn‑Tucker (KKT) conditions, and finally explaining the interior‑point method.

A Motivating Example: Steering a Ship

• Decision variable: (x\in\mathbb{R}^2) – the ship’s position.
• Objective: maximize the opposite of the rain direction (c=(1,1)), i.e. minimize (c^T x = x_1+x_2).
• Constraint: stay inside the safe unit disk (|x|_2\le 1). The problem is convex because the objective is linear (hence convex) and the feasible set is a convex disk.

From Constraints to Penalties

1. Zero‑Infinity penalty: (p(y)=0) if (y\le0), (+\infty) otherwise. Adding (p(g(x))) to the objective forces feasibility without changing the optimal value, but creates a discontinuous objective.
2. Linear penalty approximation: (u\,y) with (u\ge0). This yields a smooth but biased objective; the bias depends on (u).
3. Maximum over all (u) recovers the original zero‑infinity penalty, leading to a min‑max (or two‑player) formulation where the (x)-player minimizes and the (u)-player maximizes.

The Dual Problem

• By moving each constraint into the objective with a multiplier ((u_i) for inequalities, (v_i) for equalities) and taking the maximum over the multipliers, we obtain the Lagrangian: [L(x,\lambda)=f(x)+\sum_i\lambda_i g_i(x)]
• Swapping the order of min and max yields the dual problem (the Lagrangian dual). It has one variable per primal constraint, interpreted as the price of violating that constraint.
• Key properties:
• The dual provides a lower bound on the primal optimum.
• Under mild conditions (e.g., Slater’s condition) strong duality holds, so the primal and dual optimal values coincide.

KKT Conditions

For a convex problem with differentiable functions, any optimal pair ((x^,\lambda^)) must satisfy: 1. Primal feasibility: (g_i(x^)\le0) (and equality constraints hold). 2. Dual feasibility: (\lambda_i^\ge0) for inequality constraints. 3. Complementary slackness: (\lambda_i^ g_i(x^) = 0). 4. Stationarity: (\nabla f(x^) + \sum_i \lambda_i^ \nabla g_i(x^*) = 0). Geometrically, stationarity means the gradient of the objective is a linear combination of the active constraint gradients – the feasible descent direction vanishes.

From KKT to Algorithms: Interior‑Point Method

Directly solving the KKT equations can be hard. The interior‑point approach perturbs the complementary‑slackness condition: - Replace (\lambda_i g_i(x)=0) with (\lambda_i g_i(x) = -t), where (t>0) is a barrier parameter. - This yields (\lambda_i = -t / g_i(x)) and transforms the stationarity condition into the gradient of a log‑barrier function: [\nabla f(x) - t \sum_i \frac{\nabla g_i(x)}{g_i(x)} = 0] - The resulting unconstrained problem can be tackled with Newton’s method. - Central path: As (t) decreases to zero, the iterates trace a path inside the feasible region from the analytic center (solution for large (t)) to the optimal primal point. - By gradually reducing (t) (e.g., (t_{k+1}=0.9\,t_k)) and warm‑starting Newton’s method, convergence is fast and numerically stable.

Why Duality and Interior‑Point Methods Matter

• They turn a constrained convex problem into a sequence of easier unconstrained problems.
• The dual gives insight into the price of constraints, useful for sensitivity analysis.
• Interior‑point algorithms are polynomial‑time and form the backbone of many modern solvers (e.g., MOSEK, Gurobi, CVX).

Recap

• Duality converts constraints into penalty terms, leading to a dual (maximization) problem.
• KKT conditions characterize optimality for convex problems.
• Interior‑point methods solve a perturbed KKT system using log‑barriers and a decreasing barrier parameter, following the central path to the optimum.

Further Reading

For a deeper dive, see Convex Optimization by Boyd and Vandenberghe, freely available as a PDF online.

Duality lets us replace hard constraints with easier-to‑handle penalty terms, and the KKT conditions together with interior‑point methods provide a systematic, efficient way to solve convex optimization problems by following the central path from the interior to the optimum.