
Quadratic Programming 269
f(x
∗
) ≤ f(x
∗
+ λ
∗
(y −x
∗
)),
then since f(x) is a convex function over S, we have
f(x
∗
) ≤ f(x
∗
+ λ
∗
(y −x
∗
)) = f(λ
∗
y + (1 − λ
∗
)x
∗
)
≤ λ
∗
f(y) + (1 − λ
∗
)f(x
∗
),
then
f(x
∗
) ≤ λ
∗
f(y) + (1 − λ
∗
)f(x
∗
),
or equivalently
f(x
∗
) ≤ f(y).
Therefore x
∗
is a global minimum. If f(x) is a strictly convex function,
then the inequalities above hold strictly for all y 6= x
∗
.
7.5.4 Equality-Constrained Quadratic Programs
Next we consider equality-constrained quadratic programs (EQP) of the form
minimize f(x) =
1
2
x
T
Qx + c
T
x
subject to Ax = b.
The key idea is to turn an EQP into an unconstrained problem by defining
a new function called the Lagrangian. This is accomplished ...