10 Constraints
Previous chapters have focused on unconstrained problems where the domain ofeach design variable is the space of real numbers. Many problems are constrained,
which forces design points to satisfy certain conditions. This chapter presents avariety of approaches for transforming problems with constraints into problems
without constraints, thereby permitting the use of the optimization algorithms
we have already discussed. Analytical methods are also discussed, including theconcepts of duality and the necessary conditions for optimality under constrained
optimization.

10.1 Constrained Optimization
Recall the core optimization problem equation (1.1):
minimizexf (x)subject to x ∈ X(10.1)In unconstrained problems, the feasible set X is R n . In constrained problems, thefeasible set is some subset thereof.
Some constraints are simply upper or lower bounds on the design variables,
as we have seen in bracketed line search, in which x must lie between a and b.
A bracketing constraint x ∈ [ a, b] can be replaced by two inequality constraints:a ≤ x and x ≤ b as shown in figure 10.1. In multivariate problems, bracketing the
input variables forces them to lie within a hyperrectangle as shown in figure 10.2.

168

c ha p te r 10 . c on stra i n ts

Figure 10.1. A simple optimization
problem constrained by upper andlower bounds.

f (x)minimizef (x)subject tox ∈ [ a, b]xx
aConstraints arise naturally when formulating real problems. A hedge fundmanager cannot sell more stock than they have, an airplane cannot have wings
with zero thickness, and the number of hours you spend per week on yourhomework cannot exceed 168. We include constraints in such problems to preventthe optimization algorithm from suggesting an infeasible solution.
Applying constraints to a problem can affect the solution, but this need not be
the case as shown in figure 10.3.
Constrained, Same Solution

Unconstrained

x2

b

x1
Figure 10.2. Bracketing constraints
force the solution to lie within a
hyperrectangle.

Constrained, New Solution

f (x)

x∗

x∗

x∗
x

x
a

Constraints are not typically specified directly through a known feasible set X .
Instead, the feasible set is typically formed from two types of constraints:1
2. inequality constraints, g(x) ≤ 0ab10.2 Constraint Types

1. equality constraints, h(x) = 0xbFigure 10.3. Constraints can change
the solution to a problem, but do
not have to.

We have g representing a lessthan inequality constraint. Greaterthan equality constraints can betranslated into less-than inequality
constraints by introducing a negative sign.

1© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

10 . 3. tra n sforma ti on s to re move c on stra i n ts

169

Any optimization problem can be rewritten using these constraints:
minimizex

subject tof (x)hi (x) = 0 for all i in {1, . . . , ℓ}(10.2)g j (x) ≤ 0 for all j in {1, . . . , m}

Of course, constraints can be constructed from a feasible set X :h (x) = (x ∈/ X)

(10.3)

where Boolean expressions evaluate to 0 or 1.
We often use equality and inequality functions (h(x) = 0, g(x) ≤ 0) to define
constraints rather than set membership (x ∈ X ) because the functions can provide
information about how far a given point is from being feasible. This information
helps drive solution methods toward feasibility.
Equality constraints are sometimes decomposed into two inequality constraints: h (x) ≤ 0h(x) = 0 ⇐⇒(10.4)
 h (x) ≥ 0

However, sometimes we want to handle equality constraints separately, as we
will discuss later in this chapter.

10.3

Transformations to Remove Constraints

In some cases, it may be possible to transform a problem so that constraints can beremoved. For example, bound constraints a ≤ x ≤ b can be removed by passing
x through a transform (figure 10.4):
b+a b−a2x̂
x = t a,b ( x̂ ) =+(10.5)
2
2
1 + x̂2x

Example 10.1 demonstrates this process.
Some equality constraints can be used to solve for xn given x1 , . . . , xn−1 . In
other words, if we know the first n − 1 components of x, we can use the constraint
equation to obtain xn . In such cases, the optimization problem can be reformulated over x1 , . . . , xn−1 instead, removing the constraint and removing one design
variable. Example 10.2 demonstrates this process.

b

a

−1 1
x̂

Figure 10.4. This transform ensuresthat x lies between a and b.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

170c ha p te r 10 . c on stra i n ts

Example 10.1. Removing bounds
constraints using a transform on
the input variable.

Consider the optimization problem
minimizex

x sin( x )subject to 2 ≤ x ≤ 6
We can transform the problem to remove the constraints:
minimizex̂minimize
x̂

4+2



2x̂
1 + x̂2t2,6 ( x̂ ) sin(t2,6 ( x̂ ))



2x̂
sin 4 + 2
1 + x̂2

We can use the optimization method of our choice to solve the unconstrained problem. In doing so, we find two minima: x̂ ≈ 0.242 and x̂ ≈ 4.139,
both of which have a function value of approximately −4.814.

( f ◦ T2,6 )( x̂ )f ( x ) = x sin( x )
2
10
0
0

−2
−4

−10
0

5

10
x

15

−5

0

5

x̂

The solution for the original problem is obtained by passing x̂ throughthe transform. Both values of x̂ produce x = t2,6 ( x̂ ) ≈ 4.914.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

10 . 4 . l a g ra n g e mu l ti p l i e rs 171

Example 10.2. Using constraint
equations to eliminate design variables.

Consider the constraint:h (x) = c1 x1 + c2 x2 + · · · + c n x n = 0
We can solve for xn using the first n − 1 variables:xn =We can transform1(−c1 x1 − c2 x2 − · · · − cn−1 xn−1 )cnminimizef (x)subject toh (x) = 0x

intominimize
x1 ,...,xn−1

f



1
x1 , . . . , xn−1 , (−c1 x1 − c2 x2 − · · · − cn−1 xn−1 )cn

10.4 Lagrange Multipliers
The method of Lagrange multipliers is used to optimize a function subject to equality
constraints. Consider an optimization problem with a single equality constraint:
minimizef (x)subject toh (x) = 0x(10.6)

where f and h have continuous partial derivatives. Example 10.3 discusses such aproblem.
The method of Lagrange multipliers is used to compute where a contour lineof f is aligned with the contour line of h(x) = 0. Since the gradient of a function
at a point is perpendicular to the contour line of that function through that point,
we know the gradient of h will be perpendicular to the contour line h(x) = 0.
Hence, we need to find where the gradient of f and the gradient of h are aligned.
We seek the best x such that the constraint
h (x) = 0

(10.7)

is satisfied and the gradients are aligned∇ f (x) = λ ∇ h (x)(10.8)© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

c ha p te r 10 . c on stra i n ts

Consider the minimization problem:
minimizex

subject to

3− exp − x1 x2 −
2

2



3
− x2 −22 !

x1 − x22 = 0

We substitute the constraint x1 = x22 into the objective function to obtain
an unconstrained objective:



 !
3 2
3 2
3
f unc = − exp − x2 −− x2 −
2
2

Example 10.3. A motivating example of the method of Lagrange multipliers.

h (x) = 0x2

172whose derivative is:



 !

3 2
1
3 2
3 2 1
∂
3
5
f unc = 6 exp − x2 −− x2 −
x2 − x2 + x2 −
∂x2
2
2
2
3
2
Setting the derivative to zero and solving for x2 yields x2 ≈ 1.165. The
solution to the original optimization problem is thus x∗ ≈ [1.358, 1.165]. The
optimum lies where the contour line of f is aligned with h.
If the point x ∗ optimizes f along h, then its directional derivative at x ∗along h must be zero. That is, small shifts of x ∗ along h cannot result in an
improvement.
The contour lines of f are lines of constant f . Thus, if a contour line of f
is tangent to h, then the directional derivative of h at that point, along thedirection of the contour h(x) = 0, must be zero.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

x∗x1

10 . 4 . l a g ra n g e mu l ti p l i e rs 173

for some Lagrange multiplier λ. We need the scalar λ because the magnitudes of
the gradients may not be the same.2
We can formulate the Lagrangian, which is a function of the design variables
and the multiplierL(x, λ) = f (x) − λh(x)(10.9)
Solving ∇L(x, λ) = 0 solves equations (10.7) and (10.8). Specifically, ∇x L = 0
gives us the condition ∇ f = λ∇h, and ∇λ L = 0 gives us h(x) = 0. Any solution
is considered a critical point. Critical points can be local minima, global minima,or saddle points.3 Example 10.4 demonstrates this approach.
We can use the method of Lagrange multipliers to solve the problem inexample 10.3. We form the Lagrangian


 !

3 2
3 2
− x2 −− λ( x1 − x22 )L( x1 , x2 , λ) = − exp − x1 x2 −22When ∇ f is zero, the Lagrange
multiplier λ equals zero, irrespective of ∇h.

2

The method of Lagrange multipliers gives us a first-order necessary
condition to test for optimality. We
will extend this method to include
inequalities.
3

Example 10.4. Using the method of
Lagrange multipliers to solve theproblem in example 10.3.

and compute the gradient∂L3= 2x2 f (x)− x1 x2 − λ
∂x1
2


∂L
3
3
= 2λx2 + f (x) −2x1 ( x1 x2 − ) − 2( x2 − )
∂x2
2
2
∂L
= x22 − x1
∂λSetting these derivatives to zero and solving yields x1 ≈ 1.358, x2 ≈ 1.165,
and λ ≈ 0.170.
The method of Lagrange multipliers can be extended to multiple equality
constraints. Consider a problem with two equality constraints:
minimizef (x)subject toh1 (x) = 0

x(10.10)h2 (x) = 0© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

174

c ha p te r 10 . c on stra i n ts

We can collapse these constraints into a single constraint. The new constraint
is satisfied by exactly the same points as before, so the solution is unchanged.
minimizef (x)subject tohcomb (x) = h1 (x)2 + h2 (x)2 = 0

x(10.11)

We can now apply the method of Lagrange multipliers as we did before. In
particular, we compute the gradient condition∇ f − λ∇hcomb = 0∇ f − 2λ(h1 ∇h1 + h2 ∇h2 ) = 0(10.12)(10.13)

Our choice for hcomb was somewhat arbitrary. We could have usedhcomb (x) = h1 (x)2 + c · h2 (x)2

(10.14)for some constant c > 0.
With this more general formulation, we get(10.15)0 = ∇ f − λ∇hcomb= ∇ f − 2λh1 ∇h1 − 2cλh2 ∇h2= ∇ f − λ1 ∇ h1 − λ2 ∇ h2

(10.16)(10.17)

We can thus define a Lagrangian with ℓ Lagrange multipliers for problems
with ℓ equality constraintsℓL(x, λ) = f (x) − ∑ λi hi (x) = f (x) − λ⊤ h(x)(10.18)

i =1

10.5

Inequality Constraints

Consider a problem with a single inequality constraint:
minimizef (x)subject tog (x) ≤ 0x

(10.19)We know that if the solution lies at the constraint boundary, then the Lagrange
condition holds∇ f + µ∇ g = 0(10.20)© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

10 . 5 . i n e q u a l i ty c on stra i n ts 175

for some non-negative constant µ. When this occurs, the constraint is considered
active, and the gradient of the objective function is limited exactly as it was withequality constraints. Figure 10.5 shows an example.
If the solution to the problem does not lie at the constraint boundary, then theconstraint is considered inactive. Solutions of f will simply lie where the gradientof f is zero, as with unconstrained optimization. In this case, equation (10.20)
will hold by setting µ to zero. Figure 10.6 shows an example.
We could optimize a problem with an inequality constraint by introducing an
infinite step penalty for infeasible points: f (x) if g(x) ≤ 0(10.21)f ∞-step (x) =∞otherwise= f (x) + ∞ · ( g (x) > 0)

We can recover f ∞-step by maximizing with respect to µµ ≥0(10.24)xµ ≥0This reformulation is known as the primal problem.

x∗

Figure 10.6. An inactive inequality
constraint.
Such a problem formulation canbe optimized using direct methods
such as the mesh adaptive direct
search (section 8.2).

4

1
0

For any infeasible x we get infinity and for any feasible x we get f (x).
The new optimization problem is thus
minimize maximize L(x, µ)

Figure 10.5. An active inequality
constraint. The corresponding contour line is shown in red.

(10.22)

Unfortunately, f ∞-step is inconvenient to optimize.4 It is discontinuous andnondifferentiable. Search routines obtain no directional information to steer themselves toward feasibility.
We can instead use a linear penalty µg(x), which forms a lower bound on∞ · ( g(x) > 0) and penalizes the objective toward feasibility as long as µ > 0.
This linear penalty is visualized in figure 10.7.
We can use this linear penalty to construct a Lagrangian for inequality constraints
L(x, µ) = f (x) + µg(x)(10.23)f ∞-step = maximize L(x, µ)x∗−1(10.25)

−1

0

1

g (x)
∞ · ( g (x) > 0)µg(x)Figure 10.7. The linear functionµg(x) is a lower bound to the infinite step penalty so long as µ ≥ 0.
© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

176 c ha p te r 10 . c on stra i n ts

Optimizing the primal problem requires finding critical points x∗ such that:
1. g(x∗ ) ≤ 0
The point is feasible.
2. µ ≥ 0
The penalty must point in the right direction. This requirement is sometimes
called dual feasibility.
3. µg(x∗ ) = 0
A feasible point on the boundary will have g(x) = 0, whereas a feasible pointwith g(x) < 0 will have µ = 0 to recover f (x∗ ) from the Lagrangian.
4. ∇ f (x∗ ) + µ∇ g(x∗ ) = 0
When the constraint is active, we require that the contour lines of f and g bealigned, which is equivalent to saying that their gradients be aligned. Whenthe constraint is inactive, our optimum will have ∇ f (x∗ ) = 0 and µ = 0.
These four requirements can be generalized to optimization problems withany number of equality and inequality constraints:5
minimizef (x)subject tog(x) ≤ 0x(10.26)

If u and v are vectors of the samelength, then we say u ≤ v whenui ≤ vi for all i. We define ≥, <,and > similarly for vectors.
5h(x) = 0
where each component of g is an inequality constraint and each component of his an equality constraint. The four conditions are called the KKT conditions.6
1. Feasibility: The constraints are all satisfied.
g (x∗ ) ≤ 0∗

h(x ) = 0

(10.27)(10.28)2. Dual feasibility: Penalization is toward feasibility.
µ≥0(10.29)3. Complementary slackness: The Lagrange multipliers takes up the slack,
where µi is zero or gi (x∗ ) is zero.7µ⊙g = 0(10.30)

Named after Harold W. Kuhn
and Albert W. Tucker who published the conditions in 1951. It
was later discovered that William
Karush studied these conditionsin an unpublished master’s thesis
in 1939. A historical prospective
is provided by T. H. Kjeldsen, “A
Contextualized Historical Analysis of the Kuhn-Tucker Theorem
in Nonlinear Programming: The
Impact of World War II,” Historia
Mathematica, vol. 27, no. 4, pp. 331–
361, 2000.
6

7
The operation a ⊙ b indicates theelement-wise product between vectors a and b.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

10 . 6 . d u a l i ty 177

4. Stationarity: The objective function contour is tangent to each active constraint.8∇ f ( x ∗ ) + ∑ µ i ∇ gi ( x ∗ ) + ∑ λ j ∇ h j ( x ∗ ) = 0(10.31)ijThese four conditions are first-order necessary conditions for optimality andare thus FONCs for problems with smooth constraints. Just as with the FONCs forunconstrained optimization, special care must be taken to ensure that identified
critical points are actually local minima.

10.6

8
Since the sign of λ is not restricted, we can reverse the sign for
the equality constraints from themethod of Lagrange multipliers.

Duality

In deriving the FONCs for constrained optimization, we also find a more generalform for the Lagrangian. This generalized Lagrangian isL(x, µ, λ) = f (x) + ∑ µi gi (x) + ∑ λ j h j (x)i(10.32)j

The primal form of the optimization problem is the original optimization problem formulated using the generalized Lagrangianminimize maximize L(x, µ, λ)
x

µ≥0,λ

(10.33)The primal problem is identical to the original problem and is just as difficult
to optimize.
The dual form of the optimization problem reverses the order of the minimization and maximization in equation (10.33):
maximize minimize L(x, µ, λ)
µ≥0,λ

x

(10.34)The max-min inequality states that for any function f (a, b):
maximize minimize f (a, b) ≤ minimize maximize f (a, b)
a

b

b

a

(10.35)The solution to the dual problem is thus a lower bound to the solution of the
primal problem. That is, d∗ ≤ p∗ , where d∗ is the dual value and p∗ is the primalvalue.
The inner minimization in the dual problem is often folded into a dual function,D(µ ≥ 0, λ) = minimize L(x, µ, λ)x(10.36)© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

178 c ha p te r 10 . c on stra i n ts

for notational convenience. The dual function is concave.9 Gradient ascent on aconcave function always converges to the global maximum. Optimizing the dual
problem is easy whenever minimizing the Lagrangian with respect to x is easy.
We know that maximizeµ≥0,λ D(µ, λ) ≤ p∗ . It follows that the dual functionis always a lower bound on the primal problem (see example 10.5). For any µ ≥ 0
and any λ, we haveD(µ ≥ 0, λ) ≤ p∗
(10.37)The difference p∗ − d∗ between the dual and primal values is called the duality
gap. In some cases, the dual problem is guaranteed to have the same solution as
the original problem—the duality gap is zero.10 In such cases, duality provides
an alternative approach for optimizing our problem. Example 10.6 demonstrates
this approach.

10.7

For a detailed overview, see S.
Nash and A. Sofer, Linear and Nonlinear Programming. McGraw-Hill,
1996.
9

Conditions that guarantee a zero
duality gap are discussed in S.
Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004.
10

Penalty Methods

We can use penalty methods to convert constrained optimization problems into
unconstrained optimization problems by adding penalty terms to the objectivefunction, allowing us to use the methods developed in previous chapters.
Consider a general optimization problem:
minimizef (x)subject tog(x) ≤ 0x(10.38)h(x) = 0
A simple penalty method counts the number of constraint equations that are
violated:
pcount (x) = ∑( gi (x) > 0) + ∑ h j (x) 6= 0
(10.39)ijwhich results in the unconstrained optimization problem that penalizes infeasibility
minimize f (x) + ρ · pcount (x)(10.40)x

where ρ > 0 adjusts the penalty magnitude. Figure 10.8 shows an example.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

10 . 7. p e n a l ty me thod s 179

Example 10.5. The dual function isa lower bound of the primal problem.

Consider the optimization problem:
minimizesin( x )subject tox2 ≤ 1x

The generalized Lagrangian is L( x, µ) = sin( x ) + µ( x2 − 1), making the
primal problem:
minimize maximize sin( x ) + µ( x2 − 1)xµ ≥0

and the dual problem:
maximize minimize sin( x ) + µ( x2 − 1)
x

µ ≥0

10

µ = 0.00µ = 0.25µ = 0.50µ = 0.75µ = 1.00µ = 1.25µ = 1.50µ = 1.75µ = 2.00

y

5

x∗

0

−4

−2

0
x

2

4

The objective function is plotted in black, with the feasible region traced
over in blue. The minimum is at x ∗ = −1 with p∗ ≈ −0.841. The purple
lines are the Lagrangian L( x, µ) for different values of µ, each of which has
a minimum lower than p∗ .

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

180 c ha p te r 10 . c on stra i n ts

Consider the problem:
minimizex1 + x2 + x1 x2

subject tox12 + x22 = 1x

The Lagrangian is L( x1 , x2 , λ) = x1 + x2 + x1 x2 + λ( x12 + x22 − 1).
We apply the method of Lagrange multipliers:

Example 10.6. An example of Lagrangian duality applied to a problem with an equality constraint.
The top figure shows the objectivefunction contour and the constraint
with the four critical points marked
by scatter points. The bottom figure shows the dual function.

x2∂L= 1 + x2 + 2λx1 = 0∂x1∂L= 1 + x1 + 2λx2 = 0∂x2∂L= x12 + x22 − 1 = 0
∂λ

2

0

−2
−2

Solving yields four potential solutions, and thus four critical points:x2

λx1 + x2 + x1 x2

−1
0
√

0
−1
√

1/2
 1/2 √ 12  −1 − 2√1
2 −1 + 2

−1
−1

√2+1
√2+2
√2−1
2−2

√2+1
√2+2
√2−1
2−2

1
2 +
1
2 −

√

√

2 ≈ 1.914

2 ≈ −0.914

We find that the two optimal solutions are [−1, 0] and [0, −1].
The dual function has the form

D(λ) = minimize x1 + x2 + x1 x2 + λ( x12 + x22 − 1)x1 ,x2The dual function is unbounded below when λ is less than 1/2 (consider
x1 → ∞ and x2 → −∞). Setting the gradient to 0 and solving yields x2 =−1 − 2λx1 and x1 = (2λ − 1)/(1 − 4λ2 ) for λ 6= ±1/2. When λ = 1/2,
x1 = −1 − x2 and D(1/2) = −1. Substituting these into the dual function
yields:
−λ − 11
2λ+1 λ ≥ 2D(λ) =
−∞otherwise
The dual problem maximizeλ D(λ) is maximized at λ = 1/2.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

2

0

−2

D(λ)

x1

0
x1

−4

λ∗

−6
0

2

4
λ

10 . 7. p e n a l ty me thod s 181

Penalty methods start with an initial point x and a small value for ρ. The
unconstrained optimization problem equation (10.40) is then solved. The resulting
design point is then used as the starting point for another optimization with anincreased penalty. We continue with this procedure until the resulting point isfeasible, or a maximum number of iterations has been reached. Algorithm 10.1
provides an implementation.
function penalty_method(f, p, x, k_max; ρ=1, γ=2)
for k in 1 : k_max
x = minimize(x -> f(x) + ρ*p(x), x)ρ *= γif p(x) == 0
return x
end
end
return x
endj

Quadratic penalties close to the constraint boundary are very small and may
require ρ to approach infinity before the solution ceases to violate the constraints.
It is also possible to mix a count and a quadratic penalty function (figure 10.10):
pmixed (x) = ρ1 pcount (x) + ρ2 pquadratic (x)

a

b
f (x)
f ( x ) + ρpcount ( x )Figure 10.8. The original and countpenalized objective functions forminimizing f subject to x ∈ [ a, b].
Algorithm 10.1. The penalty
method for objective function f,
penalty function p, initial point
x, number of iterations k_max,
initial penalty ρ > 0, and penalty
multiplier γ > 1. The methodminimize should be replacedwith a suitable unconstrained
minimization method.

This penalty will preserve the problem solution for large values of ρ, but it
introduces a sharp discontinuity. Points not inside the feasible set lack gradient
information to guide the search towards feasibility.
We can use quadratic penalties to produce a smooth objective function (figure 10.9):
pquadratic (x) = ∑ max( gi (x), 0)2 + ∑ h j (x)2
(10.41)
i

x

x
a

b

f (x)
f ( x ) + ρpquadratic ( x )Figure 10.9. Using a quadratic
penalty function for minimizing f
subject to x ∈ [ a, b].

(10.42)

Such a penalty mixture provides a clear boundary between the feasible region
and the infeasible region while providing gradient information to the solver.
Figure 10.11 shows the progress of the penalty function as ρ is increased.
Quadratic penalty functions cannot ensure feasibility as discussed in example 10.7.

x
a

b
f (x)
f ( x ) + pmixed ( x )Figure 10.10. Using both aquadratic and discrete penalty
function for minimizing f subject
to x ∈ [ a, b].
© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

182

c ha p te r 10 . c on stra i n ts

ρ=0

ρ=1

ρ=2

ρ=3

x

x

x

x2

2

x

0

−2
−2

0
x1

−2

2

0
x1

2

−2

0
x1

−2

2

0
x1

2

Figure 10.11. The penalty method
applied to the flower function, appendix B.4, and the circular constraint
x12 + x22 ≥ 2

Consider the problem
minimizex

subject tox≥5x

Example 10.7. An example showing how quadratic penalties cannot
ensure feasibility.

using a quadratic penalty function.
The unconstrained objective function isf ( x ) = x + ρ max(5 − x, 0)2
The minimum of the unconstrained objective function isx∗ = 5 −1
2ρ

While the minimum of the constrained optimization problem is clearly x =5, the minimum of the penalized optimization problem merely approaches
x = 5, requiring an infinite penalty to achieve feasibility.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

10 . 8 . a u g me n te d l a g ra n g e me thod 183

10.8 Augmented Lagrange Method
The augmented Lagrange method11 is an adaptation of the penalty method specifically for equality constraints. Unlike the penalty method, where ρ must sometimes
approach infinity before a feasible solution is found, the augmented Lagrange
method will work with smaller values of ρ. It uses both a quadratic and a linear
penalty for each constraint.
For an optimization problem with equality constraints h(x) = 0, the penalty
function is:1
pLagrange (x) = ρ ∑(hi (x))2 − ∑ λi hi (x)(10.43)2 ii

Not to be confused with themethod of Lagrange multipliers.

11

where λ converges toward the Lagrange multiplier.
In addition to increasing ρ with each iteration, the linear penalty vector is
updated according to:λ(k+1) = λ(k) − ρh(x)(10.44)
Algorithm 10.2 provides an implementation.

function augmented_lagrange_method(f, h, x, k_max; ρ=1, γ=2)λ = zeros(length(h(x)))
for k in 1 : k_max
p = x -> ρ/2*sum(h(x).^2) - λ⋅h(x)x = minimize(x -> f(x) + p(x), x)λ -= ρ*h(x)ρ *= γend
return x
end

10.9

Algorithm 10.2. The augmented Lagrange method for objective function f, equality constraint function h, initial point x, numberof iterations k_max, initial penalty
scalar ρ > 0, and penalty multiplier γ > 1. The function minimize
should be replaced with the minimization method of your choice.

Interior Point Methods

Interior point methods (algorithm 10.3), sometimes referred to as barrier methods, areoptimization methods that ensure that the search points always remain feasible.12
Interior point methods use a barrier function that approaches infinity as one
approaches a constraint boundary. This barrier function, pbarrier (x), must satisfy
several properties:

Interior point methods that are
stopped early produce nearly optimal, though feasible, design points.
Methods may be stopped early due
to time or processing constraints.

12

1. pbarrier (x) is continuous© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

184

c ha p te r 10 . c on stra i n ts

2. pbarrier (x) is nonnegative (pbarrier (x) ≥ 0) in the feasible region

3. pbarrier (x) approaches infinity as x approaches any constraint boundarySome examples of barrier functions are:Inverse Barrier:pbarrier (x) = − ∑i1gi ( x )(10.45)Log Barrier:pbarrier (x) = − ∑log(− g (x))

0
i

i

if gi (x) ≥ −1otherwise(10.46)

A problem with inequality constraints can be transformed into an unconstrained optimization problem
minimize f (x) +
x

1
p
(x)
ρ barrier(10.47)

When ρ is increased, the penalty for approaching the boundary decreases (figure 10.12).
Special care must be taken such that line searches do not leave the feasible
region. Line searches f (x + αd) are constrained to the interval α = [0, αu ], where
αu is the step to the nearest boundary. In practice, αu is chosen such that x + αd isjust inside the boundary to avoid the boundary singularity.
Like the penalty method, the interior point method begins with a low value forρ and slowly increases it until convergence. The interior point method is typicallyterminated when the difference between subsequent points is less than a certain
threshold. Figure 10.13 shows an example of the effect of incrementally increasingρ.
The interior point method requires a feasible point from which to start the
search. One convenient method for finding a feasible point is to optimize thequadratic penalty function
minimize pquadratic (x)
x

x
a

b
f (x)
f ( x ) + pbarrier ( x )f ( x ) + 12 pbarrier ( x )1f ( x ) + 10
pbarrier ( x )Figure 10.12. Applying the interior
point method with an inverse barrier for minimizing f subject tox ∈ [ a, b].

(10.48)© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

10 . 9. i n te ri or p oi n t me thod s

Algorithm 10.3. The interior point
method for objective function f,barrier function p, initial point x,
initial penalty ρ > 0, penalty multiplier γ > 1, and stopping tolerance ϵ > 0.

function interior_point_method(f, p, x; ρ=1, γ=2, ϵ=0.001)
delta = Inf
while delta > ϵx′ = minimize(x -> f(x) + p(x)/ρ, x)delta = norm(x′ - x)
x = x′
ρ *= γend
return xendρ = 0.5x2x2

ρ = 1.0

ρ = 10.0

ρ = 100.0

x

x

x

185

0

−2
−2

0
x1

2

−2

0
x1

2

−2

0
x1

2

−2

0
x1

2

Figure 10.13. The interior point
method with the inverse barrier
applied to the flower function, appendix B.4, and the constraint
x12 + x22 ≥ 2© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

186

c ha p te r 10 . c on stra i n ts

10.10 Summary• Constraints are requirements on the design points that a solution must satisfy.
• Some constraints can be transformed or substituted into the problem to resultin an unconstrained optimization problem.
• Analytical methods using Lagrange multipliers yield the generalized Lagrangian
and the necessary conditions for optimality under constraints.
• A constrained optimization problem has a dual problem formulation that iseasier to solve and whose solution is a lower bound of the solution to theoriginal problem.
• Penalty methods penalize infeasible solutions and often provide gradient
information to the optimizer to guide infeasible points toward feasibility.
• Interior point methods maintain feasibility but use barrier functions to avoid
leaving the feasible set.

10.11 Exercises
Exercise 10.1. Solveminimizex

subject tox≥0x(10.49)using the quadratic penalty method with ρ > 0. Solve the problem in closed form.
Exercise 10.2. Solve the problem above using the count penalty method with
ρ > 1 and compare it to the quadratic penalty method.
Exercise 10.3. Suppose that you are solving a constrained problem with thepenalty method. You notice that the iterates remain infeasible and you decide tostop the algorithm. What can you do to be more successful in your next attempt?
Exercise 10.4. Consider a simple univariate minimization problem where you
minimize a function f ( x ) subject to x ≥ 0. Assume that you know that theconstraint is active, that is, x ∗ = 0 where x ∗ is the minimizer and f ′ ( x ∗ ) > 0 fromthe optimality conditions. Show that solving the same problem with the penalty
method(10.50)f ( x ) + (min( x, 0))2
© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

10 . 11. e x e rc i se s 187

yields an infeasible solution with respect to the original problem.
Exercise 10.5. What is the advantage of the augmented Lagrange method compared to the quadratic penalty method?
Exercise 10.6. When would you use the barrier method in place of the penalty
method?
Exercise 10.7. Give an example of a smooth optimization problem, such that,for any penalty parameter ρ > 0, there exists a starting point x (1) for which thesteepest descent method diverges.
Exercise 10.8. Suppose you have an optimization problem
minimizexf (x)subject to h(x) = 0(10.51)g(x) ≤ 0
but do not have an initial feasible design. How would you find a feasible pointwith respect to the constraints, provided that one exists?
Exercise 10.9. Solve the constrained optimization problem 
4minimizesinxx
subject to(10.52)x ∈ [1, 10]

using both the transform x = t a,b ( x̂ ) and a sigmoid transform for constraint
bounds x ∈ [ a, b]:(b − a)x = s( x̂ ) = a +(10.53)
1 + e− x̂
Why is the t transform better than the sigmoid transform?
Exercise 10.10. Give an example of a quadratic objective function involving two
design variables where the addition of a linear constraint results in a different
optimum.
Exercise 10.11. Suppose we want to minimize x13 + x22 + x3 subject to the constraintthat x1 + 2x2 + 3x3 = 6. How might we transform this into an unconstrained
problem with the same minimizer?
© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

188c ha p te r 10 . c on stra i n ts

Exercise 10.12. Suppose we want to minimize − x1 − 2x2 subject to the constraints
ax1 + x2 ≤ 5 and x1 , x2 ≥ 0. If a is a bounded constant, what range of values of awill result in an infinite number of optimal solutions?
Exercise 10.13. Consider using a penalty method to optimize
minimize

1 − x2

subject to|x| ≤ 2x(10.54)

Optimization with the penalty method typically involves running several optimizations with increasing penalty weights. Impatient engineers may wish to
optimize once using a very large penalty weight. Explain what issues are encountered for both the count penalty method and the quadratic penalty method.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com