Convex Optimization II: Duality and KKT Conditions

March 12, 2026

On this page

Image credit: Huang et al. (2022)

This article continues a three-part series on convex optimization. Across the series, we examine:

How to determine if a function is convex.
Properties and operations that preserve convexity.
Standard forms of convex optimization problems.
The Karush-Kuhn-Tucker (KKT) conditions: what they are and when they apply.
Mathematical derivations, with an SVM-like example and various convex loss functions.
A broad survey of commonly used convex functions in optimization.

Series Division:

Part 1: Fundamentals, Convexity Criteria, and Examples.
Part 2: Duality, KKT Conditions, and Advanced Applications.
Part 3: Convex Loss Functions.

Checking that an objective is convex does not yet tell us how to handle constraints. We introduce Lagrange multipliers, which assign a coefficient to each constraint, and use them to derive the dual problem. The Karush-Kuhn-Tucker (KKT) conditions then connect this dual problem to the original optimum. We work through a soft-margin support vector machine (SVM) and a score-maximization problem with a Kullback–Leibler (KL) divergence constraint.

Recap: The supporting inequality for a convex function

Part 1 established that a differentiable convex function on an open convex domain satisfies

f(y)\ge f(x)+\nabla f(x)^\top(y-x).

If its gradient vanishes at $x$ , no point in that domain has a smaller value. Below, we apply this reasoning to the Lagrangian and use feasibility and complementary slackness to relate it to the constrained objective.

3. Duality and Optimality Conditions in Convex Optimization.

The primal problem optimizes the original variables subject to constraints. The dual problem uses Lagrange multipliers to obtain bounds on the primal optimum. The KKT conditions identify when a feasible primal point and valid multipliers give the same value. The assumptions below explain when such multipliers exist.

3.1 Standard Form of a Convex Optimization Problem

A convex optimization problem typically takes the form:

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

where $f$ is convex, each $g_i$ is convex, and each $h_j$ is affine. Here we take these functions to be finite and differentiable on an open convex domain. Slater's condition requires a point in that domain satisfying all equalities and all inequalities strictly. For a convex problem with finite optimal value, this condition gives strong duality and attainment of the dual optimum. See Boyd and Vandenberghe's duality notes for the general domain formulation.

3.2 Karush-Kuhn-Tucker (KKT) Conditions

The KKT conditions are sufficient for global optimality in the differentiable convex setting above. A constraint qualification such as Slater's condition also makes them necessary at an attained optimum. Consider the problem

\begin{aligned} \min_x \quad & f(x) \\ \text{subject to} \quad & g_i(x) \le 0,\; i=1,\dots,m, \\ & h_j(x) = 0,\; j=1,\dots,p, \end{aligned}

Under Slater's condition, an optimal point $x^*$ has Lagrange multipliers $\lambda_i^*\ge0$ and $\nu_j^*\in\mathbb{R}$ satisfying:

Stationarity:

$\nabla f(x^*) + \sum_{i=1}^{m} \lambda_i^* \nabla g_i(x^*) + \sum_{j=1}^{p} \nu_j^* \nabla h_j(x^*) = 0.$
Primal Feasibility:

$g_i(x^*) \le 0, \quad h_j(x^*) = 0.$
Dual Feasibility:

$\lambda_i^* \ge 0 \quad \text{for all } i.$
Complementary Slackness:

$\lambda_i^* \, g_i(x^*) = 0 \quad \text{for all } i.$

Conversely, any point and multipliers satisfying these conditions solve the convex problem. Without a constraint qualification, an optimum need not have multipliers satisfying stationarity.

Application Case I: Soft-Margin SVM

We apply the KKT conditions to the soft-margin SVM. Let $x_i\in\mathbb{R}^d$ be features, $y_i\in\{-1,1\}$ the labels, and $C>0$ a penalty parameter. The variables are $w\in\mathbb{R}^d$ , $b\in\mathbb{R}$ , and slack variables $\xi_i$ . The primal formulation is

\min_{w,b,\xi} \quad \frac{1}{2}\|w\|^2 + C\sum_{i=1}^{n}\xi_i,

subject to margin and nonnegativity constraints:

y_i(w^\top x_i + b) \ge 1 - \xi_i, \quad \xi_i \ge 0 \quad \text{for } i = 1,\dots,n.

Let $\alpha_i \ge 0$ and $\beta_i \ge 0$ be the Lagrange multipliers. Form the Lagrangian:

\begin{aligned} L(w,b,\xi,\alpha,\beta) &= \frac{1}{2}\|w\|^2 + C\sum_{i=1}^{n}\xi_i \\ &\quad + \sum_{i=1}^n \alpha_i\bigl[1 - \xi_i - y_i(w^\top x_i + b)\bigr] - \sum_{i=1}^n \beta_i\,\xi_i. \end{aligned}

To derive the dual, we differentiate $L$ with respect to each primal variable and set the derivatives to zero:

Stationarity w.r.t $w$ :

$w - \sum_{i=1}^n \alpha_i y_i x_i = 0 \quad \Longrightarrow \quad w = \sum_{i=1}^n \alpha_i y_i x_i.$
Stationarity w.r.t $b$ :

$-\sum_{i=1}^n \alpha_i y_i = 0 \quad \Longrightarrow \quad \sum_{i=1}^n \alpha_i y_i = 0.$
Stationarity w.r.t $\xi_i$ :

$C - \alpha_i - \beta_i = 0 \quad \Longrightarrow \quad \beta_i = C - \alpha_i.$

Since $\beta_i \ge 0$ , we get $0 \le \alpha_i \le C$ .

We then substitute back into the Lagrangian, eliminating $(w, b, \xi)$ to obtain the dual problem:

\max_{\alpha} \quad \sum_{i=1}^n \alpha_i - \frac{1}{2}\sum_{i,j=1}^n \alpha_i \alpha_j y_i y_j \,(x_i^\top x_j),

subject to $0 \le \alpha_i \le C$ and $\sum_{i=1}^n \alpha_i y_i = 0$ . The stationarity equations remove the primal variables from the dual objective. The constraints on the multipliers remain: they are required for the Lagrangian infimum to be finite.

Application Case II: Score Maximization under a KL Constraint

Consider a fixed feature-label pair $(x,y)$ with $K\ge2$ classes and fixed class-score vectors $w_k$ . Define

s_k = w_k^\top x - w_y^\top x \quad\text{for}\; k = 1,\dots,K.

Here, $s_k$ is the shifted logit score for class $k$ . We introduce a distribution $\mathbf{p}=(p_1,\dots,p_K)$ and a radius $\rho\ge0$ . This example maximizes an average score over distributions in a Kullback–Leibler (KL) ball around the uniform distribution. Its dual involves log-sum-exp, which connects the calculation to softmax and cross-entropy; the constrained objective itself is not a supervised cross-entropy loss.

For each candidate $\mathbf p$ , the average is $\mathbb E_{I\sim\operatorname{Categorical}(\mathbf p)}[s_I]=\sum_kp_ks_k$ . The feature-label pair and all scores stay fixed. We optimize the distribution of this auxiliary class index, not a distribution of training datasets. The primal problem is

\max_{\mathbf{p}\in \mathbb{R}^K} \sum_{k=1}^K p_k\,s_k

subject to

$\sum_{k=1}^K p_k = 1,$
$\sum_{k=1}^K p_k \,\log\bigl(p_k\,K\bigr)\;\le\;\rho,$
$p_k \ge 0 \quad\forall k.$

In words:

We want to maximize a linear function of $\mathbf{p}$ .
$\mathbf{p}$ must lie in the probability simplex.
The constraint $\sum_k p_k\log(p_kK)\le\rho$ is a bound on KL divergence from the uniform distribution. We use $0\log0=0$ . A smaller radius requires the distribution to remain closer to uniform.

Proving Convexity

Although the objective is a maximization of a linear function, we can equivalently view it as

\min_{\mathbf{p}\in \mathcal{F}} \;\;-\sum_{k=1}^K p_k\,s_k,

where $\mathcal{F}$ is the feasible set:

Probability simplex: $p_k\ge 0,\, \sum_{k=1}^K p_k = 1.$
Entropic constraint: $\sum_{k=1}^K p_k \,\log(p_k K)\,\le\,\rho.$

The objective is linear, so its negative is convex. The probability simplex is convex, and $\sum_k p_k\log(p_kK)$ is convex: each term has second derivative $1/p_k>0$ in the interior and extends continuously to zero. Its sublevel set is therefore convex. Intersecting these two feasible sets gives a convex optimization problem.

Strict Feasibility and Slater’s Condition

To use strong duality, we typically invoke Slater’s condition. We need a strictly feasible point that satisfies

$\sum_{k=1}^K p_k = 1,$
$p_k > 0$ for all $k,$
$\sum_{k=1}^K p_k \,\log\bigl(p_k\,K\bigr) < \rho.$

A simple choice is the uniform distribution $p_k = 1/K.$ Then

\sum_{k=1}^K \frac{1}{K} \,\log\Bigl(\tfrac{1}{K}\cdot K\Bigr) = \sum_{k=1}^K \frac{1}{K}\,\log(1) = 0.

If $\rho>0$ , the uniform distribution is strictly feasible, so Slater's condition holds. When $\rho=0$ , KL divergence forces the uniform distribution; that boundary case can be solved directly.

Forming the Lagrangian

Let $\alpha$ be the Lagrange multiplier for $\sum_k p_k = 1,$ and let $\beta \ge 0$ be the multiplier for the entropic constraint $\sum_k p_k \log(p_k K)\le \rho.$ Define

\Phi(\mathbf{p}) = \sum_{k=1}^K p_k \,\log\bigl(p_k K\bigr) - \rho \le 0.

For this maximization problem, we subtract the inequality term. Keeping nonnegativity in the domain, the Lagrangian is

\mathcal{L}(\mathbf{p},\alpha,\beta) = \sum_{k=1}^K p_k\,s_k -\alpha \Bigl(\sum_{k=1}^K p_k -1\Bigr) -\beta \Bigl(\sum_{k=1}^K p_k \log(p_k K) - \rho\Bigr).

Rewriting,

\mathcal{L}(\mathbf{p},\alpha,\beta) = \sum_{k=1}^K p_k\,s_k -\alpha \sum_{k=1}^K p_k -\beta \sum_{k=1}^K p_k \log\bigl(p_k K\bigr) + \alpha + \beta \,\rho.

Solving for $\mathbf{p}$

The dual function $d(\alpha,\beta)$ is given by

d(\alpha,\beta) = \sup_{\mathbf{p}\ge 0} \;\mathcal{L}(\mathbf{p},\alpha,\beta).

The sum-to-one constraint now appears in the Lagrangian. We therefore do not impose it again when taking this supremum. For $\beta>0$ , the maximizing coordinates are positive, so we can differentiate with respect to $p_k$ and set the derivative to zero:

\frac{\partial \mathcal{L}}{\partial p_k} = s_k -\alpha -\beta\Bigl[\log\bigl(p_k K\bigr) + 1\Bigr] = 0.

Hence,

s_k - \alpha - \beta \log(p_k K) - \beta =0,

implying

\log\bigl(p_k K\bigr) = \frac{1}{\beta}\bigl(s_k - \alpha - \beta\bigr), \quad p_k = \frac{1}{K}\exp\!\Bigl(\tfrac{s_k - \alpha - \beta}{\beta}\Bigr).

Minimizing the dual function over $\alpha$ enforces $\sum_{k=1}^K p_k=1$ . This yields

\sum_{k=1}^K p_k = \sum_{k=1}^K \tfrac{1}{K} \exp\!\Bigl(\tfrac{s_k - \alpha - \beta}{\beta}\Bigr) =1.

Solving for $\alpha$ in terms of $\beta$ leads to

-\frac{\alpha+\beta}{\beta} = \log\Bigl(K\Bigr) - \log\Bigl(\sum_{k=1}^K \exp(s_k/\beta)\Bigr),

\alpha = -\beta \log\bigl(K\bigr) + \beta \log\Bigl(\sum_{k=1}^K e^{s_k/\beta}\Bigr) - \beta.

Substituting this value of $\alpha$ gives a normalized candidate distribution for each $\beta>0$ :

p_k(\beta) = \exp\!\Bigl(\frac{s_k}{\beta}\Bigr) \Big/ \Bigl[\sum_{\ell=1}^K \exp\!\bigl(\tfrac{s_\ell}{\beta}\bigr)\Bigr].

Constructing the Dual Problem

After eliminating $\alpha$ , the dual problem reduces to

\inf_{\beta\ge0}q(\beta),\qquad q(\beta)=\beta\rho+ \beta\log\!\left(\frac1K\sum_{k=1}^K e^{s_k/\beta}\right), \quad\beta>0.

At the boundary, define $q(0)=\max_k s_k$ by continuity from the right. Thus the dual objective is defined even when the softmax expression cannot be evaluated at zero. For $\rho>0$ , strong duality identifies the minimum dual value with the primal optimum.

At an optimum, complementary slackness gives

\beta^*\Bigl(\sum_{k=1}^K p_k^*\,\log\bigl(p_k^*\,K\bigr)-\rho\Bigr) =0.

In other words,

If the KL constraint is slack, then $\beta^*=0$ .
If $\beta^*>0$ , the KL constraint is active.
An active constraint alone does not imply a strictly positive multiplier.

For an interior optimum, differentiation gives $q'(\beta)=\rho-\sum_k p_k(\beta)\log(Kp_k(\beta))$ . Thus an interior minimizer chooses the softmax distribution whose KL divergence equals the prescribed radius.

Primal Solution from Optimal Dual Variables

If the optimal multiplier satisfies $\beta^*>0$ , the primal solution is

p_k^* = \frac{\exp\!\bigl(\tfrac{s_k}{\beta^*}\bigr)} {\sum_{\ell=1}^K \exp\!\bigl(\tfrac{s_\ell}{\beta^*}\bigr)}.

This is a softmax distribution with temperature $\beta^*$ , not its reciprocal. The boundary cases require separate treatment. If $\rho=0$ , the solution is uniform. Let $M=\{k:s_k=\max_j s_j\}$ and let $m$ be its size. If $\rho\ge\log(K/m)$ , the distribution uniform on $M$ is feasible and reaches the largest possible score, so it is optimal and $\beta^*=0$ is dual-optimal. For nonconstant scores and $0<\rho<\log(K/m)$ , the optimal multiplier is positive and the normalized softmax formula applies.

Only distributions supported on $M$ can attain the largest score. Among them, the uniform distribution has the smallest KL divergence from the uniform distribution on all $K$ classes, namely $\log(K/m)$ . The radius must therefore reach this threshold before an optimum can place all mass on maximizing classes.

Interpretation

Temperature: The multiplier controls concentration in the softmax distribution. If this problem is solved separately for each observation, its multiplier may differ across observations; that is a modeling construction, not by itself a guarantee about knowledge distillation.
Distributional robustness: The optimization considers the worst average score over a specified KL neighborhood of a reference distribution. It does not, on its own, establish robustness to mislabeled observations or outliers.
Entropy: Since the reference distribution is uniform, the KL constraint is equivalent to a lower bound on entropy. The reference distribution and radius determine which alternatives are allowed.

Conclusion:

The examples follow the same sequence: state the constraints, form the Lagrangian, derive stationarity conditions, and examine the multipliers. Part 3: Convex Loss Functions complements this discussion with a reference to the functions that appear in optimization objectives.

References & Further Reading

Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning.
Schölkopf, B., & Smola, A. (2001). Learning with Kernels. MIT Press.