convex analysis Flashcards
Hyperplane
H = {x∈ℝⁿ|cᵀx = β}
The hyperplane
separates ℝⁿ into two halves
convex combination
if the sum of the lambdas is 1 and v can be written as a linear combination of us with lambdas
polyhedron
{x∈ℝⁿ| Ax≤b}
bounded polyhedron
polytop
convex
A set is convex if the segment αx* + (1-α)x̄ where α∈[0,1] is contained in the set
Any hyperplanes and its halfspaces is…
convex
The intersection of convex sets…
is convex
A polyhedron is…
convex
cone
A set C is called a cone if x∈C implies λx∈C for all λ greater than or equal to 0.
convex cone
a cone and a convex set
a polyhedron is a cone if it can be represented as
P={x: Ax≤0} for some matrix A.
convex function
A function f of the vector (x₁, x₂, … , xₙ) is said to be conves if the following inequality holds for any two vectors x,y. f(λx +(1-λ)y) ≤ λf(x) + (1-λ)f(y) for all λ∈[0,1]
a convex function is convex if for….
every segment between to points the line is above the graph line
The objective function is…
convex
extreme point
a point x in a convex set X is called an extreme point of X if you cannot express it as a strict convex combination of two distinct points in X. i.e. cannot have λ∈(0,1)
ray
Let d be a vector and x be a point. The collection of points of the form {x + λd: λ≥0} is called a ray from x in direction d.
direction
Given a convex set a vector d is called a direction of a set if for each x in the set the ray {x + λd: λ≥0} belongs to the set
how to find the direction of a set
- let x be an arbitray fixed feasible point
- The d is a a direction iff x+λd∈X for all λ greater than or equal to 0.
- use constraints to show d≥0 and gain inequalities for d. these are conditions for d to be a direction of X. chose any d that satisfies these.
extreme direction
Am extreme direction of a convex set is a direction of the set that cannot be represented as a strict positive combination of two distinct directions of the set.
distinct directions
two directions are said to be distinct if one cannot be represented as a positive multiple of the other
Theorem. polyhedrons extreme points/directions.
A polyhedron has a finite number of extreme points and extreme directions.
Theorem. optimal solution is extreme point.
Let P be a polyhedron. If the LP problem has finte optimal solutions, there there is an optimal solution that is an extreme point.
recession cone
Given a polyhedron {x∈ℝⁿ| Ax≤b} then the set {d∈ℝⁿ| Ad≤0, d≥0} is the recession cone
How to find extreme directions
find the extreme points of the recessions cone
Minkowskis Theorem
Given a polyhedron {x∈ℝⁿ| Ax≤b} is non empty and rank(a)=n, then
P = {x: x = Σλⱼxʲ + Σµᵢdᶦ ,
where Σλⱼ =1, λⱼ≥0 , j = 1,…,k, Σµᵢ≥0, i=1,…,l}
where xs are extreme points and ds are extreme directions
