1Introduction and preliminaries
IB Optimisation
1.1 Constrained optimization
In optimization, the objective is to maximize or minimize some function. For
example, if we are a factory, we want to minimize our cost of production. Often,
our optimization is not unconstrained. Otherwise, the way to minimize costs is
to pro duce nothing at all. Instead, there are some constraints we have to obey.
The is known as constrained optimization.
Definition
(Constrained optimization)
.
The general problem is of constrained
optimization is
minimize f(x) subject to h(x) = b, x ∈ X
where
x ∈ R
n
is the vector of decision variables,
f
:
R
n
→ R
is the objective
function,
h
:
R
n
→ R
m
and
b ∈ R
m
are the functional constraints, and
X ⊆ R
n
is the regional constraint.
Note that everything above is a vector, but we do not bold our vectors. This
is since almost everything we work with is going to be a vector, and there isn’t
much point in bolding them.
This is indeed the most general form of the problem. If we want to maximize
f
instead of minimize, we can minimize
−f
. If we want our constraints to be an
inequality in the form
h
(
x
)
≥ b
, we can introduce a slack variable
z
, make the
functional constraint as
h
(
x
)
− z
=
b
, and add the regional constraint
z ≥
0. So
all is good, and this is in fact the most general form.
Linear programming is, surprisingly, the case where everything is linear. We
can write our problem as:
minimize c
T
x subject to
a
T
i
x ≥ b
i
for all i ∈ M
1
a
T
i
x ≤ b
i
for all i ∈ M
2
a
T
i
x = b
i
for all i ∈ M
3
x
i
≥ 0 for all i ∈ N
1
x
j
≤ 0 for all i ∈ N
2
where we’ve explicitly written out the different forms the constraints can take.
This is too clumsy. Instead, we can perform some tricks and turn them into
a nicer form:
Definition
(General and standard form)
.
The general form of a linear program
is
minimize c
T
x subject to Ax ≥ b, x ≥ 0
The standard form is
minimize c
T
x subject to Ax = b, x ≥ 0.
It takes some work to show that these are indeed the most general forms. The
equivalence between the two forms can be done via slack variables, as described
above. We still have to check some more cases. For example, this form says
that
x ≥
0, i.e. all decision variables have to be positive. What if we want
x
to
be unconstrained, ie can take any value we like? We can split
x
into to parts,
x
=
x
+
− x
−
, where each part has to be positive. Then
x
can take any positive
or negative value.
Note that when I said “nicer”, I don’t mean that turning a problem into this
form necessarily makes it easier to solve in practice. However, it will be much
easier to work with when developing general theory about linear programs.
Example. We want to minimize −(x
1
+ x
2
) subject to
x
1
+ 2x
2
≤ 6
x
1
− x
2
≤ 3
x
1
, x
2
≥ 0
Since we are lucky to have a 2D problem, we can draw this out.
x
1
x
2
x
1
− x
2
= 3
x
1
+ 2x
2
= 6
c
−(x
1
+ x
2
) = 0 −(x
1
+ x
2
) = −2 −(x
1
+ x
2
) = −5
The shaded region is the feasible region, and
c
is our cost vector. The dotted lines,
which are orthogonal to
c
are lines in which the objective function is constant.
To minimize our objective function, we want the line to be as right as possible,
which is clearly achieved at the intersection of the two boundary lines.
Now we have a problem. In the general case, we have absolutely no idea how
to solve it. What we do know, is how to do unconstrained optimization.