Numerical Methods and Optimization

Constrained Optimization 371

max

μ≥0

d(μ)=d(μ

∗

). Since μ ≥ 0andg(x

∗

) ≤ 0, it follows that μ

T

g(x

∗

) ≤ 0for

any μ, hence, d(μ

∗

)=f(x

∗

)+μ

∗

T

g(x

∗

) ≤ f(x

∗

). 

The difference f(x

∗

) − d(μ

∗

) is called the duality gap.

The following result follows directly from Theorem 14.10.

Theorem 14.11 Apoint(x

∗

,μ

∗

) ∈ X × IR

p

+

is a saddle point of the

Lagrangian L(x, μ) if and only if x

∗

is a global minimum point of the

primal problem (P), μ

∗

is a global maximum point of the dual (D),and

the optimal values f(x

∗

) of (P) and d(μ

∗

) of (D) coincide.

14.3 Projected Gradient Methods

Consider a set-constrained problem

min

x∈X

f(x).

In methods for unconstrained problems, we used an iteration