funzioni convesse lineari a tratti

(1)

Formulazione di problemi con valori assoluti

I

funzioni convesse lineari a tratti

I

problemi con valori assoluti

I

regressione lineare

rif. BT 1.3

(2)

Max di funzioni convesse

Teorema

Siano f

1

, . . . , f

m

: R

ⁿ

→ R funzioni convesse. Allora la funzione f (x) = max

_i=1,...,m

f

_i

(x) ` e convessa

Dimostrazione Siano x, y ∈ R

ⁿ

, λ ∈ [0, 1]. Si ha che:

f (λx + (1 − λ)y) = max

i=1,...,m

f

_i

(λx + (1 − λ)y)

≤ max

i=1,...,m

(λf

i

(x) + (1 − λ)f

i

(y))

≤ max

i=1,...,m

λf

i

(x) + max

i=1,...,m

(1 − λ)f

i

(y)

= λf (x) + (1 − λf (y))

(3)

Somma di funzioni convesse

Teorema

Siano f

1

, . . . , f

m

: R

ⁿ

→ R funzioni convesse. Allora la funzione f (x) = P

m

i=1

f

_i

(x) ` e convessa

Dimostrazione Proviamo il risultato per m = 2, il caso generale segue per induzione. Siano x, y ∈ R

ⁿ

, λ ∈ [0, 1]. Si ha che:

f (λx + (1 − λ)y) = f

1

(λx + (1 − λ)y) + f

2

(λx + (1 − λ)y)

≤ λf

₁

(x) + (1 − λ)f

1

(y) + λf

2

(x) + (1 − λ)f

2

(y)

= λf (x) + (1 − λf (y))

(4)

Funzioni convesse lineari a tratti

Una funzione del tipo max

i=1,...,m

(c

^T_i

x + d

i

) ` e detta funzione convessa lineare a tratti

c₁x + d₁

c₂x + d₂ c₃x + d₃

c₂x + d₂

x

f(x)

x

f (x) = |x| = max{x, −x}

(5)

Generalizzazione del problema di PL

min max

i=1,...,m

(c

^T_i

x + d

_i

) s.t. Ax ≥ b

Si osservi che max

_i=1,...,m

(c

^T_i

x + d

_i

) ` e uguale al minimo numero z che soddisfa z ≥ c

^T_i

x + d

_i

. Quindi, ` e equivalente al seguente problema di PL

min z

s.t. z ≥ c

^T_i

x + d

_i

Ax ≥ b

Allo stesso modo, un vincolo f (x) = max

i=1,...,m

(w

^T_i

x + g

i

) ≤ h pu` o essere sostituito dagli m vincoli

w

_i^T

x + g

i

≤ h, , i = 1, . . . , m

(6)

Problemi con valori assoluti

min X

i=1,...,n

c

_i

|x

_i

| s.t. Ax ≥ b in cui assumiamo c

_i

≥ 0.

Osserviamo che |x

_i

| `e pari al pi` u piccolo numero z

_i

tale che z

_i

≥ x

_i

e z

i

≥ −x

_i

. Quindi otteniamo il problema di PL equivalente:

min X

i=1,...,n

c

i

z

i

s.t. Ax ≥ b

z

i

≥ x

_i

z

_i

≥ −x

_i

(7)

Esercizio

min 2x

1

+ 3|x

2

− 10|

s.t. |x

₁

+ 2| + |x

2

| ≤ 5 riformulazione lineare:

min 2x

₁

+ 3z

₁

s.t. z

₂

+ z

₃

≤ 5

z

1

≥ x

₂

− 10

z

1

≥ −x

₂

+ 10

z

₂

≥ x

₁

+ 2

z

₂

≥ −x

₁

− 2

z

₃

≥ x

₂

z

3

≥ −x

₂

(8)

Esercizio

Consideriamo un problema della forma:

min c

^T

x + f (d

^T

x) s.t. Ax ≥ b

2 f(x)

x

−1 2

2 1

Osserviamo che f (x) = max{1 − x, 0, 2x − 4}. Quindi otteniamo la riformulazione lineare:

min c

^T

x + z

s.t. z ≥ −d

^T

x + 1

z ≥ 0

z ≥ 2d

^T

x − 4

Ax ≥ b

(9)

Regressione lineare

Nei problemi di classificazione un data-set composto da coppie (a

_i

, b

_i

), i = 1, . . . , m, in cui a

_i

∈ R

ⁿ

` e un’osservazione e b

_i

il corrispondente risultato.

Un modello di regressione lineare consiste in un vettore x (da determinare) per cui il risultato di una generica osservazione a possa rappresentarsi come b = a

^T

x

Tale vettore ` e scelto in modo da minimizzare l’errore sui campioni del data-set:

I

criterio I: minimizzare lo scarto massimo max

_i=1,...,m

|b

_i

− a

^T_i

x|

I

criterio II: minimizzare la somma degli scarti P

_m

i=1

|b

_i

− a

^T_i

x|

(10)

Regressione lineare: formulazione di PL

criterio I:

min z

s.t. z ≥ b

i

− a

^T_i

x, i = 1, . . . , m z ≥ −b

i

+ a

^T_i

x, i = 1, . . . , m criterio II:

min X

i=1,...,m

z

_i

s.t. z

i

≥ b

_i

− a

^T_i

x, i = 1, . . . , m

z

i

≥ −b

_i

+ a

^T_i

x, i = 1, . . . , m