Convex optimization and duality

Definition A set $C \subseteq \mathbb{R}^n$ is convex if it contains the segment between any two of its points, that is, $tx + (1 - t)y \in C$ whenever $x, y \in C$ and $0 \le t \le 1$. A function $f$ from a convex set $C$ to $\mathbb{R}$ is convex if

for all $x, y \in C$ and $0 \le t \le 1$, and strictly convex if the inequality is strict whenever $x \ne y$ and $0 < t < 1$. A differentiable $f$ on $\mathbb{R}^n$ is convex if and only if it lies above each of its tangent planes,

for all $x$ and $y$, and a twice continuously differentiable $f$ on $\mathbb{R}^n$ is convex if and only if its Hessian is positive semidefinite at every point. So a quadratic $\tfrac12 w^{\top} \Sigma w + c^{\top} w$ with symmetric $\Sigma$ is convex exactly when $\Sigma$ is positive semidefinite.

In this lesson the standard problem is to minimize $f(x)$ over $x \in \mathbb{R}^n$ subject to $g_i(x) \le 0$ for $i = 1, \dots, m$ and $Ax = b$, where $A$ is a $p \times n$ matrix and $b \in \mathbb{R}^p$. It is a convex problem when $f$ and every $g_i$ are convex and finite on all of $\mathbb{R}^n$. Its feasible set is then convex, because each set $\{x : g_i(x) \le 0\}$ and the affine set $\{x : Ax = b\}$ are convex and an intersection of convex sets is convex. For a convex problem every local minimizer is a global minimizer. If $x^*$ were a local minimizer and a feasible $y$ had $f(y) < f(x^*)$, then every point $x^* + t(y - x^*)$ with $0 < t \le 1$ would be feasible with objective at most $(1 - t) f(x^*) + t f(y) < f(x^*)$, and these points come arbitrarily close to $x^*$ as $t \to 0$. Strict convexity of $f$ allows at most one minimizer. Neither property guarantees that a minimizer exists, which needs a further argument, for example a continuous objective on a nonempty compact feasible set.

Definition For the standard problem, attach a multiplier $\lambda_i$ to each inequality $g_i(x) \le 0$ and a vector $\nu \in \mathbb{R}^p$ to the equalities $Ax = b$. The Lagrangian is

with $\lambda = (\lambda_1, \dots, \lambda_m) \ge 0$ componentwise and $\nu$ unrestricted in sign. The sign restriction belongs to the direction of the inequalities, so a constraint $h(x) \ge 0$ must first be written as $-h(x) \le 0$. In this lesson the letter $q$ denotes the dual function,

which may equal $-\infty$. For each fixed $x$ the Lagrangian is affine in $(\lambda, \nu)$, so the dual function, an infimum of affine functions, is concave whether or not the standard problem is convex.

Definition The dual problem is to maximize $q(\lambda, \nu)$ over $\lambda \ge 0$ and $\nu \in \mathbb{R}^p$. Let $p^*$ be the optimal primal value, the infimum of $f$ over the feasible set, with $p^* = +\infty$ when no point is feasible, and let $d^*$ be the optimal dual value, the supremum of $q$ over $\lambda \ge 0$ and all $\nu$. Weak duality is the inequality $d^* \le p^*$. For any feasible $\tilde x$, any $\lambda \ge 0$ and any $\nu$,

The first step holds because an infimum is at most each of its values, the equality because $A \tilde x = b$, and the last step because $\lambda_i \ge 0$ and $g_i(\tilde x) \le 0$. Taking the supremum on the left and the infimum on the right gives $d^* \le p^*$. The argument needs no convexity, no differentiability and no attained minimum. The difference $p^* - d^*$, when it is defined, is the duality gap, and it is never negative.

Definition Consider the standard problem with $f$ and every $g_i$ convex and differentiable on all of $\mathbb{R}^n$ and affine equality constraints $Ax = b$. A point $x^*$ with multipliers $\lambda^*$ and $\nu^*$ satisfies the Karush-Kuhn-Tucker (KKT) conditions if it has primal feasibility, dual feasibility and complementary slackness,

for $i = 1, \dots, m$, together with stationarity,

Under these hypotheses the conditions are sufficient. If $(x^*, \lambda^*, \nu^*)$ satisfies them, then $x^*$ is a global minimizer, $(\lambda^*, \nu^*)$ is optimal for the dual problem, and $p^* = d^* = f(x^*)$. Because $\lambda^* \ge 0$, the function $x \mapsto L(x, \lambda^*, \nu^*)$ is convex and differentiable, stationarity says its gradient vanishes at $x^*$, and the tangent plane inequality makes $x^*$ a global minimizer of it. Complementary slackness and feasibility remove the constraint terms, so

By weak duality every feasible $x$ has $f(x) \ge q(\lambda^*, \nu^*) = f(x^*)$, and every $\lambda \ge 0$ and $\nu$ have $q(\lambda, \nu) \le p^* \le f(x^*)$. No constraint qualification is needed in this direction. Complementary slackness forces $\lambda_i^* = 0$ for every inactive constraint, one with $g_i(x^*) < 0$, while an active constraint, one with $g_i(x^*) = 0$, may also have a zero multiplier. Without convexity the same four conditions can hold at a maximum or a saddle point.

Definition Strong duality holds when $d^* = p^*$. Equal values do not by themselves say that either optimum is attained. A constraint qualification is a condition on the constraints, not on the objective, that guarantees strong duality or the existence of KKT multipliers at a minimizer. For a convex standard problem, Slater’s condition asks for a strictly feasible point, an $\bar x$ with $A \bar x = b$ and $g_i(\bar x) < 0$ for every $i$. A refined version lets affine inequality constraints hold with equality at $\bar x$. The following result is stated here without proof. If the standard problem is convex, Slater’s condition holds and $p^*$ is finite, then $d^* = p^*$ and the dual problem has an optimal solution $(\lambda^*, \nu^*)$. If in addition a primal minimizer $x^*$ exists and $f$ and the $g_i$ are differentiable, then $(x^*, \lambda^*, \nu^*)$ satisfies the KKT conditions. That last step is elementary, since strong duality with both optima attained gives

so both inequalities are equalities. The nonpositive terms $\lambda_i^* g_i(x^*)$ then add to zero, which is complementary slackness, and $x^*$ minimizes $L(\cdot, \lambda^*, \nu^*)$ over $\mathbb{R}^n$, so its gradient there is zero. Hence, for a differentiable convex problem that satisfies Slater’s condition, a feasible point is optimal if and only if some multipliers satisfy the KKT conditions with it. Slater’s condition is sufficient for strong duality, not necessary, and it does not guarantee that a primal minimizer exists.

Definition An inequality constraint $g_i(x) \le 0$ is active at a feasible point $x$ when $g_i(x) = 0$, and inactive, or slack, when $g_i(x) < 0$. In this lesson a constraint is binding at the optimum when it is active there and relaxing it alone lowers the optimal value. Many texts use binding as a synonym for active, and the two differ only for an active constraint whose relaxation changes nothing. To measure relaxation, replace $g_i(x) \le 0$ by $g_i(x) \le u_i$ and let $p^*(u)$ be the optimal value of the perturbed problem, so $u_i > 0$ relaxes constraint $i$ and $u_i < 0$ tightens it. If strong duality holds at $u = 0$ with a dual optimum $(\lambda^*, \nu^*)$, then for every $u$

Indeed, any $x$ with $g_i(x) \le u_i$ for all $i$ and $Ax = b$ has $f(x) \ge L(x, \lambda^*, \nu^*) - \lambda^{*\top} u$, and the Lagrangian is at least $q(\lambda^*, \nu^*) = p^*(0)$. So relaxing constraint $i$ by $u_i > 0$ lowers the optimal value by at most $\lambda_i^* u_i$, tightening it by $\lvert u_i \rvert$ raises the value by at least $\lambda_i^* \lvert u_i \rvert$, and a constraint with $\lambda_i^* = 0$ is not binding. If moreover $p^*$ is differentiable at $u = 0$, then

and a constraint with $\lambda_i^* > 0$ is binding, its relaxation lowering the value at the rate $\lambda_i^*$. Without differentiability a positive multiplier does not settle the question. If one constraint is written twice, the multipliers of the two copies need only add up to the multiplier of the single constraint, so one dual optimum can give a copy a positive multiplier although relaxing that copy alone changes nothing.