Technische Universität München, Zentrum Mathematik

Lehrstuhl für Angewandte Geometrie und Diskrete Mathematik

Fundamentals of Convex Optimization (MA 2504),
SoSe 2018
Prof. Dr. Peter Gritzmann | PD Dr. René Brandenberg

Homework sheet 1
Homework exercise 1.1
Let X ⊂ Rn , X 6= ∅ and τ : Rn → Rm . Prove the following statements:
a) For all w ∈ Rn : aff(X + w) = aff(X) + w.
b) 0 ∈ aff(X) ⇔ aff(X) = lin(X).
c) aff(X) = v + lin(X \ {v} − v) for any v ∈ X.
d) The affine subspaces of Rn are exactly the sets of solutions of systems of linear equations.
n o
e) For all v 1 , . . . , v k ∈ X it holds v 1 , . . . , v k affinely independent if and only if v l − v i : l 6= i is
linearly independent for any l ∈ [k].

Answer to Exercise 1.1

a) Let w ∈ Rn :

x ∈ aff(X + w)
k
X k
X
⇔∃λ1 , ..., λk ∈ R with λi = 1, v 1 , ..., v k ∈ X : x = λi (v i + w)
i=1 i=1
k
X k
X
⇔∃λ1 , ..., λk ∈ R with λi = 1, v 1 , ..., v k ∈ X : x = w + λi v i
i=1 i=1
⇔x ∈ aff(X) + w

b) “⇐” is clear as 0 ∈ lin(X).

“⇒”: aff(X) ⊂ lin(X) holds in general as each affine combination is in particular a linear
combination.
Now, assume 0 ∈ aff(X). Then for all λ1 , . . . , λk ∈ R and x1 , . . . , xk ∈ X we can define
λ0 := 1 − ki=1 λi and obtain ki=1 λi xi = ki=1 λi xi + λ0 0 ∈ aff(X). Thus lin(X) ⊂ aff(X).
P P P

a) b)
c) Let v ∈ X. Then aff(X) = aff(X − v) + v = lin(X − v) + v = lin((X − v) \ {0}) + v =
lin(X \ {v} − v) + v.
d) Let X be an affine subspace, i. e., X = v+U for some fixed v ∈ Rn and a linear subspace U . From
linear algebra, we know that any linear subspace is the solution space of a system of a homogenous
linear equation system. This means there exists A ∈ Rm×n such that U = {x ∈ Rn : Ax = 0}.
Thus, X = v + U = {v + x ∈ Rn : Ax = 0} = {y ∈ Rn : A(y − v) = 0} = {y ∈ Rn : Ay = b},
with b := Av.

Page 1 of 6

MA2504 Summer 2018

 e) “⇐”: Assume v 1 , . . . , v k are affinely dependent. Then there exist λ1 , . . . , λk ∈ R, not all 0, with
Pk Pk i
i=1 λi = 0 such that i=1 λi v = P0. We may assume without loss of generality (wlog) that
λk 6= 0. Then v = i=1 − λk v or k−1
k−1
k λi i λi i k Pk−1 λi
i=1 − λk (v − v ) = 0 since i=1 − λk = 1. However, the
P
1 k
latter show that v − v , . . . , v k−1 k
− v are linear dependent.
“⇒”: Assume wlog that v 1 − v k , . . . , v k−1 − v k are linear dependent. Then there exist
λ1 , . . . , λk−1 ∈ R, not all 0, such that k−1 i k Pk−1 i Pk−1 k
i=1 λi (v −v ) = 0. That means i=1 λi v − i=1 λi v =
P
Pk−1
0, thus defining λk = − i=1 λi we see that v 1 , . . . , v k are affinely dependent.

Homework exercise 1.2

Let the polyhedron P ⊂ R5 be defined by the inequalities

x1 + 2x2 + x4 ≤ 6 (1)
x1 + x2 + x5 ≤ 4 (2)
3x1 + x5 ≤ 6 (3)
−x3 + 2x4 ≤ −1 (4)
x3 − x4 ≤ 1 (5)
x3 + x5 ≤ 4 (6)
x1 , . . . , x 5 ≥ 0 (7 - 11)

a) Show: dim(P ) = 3 (i. e. there exists an affine 3-dimensional subspace X of R5 containing P

and P itself contains 4 affinely independent points.
Is any of the constraints redundant?
b) Sketch P using an appropriate embedding into R3 .

Answer to Exercise 1.2

a) From adding inequalities (4) and (5) we obtain x4 ≤ 0, which means together with inequality (10)
that x4 = 0. Insertion into (4) and (5) gives x3 ≥ 1 and x3 ≤ 1, respectively. Hence, equations
(4), (5), and (10) are implicit equations, showing that aff(P ) ⊂ {x ∈ R5 : x3 = 1, x4 = 0} and
thus equation (9) is redundant.Thus dim(P ) ≤ 3. However, since u3 , u1 + u3 , u2 + u3 , u5 + u3
are feasible and affinely independent, we have dim(P ) ≥ 3 and together dim(P ) = 3
b)
x5

x7 x8
x6

x5 x1 x2
x1

x4
x3
x2

Page 2 of 6

MA2504 Summer 2018

 Homework exercise 1.3
a) The feasible sets of two LPs may be given as follows:

(I) x1 − x2 = 0 (II) x1 − x2 ≥ −1
x1 + x2 ≤ 1 x1 ≥ 0

(i) Sketch the feasible sets.

(ii) By replacing the second constraint in (I) by x1 + x2 + s = 1, where s ≥ 0 is a so called
“slack variable” (Schlupfvariable) the feasible set is embedded into R3 . Sketch the feasible
set and modify the objective cT x = c1 x1 + c2 x2 such that the solution of the 3 dimensional
LP leads directly to a solution of the original two dimensional LP.
− −
(iii) Defining new variables x+ +
2 , x2 ≥ 0 and replacing x2 by x2 = x2 − x2 , the feasible set in
(II) is embedded into the positive orthant of R3 . Again, sketch the new feasible set and
give a reasonably modified objective, when starting with cT x = c1 x1 + c2 x2 .
b) The natural form of an LP has been defined in the lectures, the standard form is

min cT x
Ax = b
x ≥ 0.

Transform the following LP into natural and standard form using appropriate constraints,
variables and objectives:
min cT x + dT y
Ax + By ≤ a
Cx + Dy = b
x ≥ 0
Give proper dimensions for matrices and vectors (before and after the transformation).

Page 3 of 6

MA2504 Summer 2018

 Answer to Exercise 1.3
a) (i)

x2 x2

x1

x1

(ii)
x2

x1

s
The original objective c = (c1 , c2 )T ∈ R2 is replaced by c̃ = (c1 , c2 , 0)T ∈ R3 .
(iii)

Page 4 of 6

MA2504 Summer 2018

 x+
2

x1

x−
2

The original objective c = (c1 , c2 )T ∈ R2 is replaced by c = (c1 , c2 , −c2 )T . Since

− −
c2 x+ +
2 − c2 x2 = c2 (x2 − x2 )

uniqueness of the optimal solution is lost.

b) Let A ∈ Rm1 ,n1 , B ∈ Rm1 ,n2 , C ∈ Rm2 ,n1 , B ∈ Rm2 ,n2 , c ∈ Rn1 , d ∈ Rn2 , a ∈ Rm1 , and
b ∈ Rm2 . Thus the total dimension of the original system is (m1 + m2 ) × (n1 + n2 ).
(i) Natural form:
min cT x + dT y
Ax + By ≤ a
Cx + Dy ≤ b
−Cx − Dy ≤ −b
−Ix ≤ 0
Total dimension: (m1 + 2m2 + n1 ) × (n1 + n2 )
(ii) Standard form:
min cT x + dT y + − dT y −
Ax + By + − By − + z = a
Cx + Dy + − Dy − = b
x, y + , y − , z ≥ 0
Total dimension: (m1 + m2 ) × (n1 + 2n2 + m1 ).

Homework exercise 1.4

An international enterprise plans to build up a distribution system in Bavaria. Contracts with major
customers G1 , . . . , Gn are already made, locations S1 , . . . , Sm for major storages are in appraisal. The
goal is to find an optimal selection for the storage locations.
Building a storage at location Sj causes fixed costs dj . Supplying customer Gi from location Sj causes
costs cij per unit transported. Moreover, the total delivery quantity ai for Gi is bound by contract
and the capacity bj of the possible storage at Sj is also given.

a) Formulate an optimization problem for the solution of the facility location problem given above.
Use only linear constraints, but restrict variables to be integer, if necessary.

Page 5 of 6

MA2504 Summer 2018

 b) Due to internal reasons, customer G1 wants to be served from one storage only. Add an
appropriate restriction.

Answer to Exercise 1.4

a) We introduce variables xij to model the delivery quantity from storage location Sj to customer
Gi . Since the total delivery quantities for each customer have to be fulfilled, we obtain the
constraints: m
i ∈ [n]
P
xij = ai
j=1
xij ≥ 0 i ∈ [n], j ∈ [m]
Moreover, the decision if a storage at location Sj is built, is modeled with a 0/1-variable – a so
called “decision variable” – yj :
yj ∈ {0, 1} j ∈ [m]
The capacity limit of the storage at Sj then leads to the constraint
n
X
xij ≤ bj yj j ∈ [m]
i=1

(which means it is 0, if the storage is not built and bj if it is built). The objective is the
minimization of costs over the full planning horizon, i. e.
n X
X m m
X
min cij xij + dj yj
i=1 j=1 j=1

In total we have a so called Mixed Integer Linear Program (MILP) – mixed, since some variables
must be integral (yj ), some not (xij ). If the delivery quantities should be “discrete”, i. e. integral,
we obtain an integer linear program / integer linear optimization problem (ILP).
b) Surely one may modify the above model in many ways to adjust it for different circumstances.
Serving some customer Gi from a single storage may be modeled by restricting the coresponding
variables xij as follows:
xij ∈ {0, ai } j ∈ [m]
However, for reasons we will learn about later, one should replace the last condition by x̃ij ∈ {0, 1}
using the transformation xij = ai x̃ij .

Page 6 of 6

MA2504 Summer 2018