TDA206 - Discrete Optimisation
Lecture notes - Lecture 1
1 Course information
Link to course is: http://www.cse.chalmers.se/edu/course/TDA206/
Teacher | |
---|---|
Name | John Wiedenhoeft |
mailto://john.wiedenhoeft@chalmers.se | |
Office | EDIT 6449 |
Office hours | Thursdays 14:00 |
2 What is optimization?
The most general explaination: We want to know the maximum or minimum of a function. Often there are constraints on the function that makes the problem hard (like NP-complete).
A medical company makes x number of boxes of medication. The market price for a box of medication, p, and the cost, c, of manufacturing a box of medication are two of the constraints. The other constraints are that we can not manufacture more than 500 boxes, we produce boxes in batches of 10 boxes and cannot discard any boxes. p = 900 - 0.4x c = 100 + 0.6x profit per day: x(p-c) = x(800-x) Our goal is to maximize the profit, namely maximize x(800-x), where x ∈ N, such that - x mod 10 ≡ 0 - x ≤ 500 - 0 ≤ x x(800-x) is our objective functions. We want to minimze the loss, cost or energy functions and maximize our gain or profit functions.
3 What is convex optimization?
3.1 What is a convex shape?
A convex shape is a intuitionally a shape withouts dents or crevices. The formal definition of a convex shape is a shape where we can draw a line between any two points in the shape and the line never crosses the boundary of the shape.
A set S ∈ ℝⁿ is convex iff
∀x,y ∈ , λ ∈ [0,1] λx + (1 - λ)y ∈ S
3.2 What is a norm?
A norm of a vector x, ‖x‖ is some kind of relationship between a vector x to a positive numeric value, some kind of length of the vector x.
‖x‖ ≥ 0 -- non-negative ‖x‖ = 0 ⇔ v = 0 ‖x + y‖ ≤ ‖x‖ + ‖y‖ -- triangle inequality ‖αx‖ = |α|‖x‖ -- absolute {homogenity, scalability}
3.3 Show that norms are convex shapes
‖λx + (1 - λ)y‖ ≤ ‖λx‖ + ‖(1 - λ)y‖ ≤ λ‖x‖ + (1-λ)‖y‖ ≤ λr + (1-λ)r = λr + r - λr = r
3.4 What is half-spaces?
A half-space is intuitively a space that is cut in half by a shape, for instance ℝ² space split in half by a straight line or ℝ³ space split in half by a plane.
It is a convex shape since no line between any points inside the half-space can possibly cross the border of the half-space.
3.5 What is convex functions?
Convex functions are functions that only have one maximum or minimum. The epigraph (the shape above the graph, enclosed by the graph) of a convex function forms a convex shape. The formal proof:
∀x₁,x₂, λ ∈ [0,1]: f(λx₁ + (1-λ)x₂) ≤ λf(x₁)+(1-λ)f(x₂)
To show this for a function that is only differentiable once: ∀x,x₀,f(x) ≥ f(x₀) + ∇f(x₀)*(x-x₀)
x² convex:
f(x) ≥ f(x₀) + ∇f(x₀)*(x-x₀) x² ≥ x₀² + 2x₀(x-x₀) = x₀² + 2x₀x - 2x₀² = 2x₀x - x₀² x² - 2x₀x + x₀² ≥ 0 (x-x₀)² ≥ 0
For a twice-differentiable function we can see that the value of the second derivative keeps the same value all the time.
This is provable with the Hessian:
Hf(x) ≥ 0