azotaemia (mg/dl)

Wulff’s crystallographic shapes

Overlap

Separation

glycaem ia vs. azotaem ia

0 10 20 30 40 50 60 70 80 90

40 60 80 100 120 140

glycaemia (mg/dl)

azotaemia (mg/dl)

But what if a separation hyperplane does not exist?

How to measure overlap

glycaem ia vs. azotaem ia

0 10 20 30 40 50 60 70 80 90

40 60 80 100 120 140

glycaemia (mg/dl)

azotaemia (mg/dl)

conv(P’)

S = {x

, …, x

}

conv(S) = {x ∈ IR

: x =

x

+ … +

x

λ₁ + … + λ_s

= 1

λ_i

> 0}

S = {x

, …, x

}

conv(S) = {x ∈ IR

: x =

x

+ … +

x

λ₁ + … + λ_s

= 1

λ_i

> 0}

We can compute its implicit form conv(S) = {x ∈ IR

: Ax < b} by Fourier-Motzkin’s method

convex hull

How to measure overlap

glycaem ia vs. azotaem ia

0 10 20 30 40 50 60 70 80 90

40 60 80 100 120 140

glycaemia (mg/dl)

azotaemia (mg/dl)

A’x < b’

A”x < b”

Q

diam(Q) = max {d(x , y): x, y ∈ Q}

diam(Q) = max {d(x , y): x, y ∈ Q}

Q = {x ∈ IR

: A’x < b’, A”x < b”}

Q = {x ∈ IR

: Ax < b}

The overlap can be measured by the diameter of Q

How to measure overlap

Problem Compute the diameter of a polytope Q = {x ∈ IR

: Ax < b}

max Σ

^(x

^{– y}

⁾

i=1

a

x

+ a

x

+ … + a

x

< b

a

y

+ a

y

+ … + a

y

< b

i = 1, …, m

computing the diameter

diam(Q) = max {d(x , y): x, y ∈ Q}

diam(Q) = max {d(x , y): x, y ∈ Q}

Theorem Let f: Q → IR concave (convex) with Q polytope. Then there always

exists a vertex v

of Q such that f(v

) < f(x) (such that f(v

) > f(x))

for any x ∈ Q.

Convex and concave functions

Let f: IR

→ IR, and λ

, …, λ

> 0 such that

Σ ^λ

^{= 1. Let x}

^{, …, x}

^{∈ IR}

^.

f (x₂)

x₁ x₂

f (x₁)

x = λx₁ + (1 –λ)x₂ f (x)

λ f(x₁) + (1 – λ)f (x₂)

convex if

f ( Σ

λ

x

) < Σ

λ

f (x

)

Theorem Let f: Q → IR concave (convex) with Q polytope. Then there always exists a vertex v

of Q such that f(v

) < f(x) (such that f(v

) > f(x)) for any x ∈ Q.

We call f

Convex and concave functions

f (x₂)

x₁ x₂

f (x₁)

concave if instead f ( Σ

λ

x

) > Σ

λ

f (x

)

x = λx₁ + (1 – λ)x₂

f (x) λ f(x₁) + (1 –λ)f (x₂)

Let f: IR

→ IR, and λ

, …, λ

> 0 such that Σ ^λ

^{= 1. Let x}

^{, …, x}

^{∈ IR}

^.

We call f

convex if

f ( Σ

λ

x

) < Σ

λ

f (x

)

Theorem Let f: Q → IR concave (convex) with Q polytope. Then there always

exists a vertex v

of Q such that f(v

) < f(x) (such that f(v

) > f(x))

for any x ∈ Q.

Convex and concave functions

Theorem Let f: Q → IR concave (convex) with Q polytope. Then there always exists a vertex v

of Q such that f(v

) < f(x) (such that f(v

) > f(x)) for any x ∈ Q.

f (x)

v

, …, v

vertices of Q

x ∈ Q ⇔ x = Σ

v

q

i=1

with

> 0, Σ

= 1

q

i=1

f (x) = f ( Σ

v

) > Σ

f (v

) >

q

i=1

q

i=1

> Σ

min {f (v

)} = f (v

)

i = 1…q q

i=1

Q = conv{v

, …, v

}

Q

*

minimum point v^*

How to measure overlap

0 10 20 30 40 50 60 70 80 90

40 60 80 100 120 140

Q

The theorem says that diam(Q) is the distance between two vertices of Q but the vertices of Q are not necessarily members of the sample P = P’ ∪ P”

Saying it differently, it might well be Q

= conv(Q ∩ P) ⊂ Q

How to measure overlap

0 10 20 30 40 50 60 70 80 90

40 60 80 100 120 140

Q^*

Instead of diam(Q), let us measure overlap as the maximum distance d between the sample points which belong to Q

d

In altre parole, può darsi che Q

= conv(Q ∩ P) ⊂ Q

without having to compute conv(Q ∩ P) (Fourier-Motzkin’s method is extremely heavy) and having than to solve a quadratic problem

Knowing Q ∩ P one can compute d through

iterations

2

How to measure overlap

0 10 20 30 40 50 60 70 80 90

40 60 80 100 120 140

Q^*

Definition We say that x ∈ P’ is separable from P” if there exists a hyperplane H = {x ∈ IR

: ax = b} such that ax > b e ax

< b for any x

∈ P”

ax= b

x

How to measure overlap

0 10 20 30 40 50 60 70 80 90

40 60 80 100 120 140

Q^*

Definition We say that x ∈ P’ is separable from P” if there exists a hyperplane H = {x ∈ IR

: ax = b} uch that ax > b e ax

< b for any x

∈ P”

x

Teorema Siano N’, N” gli insiemi dei punti di P’, P” non separabili rispettiva mente da P”, P’. Allora P ∩ Q

= N’ ∪ N”

Theorem Let x ∈ P’ be separable from P”. Then x ∉ Q

.

Similarly, every x of P” separable from P’ does not belong to Q

.

N’ N”

How to measure overlap

Definition We say that x ∈ P’ is separable from P” if there exists a hyperplane H = {x ∈ IR

: ax = b} such that ax > b e ax

< b for any x

∈ P”

such that x = λ₁x¹ + … + λ_mx^m Then we could write _λ1ax¹ < _λ1b

…

λ_max^m < _λmb

a(λ₁x¹ + … + λ_mx^m) < (λ₁ + … + λ_m)b Hence x∉conv(P”)

Let x∈P’ – N’. Then there are a, b such that ax > b

ax^k < b for any x^k∈P”

Theorem Let x ∈ P’ be separable from P”. Then x ∉ Q

.

Similarly, every x of P” separable from P’ does not belong to Q

.

Let |P”| = m. If x ∈ conv(P”), there would be λ₁, …, λ_m > 0 with

Σ

m

i=1

that is ax < b

and, since Q^* ⊆ conv(P”), x∉Q^*

How to measure overlap

0 10 20 30 40 50 60 70 80 90

40 60 80 100 120 140

Q^*

• So, to decide whether a point of P’ (di P”) belongs or not to Q

, we check whether it is inseparable or not from P” (from P’)

• Once constructed P ∩ Q

, we compute its diameter by exhaustion

x

Checking if x is separable from P” (or from P’) is a linear programming problem

The objective chosen can be maximizing the violation by x