4What is optimization?
4.1 What is an optimization problem?
Can you see a way of solving this optimization problem by eliminating in
the constraint ?
Hint
and can be inserted in . Why is this helpful?
A person is in distress meters from the beach. The life guard
spots the situation, but is meters from where he would naturally jump
in the water as indicated below. The life guard runs m/s on the
beach and swims m/s in the water. How far () should he run along the
beach before jumping into the water in order to minimize the time needed
to reach the person in distress?
The time spent moving with a speed of over a distance of is
If the life guard jumps in the water at the point he will have
to swim a distance of
using the Pythagorean theorem. Therefore the optimization problem becomes
Strictly speaking we do not need the constraint , as the life guard is free
to run in the other direction. So the optimization problem is simply to minimize
with no strings attached i.e., is just assumed to be any number.
You need to build a rectangular fence in front of your house for a herb garden.
Your house will make up one side of the rectangle, so you only need to build three
sides. Suppose you have 10 m of wire. What is the maximum area of the herb garden you can
wall in?
4.2 General definition
In our most general setting an optimization problem looks like
where and are subsets of with and is a function.
A solution to the optimization problem is a vector , such that
for every . Here is called an optimum and is called the optimal value.
We will often write the optimization problem defined above in short form as
The complexity of the problem depends very much on the nature of and . Also,
we cannot even be certain that an optimization problem has a solution. Consider
the problem
where .
Here can be made arbitrarily small subject to the constraint and
the problem has no optimal solution.
We have deliberately not included maximization problems in Definition
4.5
. This is
because a maximization problem, such as
can be formulated as the minimization problem
Again, we will use the short notation
for the maximization problem in
(4.1)
.
A solution to
(4.1)
is a vector , such that
for every . Again, is called an optimum and the
optimal value.
Suppose that the maximization problem
is formulated as
the minimization problem
Show that is the optimal value
and the optimum for
(4.3)
if
is the optimal value
and the optimum for
(4.4)
.
Suppose that . Solve the optimization problem
4.3 Convex optimization
A line is a subset of the form
where with .
A line in the plane is (usually) given by its equation
This means that it consists of points satisfying .
Here can be interpreted as the slope of the line and the intersection with the
-axis.
What about all the points with ? Certainly they also deserve to be called
a line. However, they do not satisfy an equation like
(4.5)
. Informally, this line
has infinite slope.
Therefore we introduce the parametric representation of a line: a line is the
set of points of the form
where ,
is any point on the line and
is a non-zero (directional) vector.
Example of a line in with (directional) vector through the point .
Given two distinct points
there is one and only one line passing through them. This line is given by
How do we convert the line in
(4.5)
to the parametric form
(4.6)
? Well, we know that the two distinct points
are on the line. Therefore it is given by
by
(4.7)
.
Compute the parametric representation of the line through the points and .
Also compute and in the representation for .
What is the parametric representation of the
line consisting of the points with ?
Show in Definition
4.10
that if is given by and , then
you might as well replace by , where is a real number and . It gives
the same line.
Show that there is a unique line passing through two distinct points
and that it is given by and in Definition
4.10
.
Do the points
lie on the same line in ?
Show that the line through two distinct points is equal to the subset
A convex subset is a subset that contains the
line segment between any two of its points i.e.,
for every number with .
Which of the subsets below are convex?
The points on a line in .
A closed interval in is a subset of the form
for . Prove that is a convex subset of .
Hint
Keep cool and just apply the definitions! First of all, if and only if
Now pick any . We must show that if and , then
You may also write this out as
implies that
Hint
implies that
What is ?
Let and be convex subsets of . Prove that is a
convex subset of . Generalize this to show that if
are any number of convex subsets of , then their intersection
is a convex subset of . Is the union of two convex subsets necessarily convex?
A convex function is a function
defined on a convex subset , such that
for every number with .
-
Let the function be given by
, where . Show that is a convex
function.Try the case first.
-
Can you at this point prove that is a convex function?
-
Using that is a convex function, prove that is a convex function. Use that and if (here we really need , since for example , but is not true) to conclude that for .
-
It is a fact that is not a convex function, but can
you explain this using the definition of a convex function?Try and .
Let be a convex function. Then the subset
is a convex subset of , where .
Suppose that and . Looking at Definition
4.19
we must prove that
By the definition of being convex (Definition
4.24
), it follows that
But, since and we have
and therefore
Therefore,
and .
In hunting for optimal solutions to an optimization problem one is often stuck with a
point , which is optimal locally. This means that for
every that is sufficiently close to (we will explain what this means in the next
chapter). The remarkable thing that happens in a convex optimization problem is
that if is optimal locally, then it is a global optimum! It satisfies
not only for close to , but for every .
Below you see a plot of the function (press Compute)
restricted
to the interval . You can see that it has a local minimum around and
also that this minimum is not a global minimum (certainly is smaller). So
is not a convex function on this interval according to Remark
4.28
(but if you look at it more locally on the
interval it is a convex function).
Solve the optimization problem
for and .
4.4 Linear optimization
Show that a linear function is convex.
Use a selection of previous exercises to show that
the subset defined in
(4.9)
is a convex subset of .
4.5 Fourier-Motzkin elimination
What is the solution if we replace Maximize with Minimize in the optimization problem
(4.10)
?
LP = MixedIntegerLinearProgram(maximization=False, solver = "GLPK").'