Operations research (Prof.ssa Palagi) - Appunti

General Definitions and Theorems

• Hyper-planes

  L_H = { x ∈ ℝⁿ : a^Tx = b }

  ∀ℝ u, v ∈ H a^Tu - b = a^Tv - b

  → We can drop prove [u, w] ∈ H ≡ Hyper Plane is Convex

  ∃z : (1-ρ)u + ρw

  We want to prove : a^Tz = b

  a^Tz = (1-ρ)a^Tu + ρa^Tw = (1-ρ)b + ρb = b

• Semi Spaces

  L_S = { x ∈ ℝⁿ : a^Tx ≤ b }

  S_s = { x ∈ ℝⁿ : a^Tx > b }

  We can drop prove [u, w] ∈ S^s ≡ Semi-Spaces are Convex

  a^Tz = (1-ρ)a^Tu + ρa^Tw ≤ (1-ρ)b + ρb = b

• Th. "The intersection of convex sets is convex"

  S = ⋂ S_i is Convex

  Proof:

  X = X₁ ∩ X₂ → ∀x₁, x₂ ∈ X → x₁y ∈ X₁ ∧ x₁y ∈ X₂

  But x₁, x₂ convex

  → [x₁, x₂] ⊆ X₁ → [x₁, x₂] ⊆ X → X is convex

• Th. "A convex problem only admits global solution or no solution."

  Proof:

  Reduction ad absurdum :

  ∃ x^* GLOBAL SOL. with x^* ≠ x^ˆ and F(x^*) < F(x^ˆ)

  ∃ x^ˆ LOCAL SOL.

  IF Z = [x^*, x^ˆ]

  ⇒ F(Z) = F((1-ρ)x^ˆ + ρx^*) ≤ (1-ρ)F(x^ˆ) + ρF(x^*) = F(x^ˆ) + ρ(F(x^*) - F(x^ˆ)) = F(x^ˆ) - δ

  ⇒ F(Z) ≤ F(x^ˆ), ∀β ⇒ ∄ N(x^ˆ, ρ) ⊆ loc. min ⇒ ABSURDUM.

General Definitions and Theorems

• Hyper-planes
• L = H = {x ∈ Rⁿ : a^Tx = b}

∀ R u, v, w ∈ H ⟺ a^Tu = b

a^Tv = b

• We can drop prove [τu, w] ∈ H ⟺ Hyper Plane is Convex

∃ z = (1-ρ)u + ρw

We want to prove: a^Tz = b

a^Tz = (1-ρ)a^Tu + ρa^Tw = (1-ρ)b + ρb = b

• Semi Spaces
• S⁺ = {x ∈ Rⁿ: a^Tx > b}
• S^- = {x ∈ Rⁿ: a^Tx < b}
• We can drop prove [τu, w] ⊆ S⁺ ⟺ Semi-Spaces are Convex

a^Tz = (1-ρ)a^Tu + ρa^Tw ≤ (1-ρ)b + ρb = b

• Th. “The intersection of convex sets is convex”
• S = ⋂ S_i is Convex

Proof:

Let X = X₁ ∩ X₂ ⟹ ∀ x₁, y ∈ X ⟹ x_j ∈ X_i ∀ j ∈ X_i

But x_i, x₂ convex

⟹ [x₁, x_j ] ⊆ X₂ ⟹ [x₁, y ] ⊆ X ⟹ X is convex

• Th. “A convex problem only admits global solution or no solution”.

Proof:

Reduction ad absurdum: ∃ x^* GLOBAL SOL. with x^* ≠ x̂ and f(x̂) < f(x)

∃ x̂ LOCAL SOL.

∃Z = [x̂, x^*]

∴ f(Z) = f((1-ρ)x̂, ρx^*) ≤ (1-ρ)f(x̂) + ρ f(x^*) =

= f(x̂) + ρ (f(x^*) - f(x̂))

= lowering

⇒ f(Z) ≤ f(x̂) ∀β ⇒ ∄ (x̂, ρ) ⊆ loc.min ⇒ Absurdum

Taylor Expansion

In R : f(x+s) = f(x) + df(x)_s + ¹⁄₂ d²f(x)_s² + O(s³)

In Rⁿ : f(x+s) = f(x) + ∇f(x)_s + ¹⁄₂ s^T ∇²f(x)_s + O(||s||³)

Conditions for Convexity

I Order Condition : [ F convex ⇔ F(y) > F(x) + ∇F(x)_(y-x) ]

II Order Condition : [ F convex ⇔ ∇²f(x) > 0 ]

→ non strict when ∇F = 0

Th: "Absence of interval optimum for CONCAVE F."

IF F sol. x^* ∃ x^* on F(x) lays on the boundary

Proof:

Let’s assume the existence of a solution x^*∊S ⇒ F(x^*) > F(x), ∀x∊S

⇒ ∃ z ∊ S : F(x^*) = F(x)

Let's now consider an internal point z∊Í̊ and N(z,p)⊂S

On the straight line for z and x we can find y∊N(z,p):

z∊[x,y]

⇒ ∃ λ∊[0,y] : z = (1-λ)x + λy

F(z)≥(1-λ)F(x) + λF(y) ≳ (1-λ)F(x^*) + λF(x^*) = F(x^*)

⇒ F(z) > F(x^*) ⇒ cannot exist on internal optimum

Constrained Optimization

• Descent Direction in _x

  d is ∼ f ^{xmax} f(x_k+td) < f(x), ∀ t ∈ (0,t_k^max]

  Characterization:

  f(x_k+td) = f(x_k) + t∇f(x)^T d + o(t), ∼ f(x+t)−f(x) = t∇f(x)^Td+o(t)

  Fast small d if ∇f(x)^Td