È una branca dell’algebra lineare che ci permette di semplificare tutti i concetti.

Intro dualità🟩

<img src="/images/notes/image/universita/ex-notion/Programmazione lineare/Untitled 8.png" alt="image/universita/ex-notion/Programmazione lineare/Untitled 8">
  • Si fa una sorta di trasposta alla matrice di A.
  • y è pari al numero di righe di A

La trasformazione al duale è molto facile, ed è abbastanza intuitiva una volta che capiamo che vogliamo andare a fare l’upper bound.

Dualità asimmetrica 🟥+

Teorema debole di dualità 🟩

  • Slide

    image/universita/ex-notion/Programmazione lineare/Untitled 9

Qui c’è una cosa simile a quanto fatto in MCMF, il cui massimo di x è boundato dal minimo del suo duale, in Tarjan e MCMF.

Corollari di dualità (2) 🟩

  • Slide

    image/universita/ex-notion/Programmazione lineare/Untitled 10
  1. il fatto che ci sia un bound a x, implica che se x è illimitato, non posso avere il bound!
  2. Abbiamo una condizione di ottimalità delle soluzioni trovate!

Def Direzioni ammissibili

Vogliamo trovare un modo per muoverci e trovare ancora una direzione ottimale!

Def: un vettore $\varepsilon \in \mathbb{R} ^n$ è una direzione ammissibile se esiste $\bar{\lambda} > 0$ tale che $x(\lambda) = x + \lambda \varepsilon$, per ogni $\lambda \in 0...\bar{\lambda}$

Intuizione Ossia se possiamo spostarci di almeno un pò verso la direzione che vogliamo!

Def direzione di crescita

Possiamo considerare una direzione di crescita $\lambda \iff cx(\lambda) = c \bar{x} + \lambda c\varepsilon > c \bar{x} \iff c\varepsilon > 0$

La cosa interessante è che una direzione di crescita cresce indipendentemente dal punto, questo è una proprietà molto forte della programmazione lineare! Questi due concetti sono molto utili perché una volta che abbiamo una direzione ammissibile e di crescita allora si può verificare che si può migliorare ancora la soluzione di x.

Suff e nec per direzione ammissibile

  • Slide image/universita/ex-notion/Programmazione lineare/Untitled 11

L’idea principale per questa dimostrazione è sui vincoli attivi, differenziare se una riga è un vincolo attivo o meno. Se lo è allora voglio che sia minore, altrimeni basta scegliere un intorno sufficientemente piccolo perché il vincolo è stretto.

Da notare che se non è un vincolo attivo allora ho una disuguaglianza stretta allora posso andare ad utilizzare cose di analisi

Ottimalità del punto

Dato un punto $x$ ammissibile, questo punto è ottimo sse non ci sono direzioni di crescita ammisibile

Intuizione sulla dimo

→ se è già ottimo allora se esistessa una direzione di crescita, si potrebbe far crescere ancora il nostro punto di ottimo, violando l’ipotesi di ottimalità

←Se non ho direzioni di crescita, supponendo per assurdo che non sia ottimo abbiamo allora possiamo trovare una direzione di crescita ammissibile, creando un assurdo, questa direzione la andiamo a trovare prendendo un punto ottimo e creando il vettore da questo punto a quello nostro iniziale.

  • Dimostrazione dispense

    !image/universita/ex-notion/Programmazione lineare/Untitled 12

Legendre Transform

This is also known as Conjugate function in Analisi di Convessità#Conjugate function.

Given a convex function $f$ the Legendre transform of this function $f$ is the function

$$ g(p) = \sup_{p} \left( px - f(x) \right) $$

This is used in Lagrangian Mechanics for the Eulero Lagrange, and one can see that its dual is the Hamiltonian Mechanics (but need to verify wait).

This has an easy geometrical interpretation, is just the maximum distance between the family of the lines through origin to a point of the function that is under the line. Duality Theory-20240716135207701 First image is the intuition of the Legendre transform (the straight line and the convex shape), the second image represents how an angle is converted to a segment thanks to this transform.

We note that $p = f'(x)$ because that is an extremum, this will be useful when we prove the involutivity.

Examples of Legendre transforms

One can see that $f(x) = x^{2}$ has $g(p) = \frac{1}{4}p^{2}$ as dual. $f(x) = \frac{mx^{2}}{2}$ has as dual $g(p) = \frac{p^{2}}{2m}$ $f(x) = \frac{x^{\alpha}}{\alpha}$ has as dual $g(p) = \frac{p^{\beta}}{\beta}$ where $\frac{1}{\alpha} + \frac{1}{\beta} = 1$.

You got the Idea.

Involutive property

The involutive property asserts that applying the Legendre transform twice gives back the original function.

If we set $G(x, p) = xp - g(p)$ we have by definition of $g(p)$ that $G(x, p) = f(x)$, we still need to prove that this is the maximum possible, so that we know that this is indeed the transform.

We can have an easy interpretation of reapplying this operator: we can observe that $xp$ is the line passing through the origin, and $g(p)$ is the distance to a point of the $f(x)$ and we know that this point is tangent. It is easy to observe that this point is exactly the $y$ of the point of $f(x)$ for a fixed $x$.

Young Duality

We say the $f, g$ that are one the Legendre Transform of the other are duals following Young’s definition. We have that $F(x, p) = px - f(x) \leq g(p)$ because $g(p)$ is the supremum. This follows that $px \leq f(x) +g(p)$ in any case.

AM-GM application

We can prove the classical AM-GM inequality in this way, by setting $f(x) = \frac{x^{2}}{2}$ and $g(p) = \frac{p^{2}}{2}$ we have that $px \leq \frac{x^{2}}{2} + \frac{p^{2}}{2}$.

Similarly we can prove that

$$ px \leq \frac{x^{\alpha}}{\alpha} + \frac{p^{\beta}}{\beta} $$

Where $\frac{1}{\alpha} + \frac{1}{\beta} = 1$ is valid.

Multi-variable Legendre

Given a convex function $f(x)$ (If you don’t remember see convexity), meaning that the input is a vector $(x_{1}, \dots, x_{n})$ and the quadratic form $\left\langle \frac{ \partial^{2} f }{ \partial x^{2} }dx, dx \right\rangle$ is positive definite (see Massimi minimi multi-variabile for positive definite matrices) then the Legendre transform is a function $g(\vec{p})$ where $\vec{p} = \left( p_{1}, \dots, p_{n} \right)$ such that everything done for the single case is valid:

$$ F(\vec{p}, x(\vec{p})) = max_{x}F(\vec{p}, \vec{x}), F(\vec{p}, \vec{x}) = (\vec{p}\cdot \vec{x} ) - f(\vec{x}), \vec{p} = \frac{ \partial f }{ \partial \vec{x} } $$

Every result of the above is still valid in this case.

Coincidence of specific points

We can prove that given $f(x)$ and his Legendre transform $g(p)$ then we have that $f(x) = g(p)$, which has a geometrical interpretation that $f(x)$ divides the straight line with a fixed $x$ from the $y=0$ to $y=px$ in half.

This proof is easy for the Euler’s lemma on homogeneous functions which states that

$$ \frac{ \partial f }{ \partial x } x = 2f $$

Which this in mind we can just do the following:

$$ g(p(x)) = px - f(x) = \frac{ \partial f }{ \partial x } x - f = 2f(x) - f(x) = f(x) $$

This will allow us to prove some relation between Lagrangian Mechanics and Hamiltonian Mechanics. In particular that $H = p\dot{q} - L = 2T - (T - U) = T + U$.

The Lagrangian

Moved to Lagrange Multipliers.