Adriana Silva Research Log September | 2018

Weeks 1 & 2

Convex Optimization [1]

Theory

1 Introduction

A mathematical optimization problem has the form:

minimize f0 (x)
(1)
subjected to fi (x) ≤ bi , i = 1, ..., m

where: 


x = (x1 , ..., xn ) → optimizationvariable
f : Rn → R

→ objectivef unction
0
.


fi : Rn → R, i = 1, ..., m → constraintf unctions

b , ..., b
1 m → limits
There are classes of optimization problems, characterized by particular forms of the objective and con-
straint functions. An important example of the optimization problem is called a linear program if the
objective and constraint functions f0 , ..., fm are linear, i.e., satisfy:

fi (αx + βy) = αfi (x) + βfi (x) (2)

∀x, y ∈ Rn and ∀α, β ∈ R.

There is one class of optimization problems called convex optimization problems. A convex optimization
problem is one in which the objective and constraint functions are convex, which means they satisfy the
inequality:
fi (αx + βy) ≤ αfi (x) + βfi (x) (3)
∀x, y ∈ Rn and ∀α, β ∈ R with α + β = 1, α ≥ 0 and β ≥ 0.
Convexity is more general than linearity: inequality replaces the more restrictive equality, and the in-
equality must hold only for certain values of α and β. Since any linear program is therefore a convex
optimization problem, it can be considered that convex optimization is a generalization of linear program-
ming.

1
Adriana Silva Research Log September | 2018

2 Convex sets

2.1 Affine and convex sets

2.1.1 Lines vs. line segments

Suppose two points x1 6= x2 in Rn . Points in y, such that:

y = θx1 + (1 − θ)x2 , (4)

where θ ∈ R, form the line passing through x1 and x2 . The parameter value θ = 0 corresponds to y = x2
and θ = 1 corresponds to y = x1 .
Values of the parameter θ between 0 and 1 correspond to the (closed) line segment between x1 and x2 .
From another perspective, y is the sum of the point x2 and the direction x1 − x2 (from x2 to x1 ) scaled
by the parameter θ. Thus, θ gives the fraction of the way from x2 to x1 where y lies. As θ increases from
0 to 1, the point y moves from x2 to x1; for θ ¿ 1, the point y lies on the line beyond x1.

Figure 1: Line passing through x1 and x2 , described by θx1 + (1 − θ)x2

2.1.2 Affine sets

A set C ⊆ Rn is affine if the line through any two distinct points in C lies in C. That is, if for any
x1 , x2 ∈ C and θ ∈ R: thetax1 + (1 − θ)x2 ∈ C.
The affine set C contains the linear combination of any two points in C, if the sum of the linear coefficients
is 1.
Generalizing, a point of the form θ1 x1 + ... + θk xk , where θ1 + ... + θk = 1, is an affine combination of the
points x1 , ..., xk .
The set of all affine combinations of points in a set C is the affine hull of C:

aff C = {θ1 x1 + ... + θk xk | x1 , ..., xk ∈ C, θ1 + ... + θk = 1}.

2.1.3 Convex sets

A set C is convex if the line segment between any two points in C lies in C. That is, if for any
x1 , x2 ∈ C and any θ with 0 < θ < 1: thetax1 + (1 − θ)x2 ∈ C.

2
Adriana Silva Research Log September | 2018

Figure 2: Example: convex set (left) vs. non-convex set (right)

Every affine set is also convex, since it contains the entire line between any two distinct points in it,
therefore it also contains the line segment between the points.
A point of the form θ1 x1 +...+θk xk , where θ1 +...+θk = 1 and θi ≥ 0, i = 1, ..., k, is a convex combination
of the points x1 , ..., xk .
The set of all convex combinations of points in C is the convex hull :

aff C = {θ1 x1 + ... + θk xk | xi ∈ C, θi ≥ 0, i = 1, ..., k, θ1 + ... + θk = 1}.

2.1.4 Cones

A set C is called a cone, if for every x ∈ C and θ ≥ 0: θx ∈ C. A set C is a convex cone if it is convex
and a cone, which means that for any x1 , x2 ∈ C and θ1 , θ2 ≥ 0: θ1 x1 + θ2 x2 ∈ C. Geometrically, points
of this form can be described as forming a two-dimensional pie slice.

Figure 3: Cone: all the points of the form θ1 x1 + θ2 x2 , where θ1 , θ2 ≥ 0. θ1 = θ2 = 0 is at 0 and the edges
(which correspond to θ1 = 0 or θ2 = 0) pass through the points x1 and x2 .

A point of the form θ1 x1 + ... + θk xk with θ1 , ..., θk ≥ 0 is called a conic combination of x1 , ..., xk . If xi
are in a convex cone C, then every conic combination of xi is in C. A set C is a convex cone if and only
if it contains all conic combinations of its elements.

2.2 Examples of convex sets

• The empty set ∅, any single point x0 and the whole space Rn are affine, therefore convex.

• Any line is affine.

• A line segment is convex but not affine.

• Any subspace is affine and a convex cone. Therefore, convex.

3
Adriana Silva Research Log September | 2018

2.2.1 Hyperplane

A hyperplane is a set of the form

{x | aT x = b} (5)
where a ∈ Rn , a 6= 0 and b ∈ R.
Analytically it is the solution set of a nontrivial linear equation (and an affine set). Geometrically, the
hyperplane can be interpreted as the set of points with a constant inner product to a given vector a, or
as a hyperplane with normal vector a.

Figure 4: Hyperplane in R2 with normal vector a and a point x0 in the hyperplane. For any point x in
the hyperplane, (x − x0 ) is orthogonal to a.

2.2.2 Halfspace

A (closed) halfspace is a set of the form

{x | aT x ≤ b} (6)
where a a 6= 0. It is the solution set of one (nontrivial) linear inequality.
Halfspaces are convex, but not affine. A hyperplane divides Rn into two halfspaces.

Figure 5: A hyperplane defined by aT x = b in R2 determines two halfspaces. The halfspace determined

by aT x ≥ b is the halfspace extending in the direction a. The halfspace determined by aT x ≤ b extends
in the direction −a.

The halfspace can also be expressed as {x | aT (x − x0 ) ≤ 0}, where x0 is any point on the associated
hyperplane and satisfies aT x0 = b. The halfspace consists of x0 plus any vector that makes an obtuse (or
right) angle with the outward normal vector a.

4
Adriana Silva Research Log September | 2018

2.2.3 Ball

A (Euclidean) ball in Rn has the form:

B(xc , r) = {x | ||x − xc ||2 ≤ r} (7)

where r > 0. r is the radius and xc is the center of the ball. ||.||2 denotes the Euclidean norm.

||x||2 = (xT x)1/2 (8)

A ball is a convex set if: ||x1 − xc ||2 ≤ r, ||x2 − xc ||2 ≤ r and 0 < θ < 1.

2.2.4 Polyhedra

A polyhedron is defined as the solution set of a finite number of linear equalities and inequalities:

P = {x | aTj x ≤ bj , j = 1, ..., m, cTj x = dj , j = 1, ..., p}. (9)

A polyhedron is the intersection of a finite number of halfspaces and hyperplanes.

Figure 6: The polyhedron P is the intersection of five halfspaces, with outward normal vectors a1, ...., a5.

In compact notation:
P = {x | Ax ≺ b, Cx = d} (10)
The symbol ≺ means vector inequality.

2.3 Operations that preserve convexity

• Intersection

• Affine functions

• Perspective function

• Linear-fractional functions

2.3.1 Intersection

If S1 and S2 are convex, then: S1 ∩ S2 is convex. It extends to an infinite number of sets.

5
Adriana Silva Research Log September | 2018

2.3.2 Affine functions

The image of a convex set under f is convex:

S ⊆ Rn convex ⇒ f (S) = f (x) | x ∈ Sconvex.

The inverse image f −1 (S) of a convex set under f is convex:

S ⊆ Rn convex ⇒ f −1 (S) = f (x) | x ∈ Sconvex.

2.4 Generalized inequalities

2.4.1 Proper cones and generalized inequalities

A cone K ⊆ Rn is called a proper cone if:

• K is convex.

• K is closed.

• K is solid (nonempty interior).

• K is pointed (it contains no line: x ∈ K, −x ∈ K ⇒ x = 0).

Generalized inequality defined by a proper cone K:

x K y ⇔ y − x ∈ K, (11)

x ≺K y ⇔ y − x ∈ intK. (12)
Many properties of K are similar to ≤ on R.

2.4.2 Minimum and minimal elements

x ∈ S is the minimum element of S if:

∀y ∈ S ⇒ x K y. (13)
x ∈ S is a minimal element of S if:
∀y ∈ S, x K y ⇒ y = x. (14)

Figure 7: Left: the set S1 has a minimum element x1 . Right: x2 is a minimal point of S2 .

6
Adriana Silva Research Log September | 2018

2.5 Separating and supporting hyperplanes

2.5.1 Separating hyperplane theorem

Suppose C and D are nonempty disjoint convex sets, C ∩ D = ∅. Then there exists a 6= 0 and b such that
aT b ≤ b ∀x ∈ C and aT b ≥ b ∀x ∈ D.

Figure 8: The hyperplane x | aT x = b is called a separating hyperplane for the sets C and D.

2.5.2 Supporting hyperplane theorem

Suppose C ⊆ Rn , and x0 is a point in its boundary. The hyperplane:

{x | aT x = aT x0 } (15)

where a 6= 0 and aT x ≤ aT x0 ∀x ∈ C, is called a supporting hyperplane to C at the point x0 . If C is

convex, then there exists a supporting hyperplane at every boundary point of C.

Figure 9: The hyperplane {x | aT x = aT x0 } supports C at x0 .

2.6 Dual cones

K is a cone. The dual cone of K is:

K ∗ = {y | xT y ≥ 0, ∀x ∈ K}. (16)

K ∗ is a cone and is always convex, even if K is not convex.

Properties of K ∗ :

• K ∗ is closed and convex.

• K1 ⊆ K2 implies K2∗ ⊆ K1∗ .

7
Adriana Silva Research Log September | 2018

• If K has nonempty interior, then K ∗ is pointed.

• If the closure of K is pointed then K ∗ has nonempty interior.

• K ∗∗ is the closure of the convex hull of K. (Hence if K is convex and closed, K ∗∗ = K.)

Exercises - Chapter 2 [1]

2.1

For k = 2. Suppose that:



C ⊆ R2

x1 , x2 ∈ C



θ1 , θ2 ∈ R

θ1 ≥ 0, θ2 ≥ 0





θ1 + θ 2 = 1


y = θ 1 x1 + θ 2 x2
θ2 = 1 − θ1
⇒ y = x2 + θ1 (x1 − x2 )
By the definition of convex set: y = x2 + θ1 (x1 − x2 ) ∈ C.
Now, for k=3 suppose: 

 C ⊆ R3

x1 , x2 , x3 ∈ C



θ1 , θ2 , θ3 ∈ R

θ1 ≥ 0, θ2 ≥ 0, θ3 ≥ 0





θ1 + θ 2 + θ3 = 1


y = θ 1 x 1 + θ2 x 2 + θ3 x 3
Assuming that at least one θi is not equal to 1 ⇒ θ1 6= 1.

θ 2 + θ3 = 1 − θ1
(1 − θ1 )
⇒ y = θ1 x1 + (θ2 x2 + θ3 x3 ) = θ1 x1 + (u2 x2 + u3 x3 )(1 − θ1 )
(1 − θ1 )
θ2 θ3
where u2 = 1−θ1 , u3 = 1−θ1 and u2 , u3 ≥ 0.

θ2 + θ 3 1 − θ1
u2 + u3 = = =1
1 − θ1 1 − θ1
C is a convex set. x2 , x3 ∈ C ⇒ u2 x2 + u3 x3 . Since x1 ∈ C ⇒ y ∈ C.

8
Adriana Silva Research Log September | 2018

General case: 

C ⊆ Rn

x1 , ..., xK ∈ C



θ1 , ..., θK ∈ R

θi ≥ 0, i = 1, ..., k





θ1 + ... + θK = 1


y = θ1 x1 + ... + θK xK
Assuming θ1 6= 1 ⇒ θ2 + ... + θK = 1 − θ1 .

(1 − θ1 )
⇒ y = θ1 x1 + (θ2 x2 + θ3 x3 + ... + θK xK ) = θ1 x1 + (u2 x2 + u3 x3 + ... + uK xK )(1 − θ1 )
(1 − θ1 )
θ2 θ3 θK
where u2 = 1−θ1 , u3 = 1−θ1 , uK = 1−θ1 and u2 , u3 , ..., uK ≥ 0.
C is convex and x2 , x3 , ..., xk ∈ C. Thus, u2 x2 + u3 x3 + ... + uK xK ∈ C. And since x1 ∈ C ⇒ y ∈ C.

2.2

A set is convex if and only if it combines every convex combination of its points. This means, it contains
the line between any two points in the set (definition of convex set).
Assuming C as a convex set. Suppose the intersection of C with any line is convex. Take any two points
x1 , x2 ∈ C. The intersection of C with the line that goes through x1 and x2 is convex. All the convex
combinations of x1 and x2 are in the intersection line and therefore they are in C.
A set is affine if the line that goes through any two distinct points of the set lies in the set. That is, it
contains every affine combination of two points in it.
Take any two distinct points of the affine set C, x1 , x2 ∈ C. The line that goes through x1 and x2 contains
all the affine combinations of x1 and x2 . The intersection of the line with set C also contains all the affine
combinations of x1 and x2 . And that applies for any two points of the set.

2.3

Midpoint convexity (definition): a set C is midpoint convex if whenever two points a, b ∈ C, the
midpoint (average) a+b
2 ∈ C. A convex set is midpoint convex.
x+y
Suppose that C is a closed midpoint convex set. x, y ∈ C. The midpoint 2 ∈ C.
Assume that z is a point on the line segment between x and y.
xi + yi x0 + y0 x+y
zi = where z0 = =
2 2 2
(
zi , zi ≤ z0
xi+1 =
xi , zi > z0

9
Adriana Silva Research Log September | 2018

(
zi , zi > z0
yi+1 =
yi , zi ≤ z0
By this construction, z is always on the line segment between xi and yi and zi converges to z0 .
Due to midpoint convexity of C, zi ∈ C ∀i. And because C is closed, z0 ∈ C. This applies to all z on the
line segment between x and y, so C is convex.

2.12

Which of this sets are convex?

a) A slab (superficie?): {x ∈ Rn | α ≤ aT x ≤ β}.
(
a1 x1 + ... + an xn ≥ α
A slab is the intersection of these 2 halfspaces
a1 x1 + ... + an xn ≤ β

A halfspace is a convex set and a slab is the intersection between 2 halfspaces. The intersection of 2
convex sets is convex, therefore a slab is a convex set.
b) A rectangle: {x ∈ Rn | αi ≤ xi ≤ βi , i = 1, ..., n}.
Just like in a), a rectangle is a finite intersection of 2 halfspaces, therefore is a convex set.
c) A wedge (cunha?): {x ∈ Rn | aT1 x ≤ b1 , aT2 x ≤ b2 }.
Again, this is an intersection of 2 halfspaces, therefore is convex.
d) The set of points closer to a given point than a given set: {x | ||x − x0 ||2 ≤ ||x − y||2 , ∀y ∈ S}, S ⊆ Rn .
Applying the Euclidean norm:

||x − x0 ||2 ≤ ||x − y||2 ⇒ (x − x0 )T (x − x0 ) ≤ (x − y)T (x − y)

⇔ xT x − 2xT0 x + xT0 x0 ≤ xT x − 2y T x + y T y
⇔ 2(y − x0 )T x ≤ y T y − xT0 x0
This defines a halfspace, therefore is convex.
e) The set of points closer to one set than another: {x | dist(x, S) ≤ dist(x, T )}, S, T ⊆ Rn and
dist(x, S) = inf {||x − z||2 | z ∈ S}.
Example of 2 sets: S = {0, 10} and T = {5}.

{x | dist(x, S) ≤ dist(x, T )} = {x ∈ R | x ≤ 2.5 ∨ x ≥ 7.5}

This set is not convex.

f ) The set: {x | x + S2 ⊆ S1 }, where S1 , S2 ⊆ Rn and S1 is convex.

x + S2 ⊆ S1 if x + y ∈ S1 ∀y ∈ S2
\
⇔ {x | x + S2 ⊆ S1 } = {x | x + y ∈ S1 }
y∈S2

10
Adriana Silva Research Log September | 2018

This set is convex.

T
Nota: x ∈ A∈M ⇔ ∀A ∈ M, x ∈ A.

g) The set of points whose distance to a does not exceed a fixed fraction θ of the distance to b: {x | ||x −
a||2 ≤ θ||x − b||2 }, a 6= b, 0 ≤ θ ≤ 1.
This set has the form of a ball, therefore is convex.

||x − a||2 ≤ θ||x − b||2 =

= ||x − a||22 ≤ θ2 ||x − b||22 =

= (x − a)T (x − a) ≤ θ2 (x − b)T (x − b) = ...

2.16

S1 and S2 are convex sets in Rm+n .

Their partial sum is: S = {(x, y1 , y2 ) | x ∈ Rm , y1 , y2 ∈ Rn , (x, y1 ) ∈ S1 , (x, y2 ) ∈ S2 }.
Considering two points in S, the convex combination of those two points is in S [ver a demonstração],
because of the convexity of S1 and S2 . Partial sum of convex sets is convex.

2.25
→ C is a closed convex set.
→ x1 , ..., xK are on the boundary of C.
→ C ⊆ {x | aTi (x − xi ) ≤ 0, i = 1, ..., k}: aTi (x − xi ) = 0 defines a supporting hyperplane for C at xi .
→ Polyhedra Pinner = conv{x1 , ..., xK }
→ Polyhedra Poutter = {x | aTi (x − xi ) ≤ 0, i = 1, ..., k}

Pinner is the set with all the convex combinations of the points x1 , ..., xK . The points xi are on the
boundary of C and C is closed and convex, therefore Pinner ⊆ C.
If x ⊆ C ⇒ x ⊆ Poutter because C ⊆ {x | aTi (x − xi ) ≤ 0, i = 1, ..., k}.
Thus, Pinner ⊆ C ⊆ Poutter .

2.31

Properties of dual cones.

a) K ∗ is a convex cone.
K ∗ is the intersection of two halfspaces that includes the origin. Therefore, K ∗ is closed and convex. [ver
os desenhos no caderno]

11
Adriana Silva Research Log September | 2018

b) K1 ⊆ K2 ⇒ K2∗ ⊆ K1 ∗.
y ⊆ K2 ∗ means xT y ≥ 0 ∀x ∈ K2 and K2 includes K1 . Therefore xT y ≥ 0 ∀x ∈ K1 . [ver o desenho no
caderno]
c) K ∗ is closed.
K ∗ is an intersection of two halfspaces, that include the boundary points ((aT x) = 0). It also includes
the origin as a boundary point. Therefore, K ∗ is closed.
d) The interior of K ∗ is given by intK ∗ = {y | yT x > 0∀x ∈ clK}.
clK: closure of K and includes interior plus boundary points of K.
{y | y T x = 0} is the boundary of K ∗ (the edges). So, the interior of K ∗ is given by {y | y T x > 0}.
e) If K has nonempty interior then K ∗ is pointed.
Pointed: contains no line (x ∈ K, −x ∈ K ⇒ x = 0).
If y ∈ K ∗ and −y ∈ K ∗ , K ∗ is not pointed. This means, y T ≥ 0 and −y T ≥ 0, ∀x ∈ K. So,
y T x = 0∀x ∈ K. Thus, K has empty interior.
f ) K ∗∗ is the closure of K. (Hence if K is closed, K ∗∗ = K.)
y 6= 0 is the normal vector of a halfspace containing K if and only if y ∈ K ∗ . The intersection of all
halfspaces containing a convex cone K is the closure of K. Therefore the closure of K is K ∗∗ .
g) If the closure of K is pointed then K ∗ has nonempty interior.
If K has empty interior, there is a a 6= 0 such that aT y = 0, ∀y ∈ K ∗ . This means a and −a are in K ∗ ,
so K ∗ is not pointed.

Next Week

⇒ Chapter 3

References

[1] Boyd S., Vandenberghe L., Convex Optimization, Cambridge University Press

12