convex analysis

Question 1

Hyperplane

Answer 1

H = {x∈ℝⁿ|cᵀx = β}

Question 2

The hyperplane

Answer 2

separates ℝⁿ into two halves

Question 3

convex combination

Answer 3

if the sum of the lambdas is 1 and v can be written as a linear combination of us with lambdas

Question 4

polyhedron

Answer 4

{x∈ℝⁿ| Ax≤b}

Question 5

bounded polyhedron

Answer 5

polytop

Question 6

convex

Answer 6

A set is convex if the segment αx* + (1-α)x̄ where α∈[0,1] is contained in the set

Question 7

Any hyperplanes and its halfspaces is…

Answer 7

convex

Question 8

The intersection of convex sets…

Answer 8

is convex

Question 9

A polyhedron is…

Answer 9

convex

Question 10

cone

Answer 10

A set C is called a cone if x∈C implies λx∈C for all λ greater than or equal to 0.

Question 11

convex cone

Answer 11

a cone and a convex set

Question 12

a polyhedron is a cone if it can be represented as

Answer 12

P={x: Ax≤0} for some matrix A.

Question 13

convex function

Answer 13

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]

Question 14

a convex function is convex if for….

Answer 14

every segment between to points the line is above the graph line

Question 15

The objective function is…

Answer 15

convex

Question 16

extreme point

Answer 16

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)

Question 17

ray

Answer 17

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.

Question 18

direction

Answer 18

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

Question 19

how to find the direction of a set

Answer 19

1. let x be an arbitray fixed feasible point
2. The d is a a direction iff x+λd∈X for all λ greater than or equal to 0.
3. 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.

Question 20

extreme direction

Answer 20

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.

Question 21

distinct directions

Answer 21

two directions are said to be distinct if one cannot be represented as a positive multiple of the other

Question 22

Theorem. polyhedrons extreme points/directions.

Answer 22

A polyhedron has a finite number of extreme points and extreme directions.

Question 23

Theorem. optimal solution is extreme point.

Answer 23

Let P be a polyhedron. If the LP problem has finte optimal solutions, there there is an optimal solution that is an extreme point.

Question 24

recession cone

Answer 24

Given a polyhedron {x∈ℝⁿ| Ax≤b} then the set {d∈ℝⁿ| Ad≤0, d≥0} is the recession cone

Question 25

How to find extreme directions

Answer 25

find the extreme points of the recessions cone

Question 26

Minkowskis Theorem

Answer 26

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