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.