Constrained Optimality and Dual Certificates

An optimum on a constraint boundary can have a nonzero gradient. One way to prove optimality is to find a lower bound that applies to every feasible point, then show that a candidate attains it. The Lagrange multipliers producing that bound form a dual certificate. The underlying lower-bound argument and optimality conditions are developed in Boyd and Vandenberghe, Chapter 5.

The convex optimization overview introduces convexity and KKT; gradient and multidimensional optimization explains gradients and Hessians. For background on choosing variables, an objective, and a feasible set, see optimization modeling. Here those ideas meet in one calculation.

Objective and feasible set

For real variables $x,y$, consider the primal problem:

$$\begin{aligned} \text{minimize}\quad & f(x,y)=\frac12\bigl((x-2)^2+(y-1)^2\bigr) \\ \text{subject to}\quad & c_1(x,y)=x+y-2\le0, \\ & c_2(x,y)=-x\le0, \\ & c_3(x,y)=-y\le0. \end{aligned}$$

The feasible set $C=\{(x,y):x\ge0,\ y\ge0,\ x+y\le2\}$ is a closed triangle. The objective is half the squared distance to $(2,1)$. Since $C$ is nonempty and compact and the objective is continuous, a minimum exists. The Hessian is the identity matrix, so the objective is strictly convex and its minimizer is unique.

This fits the form used in CVXPY's quadratic-program example: $\frac12z^TPz+q^Tz$, with $Gz\le h$ and positive-semidefinite $P$. Here $z=(x,y)^T$, $P=I_2$, $q=(-2,-1)^T$, and

$$G=\begin{pmatrix}1&1\\-1&0\\0&-1\end{pmatrix},\qquad h=\begin{pmatrix}2\\0\\0\end{pmatrix},\qquad f(z)=\frac12z^Tz+q^Tz+\frac52.$$

The constant $5/2$ does not change the minimizer. Keep it to recover the values of $f$ and $g$ defined here; subtracting it from both leaves the primal–dual gap unchanged.

Find a candidate

The unconstrained minimizer $(2,1)$ violates $x+y\le2$. Try the boundary $x+y=2$ by substituting $y=2-x$:

$$f(x,2-x)=\frac12\bigl((x-2)^2+(1-x)^2\bigr) =\left(x-\frac32\right)^2+\frac14.$$

The minimum along this edge is therefore

$$(x_*,y_*)=\left(\frac32,\frac12\right),\qquad f(x_*,y_*)=\frac14.$$

Both coordinates are positive, so the candidate lies on the edge. Minimizing on one edge alone does not rule out better points elsewhere in the triangle. The dual bound below will complete the global proof.

A constraint is active at a point when it holds with equality. Here $c_1=0$, whereas $c_2=-3/2$ and $c_3=-1/2$: only the constraint on the sum is active. The objective gradient is $\nabla f=(-1/2,-1/2)$. Moving along the negative gradient would increase $x+y$ and leave the feasible set.

Lagrangian and dual bound

Using the convention $c_i\le0$, assign nonnegative multipliers $\lambda,\mu,\nu$ to the three constraints. Following Boyd and Vandenberghe, §§5.1.1–5.1.3, form

$$L(x,y,\lambda,\mu,\nu) =f(x,y)+\lambda(x+y-2)-\mu x-\nu y.$$

For fixed multipliers, the dual function is the infimum of $L$ over the variable domain:

$$g(\lambda,\mu,\nu)=\inf_{(x,y)\in\mathbb R^2}L(x,y,\lambda,\mu,\nu).$$

Take this infimum over all of $\mathbb R^2$. The three inequalities are already incorporated into $L$; restricting this calculation to the triangle would change the dual function.

The Hessian of $L$ with respect to $(x,y)$ is still $I_2$. Setting its partial derivatives to zero thus finds its unique global minimizer:

$$\partial_x L=x-2+\lambda-\mu=0,\qquad \partial_y L=y-1+\lambda-\nu=0,$$

giving $x_L=2-\lambda+\mu$ and $y_L=1-\lambda+\nu$. Completing the square yields

$$\begin{aligned} L&=\frac12\bigl((x-x_L)^2+(y-y_L)^2\bigr)+g(\lambda,\mu,\nu),\\ g(\lambda,\mu,\nu) &=\lambda-2\mu-\nu-\frac12\bigl((\lambda-\mu)^2+(\lambda-\nu)^2\bigr). \end{aligned}$$

The dual problem maximizes $g$ subject to $\lambda,\mu,\nu\ge0$. Here $g$ is finite for all finite multipliers. For any feasible $(x,y)$ and nonnegative multipliers,

$$g(\lambda,\mu,\nu)\le L(x,y,\lambda,\mu,\nu)\le f(x,y).$$

The second inequality holds because each added term is a nonnegative multiplier times a nonpositive constraint value. Write $p_*$ for the primal optimal value and $d_*=\sup_{\lambda,\mu,\nu\ge0}g$ for the dual optimal value. Then $d_*\le p_*$, known as weak duality. This argument does not require convexity.

Calculate the multipliers and check all four KKT conditions

Complementary slackness requires each multiplier times its constraint value to vanish. Since $x_*,y_*>0$, we get $\mu_*=\nu_*=0$. Substitution into the stationarity equations gives

$$-\frac12+\lambda_*=0 \quad\Longrightarrow\quad (\lambda_*,\mu_*,\nu_*)=\left(\frac12,0,0\right).$$

The four KKT conditions from §5.5.3 of the textbook now have explicit checks:

Condition	Calculation	Result
Primal feasibility	$(c_1,c_2,c_3)=(0,-3/2,-1/2)$	All nonpositive
Multiplier nonnegativity	$(\lambda_*,\mu_*,\nu_*)=(1/2,0,0)$	All multipliers nonnegative
Stationarity	$\nabla_{x,y}L=(-1/2+1/2,-1/2+1/2)$	$(0,0)$
Complementary slackness	$(\lambda_*c_1,\mu_*c_2,\nu_*c_3)=(0,0,0)$	All zero

A finite dual lower bound additionally requires $g>-\infty$. This is automatic for this quadratic program, but does not follow from the multiplier signs alone in a general problem.

A positive multiplier requires its constraint to be active; an inactive constraint requires a zero multiplier. An active constraint can still have a zero multiplier. For example, change the bound in this problem to $3$: the unconstrained minimizer $(2,1)$ lies on $x+y=3$, with every multiplier zero.

For a differentiable convex problem, with convex objective and inequality functions and affine equalities, satisfying KKT certifies global optimality. Here the certificate also gives a numerical equality:

$$g\left(\frac12,0,0\right)=\frac12-\left(\frac12\right)^2=\frac14 =f\left(\frac32,\frac12\right).$$

Every feasible point has objective at least $1/4$, and the candidate attains it. Hence $p_*=d_*=1/4$. The squared terms give the same conclusion directly:

$$f(x,y)-\frac14 =\frac12\left(\left(x-\frac32\right)^2+\left(y-\frac12\right)^2\right) +\frac12(2-x-y)\ge0\qquad ((x,y)\in C).$$

Equality holds only at $(3/2,1/2)$. This proves optimality and uniqueness without searching through every feasible point.

Measure a candidate's error with the gap

For a primal feasible point and dual feasible multipliers, the primal–dual gap is $f(x,y)-g(\lambda,\mu,\nu)$. It bounds the candidate's suboptimality:

$$0\le f(x,y)-p_*\le f(x,y)-g(\lambda,\mu,\nu).$$

Each row below is a feasible primal–dual pair, but the first two use multipliers that are not dual optimal.

$(x,y)$	$(\lambda,\mu,\nu)$	$f$	$g$	$f-g$
$(1,1)$	$(0,0,0)$	$1/2$	$0$	$1/2$
$(1,1)$	$(1/4,0,0)$	$1/2$	$3/16$	$5/16$
$(3/2,1/2)$	$(1/2,0,0)$	$1/4$	$1/4$	$0$

The second row gives $3/16\le p_*\le1/2$ and a suboptimality bound of $5/16=0.3125$. The candidate's actual suboptimality is $1/2-1/4=1/4$. A positive gap for a candidate pair does not establish a positive gap between the optimal values: here the optimal duality gap $p_*-d_*$ is zero.

What regularity and convexity each guarantee

A convex optimum can lack KKT multipliers

Slater's condition, §5.2.3, requires a convex problem to have a point in the relative interior of its common domain satisfying the equalities and all inequalities strictly. It guarantees strong duality and, for a finite optimal value, attainment of the dual optimum by finite multipliers. With differentiability, KKT becomes necessary and sufficient for optimality. The textbook's refined version allows affine inequalities to hold without strict inequality.

The point $(1/2,1/2)$ satisfies all three inequalities strictly in our quadratic program, so Slater holds. It guarantees that an optimal certificate exists. Sufficiency of an already established KKT certificate in a convex problem does not itself require Slater.

Now consider a different convex problem:

$$\min_{x\in\mathbb R}x\quad\text{subject to}\quad x^2\le0.$$

Its only feasible point is $x_*=0$, with $p_*=0$. No point satisfies $x^2<0$, so Slater fails. The stationarity equation for $L=x+\lambda x^2$ is $1+2\lambda x=0$. No finite multiplier can satisfy it at $x_*=0$.

For $\lambda>0$, the minimizer of $L$ is $-1/(2\lambda)$, giving $g(\lambda)=-1/(4\lambda)$; at $\lambda=0$, $g(0)=-\infty$. Thus $d_*=\sup_{\lambda\ge0}g(\lambda)=0=p_*$, but no finite multiplier attains the supremum. Multiplier existence and KKT necessity fail in this example; strong duality still holds.

A nonconvex KKT point can be a maximum

Consider

$$\min_{x\in\mathbb R}-x^2\quad\text{subject to}\quad x-1\le0,\quad -x-1\le0.$$

The feasible set is $[-1,1]$, and the objective is not convex. At $x=0$ with both multipliers zero, primal feasibility, nonnegative multipliers, stationarity, and complementary slackness all hold. Yet $f(0)=0$ and $f(-1)=f(1)=-1$: this KKT point is the strict maximum over the feasible set.

The stationary point of $L=-x^2$ is not its global minimizer; $\inf_{x\in\mathbb R}L=-\infty$. In fact, any finite multipliers only add affine terms, leaving a downward-opening quadratic, so $d_*=-\infty$ in this problem. Weak duality survives but gives no finite lower bound. Although $x=0$ satisfies both constraints strictly, Slater's theorem for convex problems cannot be applied to this nonconvex objective.

Recompute with Python

This trace uses only rational arithmetic from Python's standard library. It checks the derived point and multipliers and recomputes the gaps and counterexamples. The global infimum needed for the certificate follows from the completed-square derivation above.

from fractions import Fraction as F


def objective(x, y):
    return F(1, 2) * ((x - 2)**2 + (y - 1)**2)


def dual(lam, mu, nu):
    return lam - 2*mu - nu - F(1, 2)*((lam-mu)**2 + (lam-nu)**2)


def vector(values):
    return '(' + ', '.join(map(str, values)) + ')'


x, y = F(3, 2), F(1, 2)
lam, mu, nu = F(1, 2), F(0), F(0)
constraints = (x+y-2, -x, -y)
multipliers = (lam, mu, nu)
stationarity = (x-2+lam-mu, y-1+lam-nu)
kkt = (
    all(c <= 0 for c in constraints),
    all(m >= 0 for m in multipliers),
    all(s == 0 for s in stationarity),
    all(m*c == 0 for m, c in zip(multipliers, constraints)),
)
assert all(kkt)
print('x=' + vector((x, y)) + ', multipliers=' + vector(multipliers))
print('constraints=' + vector(constraints))
print('stationarity=' + vector(stationarity))
print('KKT=' + vector(kkt))
for label, a, b, l in [('candidate', F(1), F(1), F(1, 4)),
                     ('optimum', x, y, lam)]:
    p, d = objective(a, b), dual(l, F(0), F(0))
    print(f'{label}: f={p}, g={d}, gap={p-d}')
for l in (F(1), F(10), F(100)):
    z = -1/(2*l)
    g = z + l*z*z
    assert g == -1/(4*l)
    print(f'degenerate: lambda={l}, x_min_L={z}, g={g}')
z = F(0)
nonconvex_constraints = (z-1, -z-1)
nonconvex_multipliers = (F(0), F(0))
nonconvex_kkt = (
    all(c <= 0 for c in nonconvex_constraints),
    all(m >= 0 for m in nonconvex_multipliers),
    -2*z + nonconvex_multipliers[0] - nonconvex_multipliers[1] == 0,
    all(m*c == 0 for m, c in zip(nonconvex_multipliers, nonconvex_constraints)),
)
print('nonconvex: KKT=' + vector(nonconvex_kkt)
      + f', f(0)={-z*z}, f(-1)=f(1)={-F(1)**2}')

Actual output:

x=(3/2, 1/2), multipliers=(1/2, 0, 0)
constraints=(0, -3/2, -1/2)
stationarity=(0, 0)
KKT=(True, True, True, True)
candidate: f=1/2, g=3/16, gap=5/16
optimum: f=1/4, g=1/4, gap=0
degenerate: lambda=1, x_min_L=-1/2, g=-1/4
degenerate: lambda=10, x_min_L=-1/20, g=-1/40
degenerate: lambda=100, x_min_L=-1/200, g=-1/400
nonconvex: KKT=(True, True, True, True), f(0)=0, f(-1)=f(1)=-1

For larger quadratic programs, the CVXPY example retrieves multipliers through a constraint object's dual_value. Keep the constraint order and sign convention consistent, then check feasibility, stationarity residuals, complementary products, and the lower bound from the actual dual function. A small stationarity residual alone would not exclude the nonconvex maximum above.

My reading · Opened notes are remembered in this browser.