TDA206 - Discrete Optimisation

Lecture notes - Lecture 2

1 Recap from lecture 1

The first lecture discussed the notion of convexity and tried to get some intuition about what convexity means.

  • Convex set: No line between two points inside the set crosses the boundary of the set. A convex set can not have any crevices or dents.
  • Convex function: For a function to be a convex function it's epigraph and domain must be convex. That is a line from any two points on the line of the function can not go outside the area above the graph of the function.

    Convex functions only have one maximum/minimum (no other local extremes).

The formal definition of convexity is:

Given a set S ∈ ℝⁿ

∀x₁,x₂,f: x₁,x₂ ∈ S
  f(λx₁ + (1-λ)x₂) ≤ λf(x₁) + (1-λ)f(x₂)

Another way to check convexity of a function that is once-derivable is to check if only the node of a tangent is on the line of the function. If so (only the node of the tangent is on the line, all other points on the tangent is outside of the function line) then the function is convex.

For a twice-derivable function we can use the hessian and check that it is positive and semi-definite. If not, our function is not convex.

2 Linear programming

In linear programming (LP) our goal is to optimise our objective function f(x) such that our constraints hold. We do this by trying to restrict the domain so that it only contains the values for which f(x) or x satisfies the constraints. The set of all values on x that satisfies the constraints on either x or f(x) are called feasible and the set of all feasible x's form our feasible region. Our feasible region will therefore provide us with the valid inputs to our objective function.

We can create our feasible region by restricting the domain of our objective f(x) by creating multiple half-spaces, one half-space per constraint. Our feasible region is then the intersection of all these half-spaces and thus we have a set of values that are valid for all our constraints.

Is this feasible region created by the intersection of half-spaces a convex set? Well, to prove this we start by proving that intersections of convex sets form convex sets themselves.

2.1 Proof of intersections of convex sets are convex

We start with two convex sets \(A, B\) and form a new set \(S\) from the intersections of \(A\) and \(B\), \(S = A \cap B\). In this new set we choose any two points and draw a line between them (equation 1.) We know from the fact that \(S\) contains the common elements in both \(A\) and \(B\) that if \(s\) and \(t\) are present in \(S\) then they must be present in the two other sets as well (equation 2 & 3). Moreover since both \(A\) and \(B\) are convex this means that the line segment \(\overline{st}\) also is present in both sets and therefore in \(S\) (equation 4, 5 & 6).

The line segment between \(s\) and \(t\) must be the same line segment since line segments in euclidian spaces are unique.

\begin{align} ∀s,t ∈ S \end{align} \begin{align} s,t ∈ S &⇒ s,t ∈ A \\ s,t ∈ S &⇒ s,t ∈ B \\ \end{align} \begin{align} A~\mathrm{convex} &⇒ \overline{st} ∈ A \\ B~\mathrm{convex} &⇒ \overline{st} ∈ B \\ \overline{st} ∈ A ∧ \overline{st} ∈ B &⇒ \overline{st} ∈ S \end{align}

2.2 Diet problem

The diet problem is a problem with roots in the WWII. During the second world war a lot of soldiers needed to be fed and already economically stressed countries thought of ways to feed their armies cheaply without having them die of malnutrition. For more information about the problem, read it's wikipedia article.

Formally the problem can be expressed in the following way:

We want to minimise: c₁x₁ + c₂x₂ + c₃x₃ + …

Realising that we are looking at a vector-valued (where our x\(_i\)'s are the vector-valued input) we can restate the above minimisation problem as:

min c\(^\intercal\)x

Symbol Meaning
c\(^\intercal\) vector of costs per food item
x vector of amount per food item
a\(^\intercal\) vector of nutrients per food item

We can't just minimise the cost of feeding the soldiers, we need some kind of constraints that make sure they don't starve or suffer from malnutrition. Therefore we come up with the following constraints:

\begin{align*} a^\intercal x &≥ 150 \\ x_i &≥ 0 \\ c^\intercal x &≤ 2000 \\ \end{align*}

We solve the problem by creating half-spaces of the constraints and taking the intersection of those half-spaces forming our feasible region and then minimising the cost function (c\(^\intercal\)x).

2.3 General linear programming problems

The diet problem is an instance of a linear programming problem. In general an LP problem looks like this:

We want to maximize some kind of profit function (max p\(^\intercal\)x) such that some constraints are valid.

For instance the constraints can be that we only can't produce/use/consume more than a total amount of all our resources (a\(^\intercal\)x ≤ b), that some calculation on the resources must match a specific value (e\(^\intercal\)x = h) or that some calculation (i.e. enough nutrients in a diet) on the resources must be greater than a specific value (k\(^\intercal\)x ≥ l).

Depending on the constraints (= size of the feasible region) the solution set can have different shape. If the feasible region is empty, that is if the constraints contradict each other, there can be no solution to the problem at all since there are no valid inputs. If the constraints (viewed graphically) are aligned roughly perpendicular to each other and not parallell to our objective function then there would be a point where the half-planes' boundaries would intersect and in that vertex is our optimum solution. A third option is possible when the objective function is not bounded by constraints in the maximisation direction, in that case there are no optimum solution (since we can keep on and just pick greater values), but plenty of solutions.

2.4 Canonical forms

There exists a canonical form of LP problems that is easy to solve and in other ways work with.

Canonical form: max c\(^\intercal\)x, such that Ax ≤ b and x\(_i\) ≥ 0. Where x ∈ ℝⁿ, A is some matrix.

Is the restriction that all values in x must be non-negative a problem? No, because we can always transform a problem with a negative x\(_i\) by replacing that x\(_i\) with two new variables (\(x'_i~\mathrm{and}~x''_i\)) that are strictly and replacing x\(_i\) in the objective function to \(x'_i - x''_i\).

Author: Jacob Jonsson

Created: 2019-01-22 tis 19:56