UC Berkeley

Department of Electrical Engineering and Computer Sciences

EECS 127 - EECS 227AT. Optimization

Models in Engineering

Lecture Notes
Fall 2025

Instructor: Somayeh Sojoudi

Typeset by: George Ma

© EECS 127 - EECS 227AT. Optimization Models in Engineering

EECS 127/227AT Lecture Notes Fall 2025

Convexity.
First, we define different types of sets.
• A ball in Rn centered at x ∈ Rn of radius ε is shown as
Bε (x) = {z ∈ Rn | ∥z − x∥2 ≤ ε}.

Example:
x
n=1
−ε ε

n=2 ε

n=3

• A set S ∈ Rn is called open if for every x ∈ S, there is a radius ε > 0 such that
Bε (x) ⊆ S.
Example:
falls out of S
for all ε > 0

x
x
but ⇒

S this ball works is not open

The above set is not open because if x is on the edge of S, some part of the ball Bε (x)
always falls out of S no matter how you choose ε > 0. However, the following set is
open:

S such ball always exists

(dotted lines are not ⇒ this is an open set
part of the set)

© EECS127/227AT. Optimization Models in Engineering, Somayeh Sojoudi, Fall 2025.

EECS 127/227AT Lecture Notes Fall 2025

Notice that the edges are no longer part of S.

• A set S ⊆ Rn is called closed if its complement Rn \S is open.
Example:

S: R2 \S:

R2 \S is open, thus S is closed.

• Rn and the empty set ∅ are both open and closed.
• The interior of a set S ⊆ Rn is defined as:
int(S) = {z ∈ S | Bε (z) ⊆ S for some ε > 0}.

The interior includes all points z that are strictly inside the set, meaning that there is
a ball around each such point that is in the set:

S int(S)
dotted lines are
excluded from the set

Example 1 (Interior of sets).

int(Rn ) = Rn , int( [1, 2] ) = (1, 2) .
|{z} | {z }
1≤x≤2 1<x<2

■
• The closure of a set S ⊆ Rn is defined as:
n o
cls(S) = z ∈ Rn z = lim x(k) where x(k) ∈ S, ∀k .
k→∞

This means that a point z is in the closure if there is a sequence of points x(1) , x(2) , . . .
in S that converges to z.

© EECS127/227AT. Optimization Models in Engineering, Somayeh Sojoudi, Fall 2025.

EECS 127/227AT Lecture Notes Fall 2025

Example:

z is in the closure since

one can pick x(1) = x(2) = · · · = z
z

z is not in S but is in
z the closure since there is such
a sequence:

x(1) . . . z
x(2)

The closure includes points on the boundary:

S cls(S)

• The boundary of a set S ⊆ Rn is defined as

∂S = cls(S)\ int(S).

Example:

⇒ ⇒

S int(S) cls(S) ∂S

⇒ ⇒

S int(S) cls(S) ∂S

© EECS127/227AT. Optimization Models in Engineering, Somayeh Sojoudi, Fall 2025.

EECS 127/227AT Lecture Notes Fall 2025

Note that in the second case, ∂S is not part of S.

• A set S ⊆ Rn is bounded if there exists r > 0 such that S ⊆ Br (0) (meaning that S
can be fit into a ball centered at the origin).
Example:

S is neither open
nor closed
(dotted lines O
mean exclusion)
S
fits in a ball ⇒ bounded

• A set S ⊆ Rn is called compact if it is closed and bounded.

Example:

grows into
wedge: infinity

closed and bounded closed but unbounded

⇒ compact ⇒ not compact

Consider a set of points x(1) , . . . , x(m) ∈ Rn .

• A point x ∈ Rn is called a linear combination of x(1) , . . . , x(m) if x = α1 x(1) + · · · +
αm x(m) for some α1 , . . . , αm ∈ R.
• The set of all linear combinations of points is called the linear hull of x(1) , . . . , x(m) ,
which is the same as span(x(1) , . . . , x(m) ).
• A point x ∈ Rn is called an affine combination of x(1) , . . . , x(m) if x = α1 x(1) + · · · +
αm x(m) , for some α1 , . . . , αm ∈ R such that α1 + · · · + αm = 1.
• A point x ∈ Rn is called a convex combination of x(1) , . . . , x(m) if x = α1 x(1) + · · · +
αm x(m) , for some α1 , . . . , αm ∈ R such that α1 , . . . , αm ≥ 0 and α1 + · · · + αm = 1.
Definition 1 (Affine hull). Given a set S ⊆ Rn , define the affine hull of S as the set of all
affine combinations of x(1) , . . . , x(m) ∈ S for all possible points x(1) , . . . , x(m) and all values
of m ∈ {1, 2, . . . }.
Theorem 1. The affine hull aff(S) of an arbitrary set S is an affine set.
(Recall that an affine set is defined to be a point plus a subspace in Definition 4 of Lecture
Note 2.)

© EECS127/227AT. Optimization Models in Engineering, Somayeh Sojoudi, Fall 2025.

EECS 127/227AT Lecture Notes Fall 2025

Example 2. 1. If S = {x(1) }, then aff(S) = {x(1) }.

2. If S = {x(1) , x(2) }, then aff(S) is a line passing through x(1) and x(2) .

aff(S)
x(2)

x(1)

3. If S = {x(1) , x(2) , x(3) }, then aff(S) is a plane passing through x(1) , x(2) , x(3) .

aff(S)

x(2)

x(1)
x(3)

4. If S = {x ∈ R3 | x3 = 1, x21 + x22 ≤ 1}, then S is a lifted ball, and aff(S) is a plane

containing this lifted ball.
x3 x3
aff(S)
S

x2 x2

x1 x1
■
Definition 2 (Convex hull). Given a set S ⊆ R , define the convex hull of S as the set
n

of all convex combinations of x(1) , . . . , x(m) ∈ S for all possible points x(1) , . . . , x(m) and all
values of m ∈ {1, 2, . . . }.
We denote the convex hull of S as co(S).
Example 3. 1. If S = {x(1) }, then co(S) = {x(1) }.
2. If S = {x(1) , x(2) }, then co(S) is the line segment connecting x(1) and x(2) .

x(2)
co(S)
(1)
x

3. If S = {x ∈ R2 | x21 + x22 = 1} is a circle, then co(S) = {x ∈ R2 | x21 + x22 ≤ 1} is a ball.

■

© EECS127/227AT. Optimization Models in Engineering, Somayeh Sojoudi, Fall 2025.

EECS 127/227AT Lecture Notes Fall 2025

Definition 3 (Convex set). A set C ⊆ Rn is called convex if for every two points x(1) , x(2) ∈ C,
the segment connecting x(1) and x(2) is in C.

In other words,

αx(1) + (1 − α)x(2) ∈ C, ∀x(1) , x(2) ∈ C, ∀α ∈ [0, 1].

| {z }
characterization of segment

x(2)
αx(1) + (1 − α)x(2)
x(1) for some 0 ≤ α ≤ 1

Example 4 (Convex and non-convex sets).

convex non-convex

Theorem 2. Given an arbitrary set S ⊆ Rn , its convex hull co(S) is the smallest convex
set containing S, meaning that any other convex set containing S includes co(S).

Example:

S co(S) any convex set containing S

must include co(S)

(The convex hull adds the dark blue part to S.)

Definition 4 (Dimension). Consider a set S ⊆ Rn .

1. If S is a subspace, then dim(S) is the number of basis vectors.

2. If S is an affine set: S = x0 + V , where x0 ∈ Rn is a point and V ⊆ Rn is a subspace,

then dim(S) is defined as dim(V ).

© EECS127/227AT. Optimization Models in Engineering, Somayeh Sojoudi, Fall 2025.

EECS 127/227AT Lecture Notes Fall 2025

3. If S is a convex set, then dim(S) is defined as the dimension of the affine hull aff(S).

Examples:

subspace of affine set of

dimension 1 dimension 1

dim(S) = 2
S aff(S)
convex

The union of two convex sets may not be convex:

non-convex

C2
C1 C1 ∪ C 2

Theorem 3. Given convex sets C1 , . . . , Cm , their intersection C1 ∩ C2 ∩ · · · ∩ Cm is convex.

Example:

convex

C2 C1 ∩ C 2
C1

© EECS127/227AT. Optimization Models in Engineering, Somayeh Sojoudi, Fall 2025.