KKT and interior-point methods: when constraints enter the picture

From Lagrangians and KKT conditions to barrier methods and the Convex QP Solver.

Optimization & MetaheuristicsAdvanced

Learning goal

Write KKT conditions for a constrained problem, interpret multipliers, and explain the main idea of interior-point methods.

Prerequisites

Multivariable derivatives
Basic linear algebra
Optimization basics

Constrained optimization

Constrained problem

min_{x} f (x) s.t. g_{i} (x) \leq 0, h_{j} (x) = 0

With constraints, ∇f=0 alone is not enough. The feasible region becomes part of the optimality conditions.

The Lagrangian

Lagrangian

L (x, λ, ν) = f (x) + \sum_{i}^{} λ_{i} g_{i} (x) + \sum_{j}^{} ν_{j} h_{j} (x)

The multipliers describe how the constraints interact with the objective and become part of the KKT system under suitable assumptions.

KKT conditions

Primal feasibility: the original constraints hold.
Dual feasibility: inequality multipliers are non-negative.
Stationarity: the Lagrangian gradient with respect to x is zero.
Complementary slackness: λᵢgᵢ(x)=0.

KKT summary

\nabla_{x} L = 0, g_{i} (x) \leq 0, λ_{i} \geq 0, λ_{i} g_{i} (x) = 0

A one-dimensional example

Example

\min_x x^2\quad\text{s.t.}\quad x\ge1

The unconstrained minimum is x=0, but the constraint excludes it. The constrained optimum is x*=1 on the boundary.

Barrier and interior-point idea

Barrier formulation

min_{x} f (x) - μ \sum_{i}^{} \log (- g_{i} (x))

For μ>0, approaching an inequality boundary increases the barrier cost. Reducing μ gradually brings the barrier problem toward the original constrained problem.

Connection to the Convex QP Solver

The Convex QP Solver uses primal-dual interior-point and a Mehrotra predictor-corrector method. This is where KKT becomes a numerical system inside actual solver code.

Exercises

Write KKT conditions for minimize x² subject to x≥2.
Identify the active constraint.
Explain stationarity versus feasibility with an example.

Related project

Convex Quadratic Programming Solver

KKT, numerical diagnostics, and interior-point methods are part of the solver core.

Open source

Working on constrained optimization?

We can move from the model and constraints to the numerical method and implementation.

Start a conversation