Optimizare convexă

Problemele convexe au o singură vale. Rețelele neuronale au milioane. Este important să cunoașteți diferența.

Tip: Construire Limbaj: Python Cerințe preliminare: Faza 1, lecțiile 04 (Calcul diferențial și integral pentru învățarea automată), 08 (Optimizare) Durată: ~90 de minute

Obiective de învățare

• Testarea convexității unei funcții folosind definiția, derivata a doua și criteriul Hessianei
• Implementarea metodei lui Newton și compararea convergenței sale pătratice cu cea a coborârii pe gradient
• Rezolvarea problemelor de optimizare cu restricții folosind multiplicatori Lagrange și interpretarea condițiilor KKT
• Explicarea motivului pentru care suprafețele de pierdere ale rețelelor neuronale sunt neconvexe, dar SGD găsește totuși soluții bune

Problema

În lecția 08 ați învățat despre coborârea pe gradient, momentum și Adam. Acești optimizatori coboară pe orice suprafață, dar nu oferă garanții în general. Pe un peisaj neconvex, coborârea pe gradient poate ajunge într-un minim local slab, se poate bloca într-un punct de șa sau poate oscila la nesfârșit. Ați folosit-o oricum, deoarece rețelele neuronale sunt neconvexe și nu există o alternativă universală.

Multe probleme din învățarea automată sunt însă convexe: regresia liniară, regresia logistică, SVM-urile, LASSO și regresia Ridge. Pentru acestea există ceva mai puternic: optimizare cu garanții matematice. O problemă convexă are o singură vale. Orice algoritm care coboară în condiții corespunzătoare va ajunge la un minim global. Nu sunt necesare reporniri. Nici programe complicate pentru rata de învățare. Nici speranțe deșarte.

Înțelegerea convexității vă ajută în trei moduri. Mai întâi, vă arată când problema este ușoară (convexă) sau dificilă (neconvexă). În al doilea rând, vă oferă instrumente mai rapide pentru problemele convexe, precum metoda lui Newton. În al treilea rând, explică noțiuni întâlnite în întreaga învățare automată: regularizarea ca restricție, dualitatea din SVM-uri și motivul pentru care învățarea profundă funcționează în pofida încălcării tuturor proprietăților convenabile oferite de convexitate.

Notă tehnică a traducerii: convexitatea garantează că orice minim local este global, dar nu neapărat că minimizatorul este unic; pot exista regiuni plate cu mai multe soluții optime. Convergența coborârii pe gradient necesită, de asemenea, ipoteze despre funcție și o alegere adecvată a pasului.

Conceptul

Mulțimi convexe

O mulțime S este convexă dacă, pentru oricare două puncte din S, întregul segment de dreaptă dintre ele se află tot în S.

Mulțimi convexe	Mulțimi neconvexe
Dreptunghi: oricare două puncte din interior pot fi unite printr-un segment care rămâne în interior	Stea/semilună: dreapta dintre două puncte interioare poate ieși din mulțime
Triunghi: aceeași proprietate este valabilă pentru toate punctele interioare	Inel: gaura face ca unele segmente să iasă din mulțime
Segmentul dintre oricare două puncte rămâne în mulțime	Segmentul dintre anumite perechi de puncte iese din mulțime

Testul formal: pentru orice puncte x, y din S și orice t din [0, 1], punctul tx + (1-t)y aparține, de asemenea, lui S.

Exemple de mulțimi convexe:

• O dreaptă, un plan, întregul R^n
• O bilă (disc, sferă, hipersferă)
• Un semispațiu: {x : a^T x <= b}
• Intersecția oricărui număr de mulțimi convexe

Exemple de mulțimi neconvexe:

• Un inel
• Reuniunea a două discuri disjuncte
• Orice mulțime cu o „adâncitură” sau o „gaură”

Funcții convexe

O funcție f este convexă dacă domeniul său este o mulțime convexă și, pentru oricare două puncte x, y din domeniu și orice t din [0, 1]:

f(tx + (1-t)y) <= t*f(x) + (1-t)*f(y)

Geometric, segmentul dintre oricare două puncte de pe grafic se află deasupra graficului sau pe acesta.

Proprietate	Funcție convexă	Funcție neconvexă
Testul segmentului	Dreapta dintre oricare două puncte de pe grafic se află deasupra curbei sau pe aceasta	Dreapta dintre anumite puncte de pe grafic coboară sub curbă
Formă	Un singur bol/o singură vale, curbată în sus	Mai multe vârfuri și văi, cu curbură mixtă
Minime locale	Fiecare minim local este un minim global	Pot exista mai multe minime locale la înălțimi diferite

Funcții convexe frecvente:

• f(x) = x^2 (parabolă)
• f(x) = |x| (valoare absolută)
• f(x) = e^x (exponențială)
• f(x) = max(0, x) (ReLU, deși este liniară pe porțiuni)
• f(x) = -log(x) pentru x > 0 (logaritm negativ)
• Orice funcție liniară f(x) = a^T x + b (atât convexă, cât și concavă)

Testarea convexității

Trei teste practice, de la cel mai simplu la cel mai riguros.

Testul 1: testul derivatei a doua (1D). Dacă f’’(x) >= 0 pentru orice x, atunci f este convexă.

• f(x) = x^2: f’’(x) = 2 >= 0. Convexă.
• f(x) = x^3: f’’(x) = 6x. Negativă pentru x < 0. Neconvexă.
• f(x) = e^x: f’’(x) = e^x > 0. Convexă.

Testul 2: testul Hessianei (caz multivariat). Dacă matricea Hessiană H(x) este pozitiv semidefinită pentru orice x, atunci f este convexă. Hessiana este matricea derivatelor parțiale de ordinul al doilea.

Testul 3: testul definiției. Verificați direct inegalitatea f(tx + (1-t)y) <= t*f(x) + (1-t)*f(y). Este util pentru funcțiile ale căror derivate sunt dificil de calculat.

Notă tehnică a traducerii: criteriile cu derivata a doua și Hessiana se aplică funcțiilor suficient de diferențiabile pe un domeniu convex adecvat. Testul definiției rămâne criteriul general și acoperă și funcții nediferențiabile precum |x|.

De ce contează convexitatea

Teorema centrală a optimizării convexe:

Pentru o funcție convexă, fiecare minim local este un minim global.

Prin urmare, coborârea pe gradient nu este prinsă într-un minim local suboptimal. Cu ipotezele și pasul potrivite, algoritmul converge la o soluție optimă.

Consecințe:

• Nu sunt necesare reporniri aleatoare
• Nu sunt necesare programe sofisticate pentru rata de învățare
• Sunt posibile demonstrații de convergență (rata depinde de proprietățile funcției)
• Soluția este unică, cu excepția eventualelor regiuni plate

Probleme convexe și neconvexe în învățarea automată

Problemă	Convexă?	Motiv
Regresie liniară (MSE)	Da	Pierderea este pătratică în ponderi
Regresie logistică	Da	Pierderea logaritmică este convexă în ponderi
SVM (pierderea hinge)	Da	Maximul funcțiilor liniare
LASSO (regresie L1)	Da	Suma funcțiilor convexe este convexă
Regresie Ridge (L2)	Da	Pătratică + pătratică = convexă
Rețea neuronală (orice pierdere)	Nu	Activările neliniare creează un peisaj neconvex
Clusterizare k-means	Nu	Pasul discret de atribuire
Factorizare matricială	Nu	Produsul necunoscutelor

Modelele liniare cu pierderi convexe sunt convexe. De îndată ce adăugați straturi ascunse cu activări neliniare, convexitatea dispare.

Notă tehnică a traducerii: rândul despre „orice” rețea neuronală este prea general. Un model neuronal liniar fără straturi ascunse poate conduce la o problemă convexă pentru o pierdere potrivită; neconvexitatea apare în mod obișnuit la rețelele multistrat parametrizate neliniar.

Matricea Hessiană

Hessiana H a unei funcții f: R^n -> R este matricea n x n a derivatelor parțiale de ordinul al doilea.

H[i][j] = d^2 f / (dx_i dx_j)

Pentru f(x, y) = x^2 + 3xy + y^2:

df/dx = 2x + 3y       d^2f/dx^2 = 2      d^2f/dxdy = 3
df/dy = 3x + 2y       d^2f/dydx = 3      d^2f/dy^2 = 2

H = [ 2  3 ]
    [ 3  2 ]

Hessiana oferă informații despre curbura locală:

• Toate valorile proprii sunt pozitive: funcția are curbură pozitivă în orice direcție; dacă gradientul este zero, punctul este un minim local strict
• Toate valorile proprii sunt negative: funcția are curbură negativă în orice direcție; dacă gradientul este zero, punctul este un maxim local strict
• Semne mixte: dacă gradientul este zero, punctul este un punct de șa (curbură ascendentă în unele direcții și descendentă în altele)
• Valoare proprie zero: testul de ordinul al doilea nu oferă o concluzie în acea direcție; aceasta nu este neapărat plată dincolo de ordinul al doilea

Pentru convexitate, Hessiana trebuie să fie pozitiv semidefinită (toate valorile proprii >= 0) peste tot, nu doar într-un singur punct.

Notă tehnică a traducerii: originalul deduce un maxim local sau un punct de șa numai din semnele valorilor proprii și echivalează o valoare proprie zero cu o direcție plată. Clasificarea extremelor necesită și un punct staționar, iar o curbură de ordinul al doilea egală cu zero poate ascunde termeni de ordin superior; de exemplu, f(x) = x^4 are derivata a doua zero în origine, fără să fie constantă în jurul ei.

Metoda lui Newton

Coborârea pe gradient folosește informații de ordinul întâi (gradientul). Metoda lui Newton folosește informații de ordinul al doilea (Hessiana). Ea aproximează funcția printr-o formă pătratică în punctul curent și sare direct la minimul acestei aproximări.

Regula de actualizare:
  x_new = x - H^(-1) * gradient

Comparație cu coborârea pe gradient:
  x_new = x - lr * gradient

Metoda lui Newton înlocuiește rata de învățare scalară cu inversa Hessianei. Astfel ajustează automat mărimea și direcția pasului în funcție de curbura locală.

Avantaje:

• Convergență pătratică în apropierea minimului (eroarea se ridică la pătrat la fiecare pas)
• Nu are o rată de învățare de reglat în forma clasică
• Este invariantă la scară (funcționează indiferent de parametrizarea problemei, pentru transformări afine nesingulare)

Dezavantaje:

• Calcularea Hessianei costă O(n^2) memorie, iar inversarea ei costă O(n^3)
• Pentru o rețea neuronală cu 1 milion de ponderi, aceasta înseamnă 10^12 elemente și 10^18 operații
• Nu este practică pentru învățarea profundă

Notă tehnică a traducerii: metoda Newton pură are convergență pătratică numai local și sub condiții de regularitate. Departe de minim, Hessiana poate fi singulară sau indefinită, iar pasul poate crește funcția; implementările robuste folosesc amortizare, căutare liniară ori regiuni de încredere.

Optimizare cu restricții

Optimizare fără restricții: minimizați f(x) peste toate valorile x. Optimizare cu restricții: minimizați f(x) în condițiile unor restricții.

Problemele reale au restricții. Doriți să minimizați costul, dar bugetul este limitat. Doriți să minimizați eroarea, dar complexitatea modelului este mărginită.

Multiplicatori Lagrange

Metoda multiplicatorilor Lagrange introduce Lagrangianul și transformă condiția de optimalitate cu restricții într-un sistem de ecuații de staționaritate și fezabilitate.

Problema: minimizați f(x) cu restricția g(x) = 0.

Procedura: introduceți o variabilă nouă (multiplicatorul Lagrange lambda) și formați Lagrangianul:

L(x, lambda) = f(x) + lambda * g(x)

În condiții de regularitate, o soluție locală satisface:

dL/dx = df/dx + lambda * dg/dx = 0
dL/dlambda = g(x) = 0

Notă tehnică a traducerii: originalul prezintă metoda drept o minimizare neconstrânsă în (x, lambda). În general, Lagrangianul are un punct de șa: se minimizează față de variabilele primale și se maximizează față de variabilele duale. Minimizarea simultană față de lambda este nemărginită ori de câte ori g(x) != 0.

Intuiție geometrică: în minimul cu restricții, gradientul lui f trebuie să fie paralel cu gradientul restricției g. Dacă nu ar fi paralele, v-ați putea deplasa de-a lungul suprafeței restricției pentru a reduce și mai mult f.

Exemplu: minimizați f(x,y) = x^2 + y^2 cu restricția x + y = 1.

L = x^2 + y^2 + lambda(x + y - 1)

dL/dx = 2x + lambda = 0  =>  x = -lambda/2
dL/dy = 2y + lambda = 0  =>  y = -lambda/2
dL/dlambda = x + y - 1 = 0

Din primele două ecuații: x = y
Prin substituție: 2x = 1, deci x = y = 0.5, lambda = -1

Punctul de pe dreapta x + y = 1 aflat cel mai aproape de origine este (0.5, 0.5).

Condițiile KKT

Condițiile Karush-Kuhn-Tucker extind multiplicatorii Lagrange la restricții de tip inegalitate.

Problema: minimizați f(x) cu restricțiile g_i(x) <= 0 pentru i = 1, …, m.

Condițiile KKT (necesare pentru optimalitate):

1. Staționaritate:    df/dx + sum(lambda_i * dg_i/dx) = 0
2. Fezabilitate primală:  g_i(x) <= 0  pentru orice i
3. Fezabilitate duală:    lambda_i >= 0  pentru orice i
4. Complementaritate:  lambda_i * g_i(x) = 0  pentru orice i

Complementaritatea este ideea-cheie: fie restricția este activă (g_i = 0, deci soluția se află pe frontieră), fie multiplicatorul este zero (restricția nu influențează soluția). O restricție care nu afectează soluția are lambda = 0.

Condițiile KKT sunt esențiale pentru SVM-uri. Vectorii suport sunt punctele de date în care restricția este activă (lambda > 0). Toate celelalte puncte au lambda = 0 și nu influențează frontiera de decizie.

Notă tehnică a traducerii: condițiile KKT sunt necesare sub o calificare adecvată a restricțiilor. Pentru probleme convexe, ele devin și suficiente în condițiile standard corespunzătoare.

Regularizarea ca optimizare cu restricții

Regularizările L1 și L2 nu sunt trucuri arbitrare. Ele sunt probleme de optimizare cu restricții prezentate într-o altă formă.

Regularizare L2 (Ridge):

minimizați  Loss(w)  cu restricția  ||w||^2 <= t

Forma echivalentă fără restricție:
minimizați  Loss(w) + lambda * ||w||^2

Restricția ||w||^2 <= t definește o bilă (disc în 2D, sferă în 3D). Soluția se află acolo unde curbele de nivel ale pierderii ating pentru prima dată această bilă.

Regularizare L1 (LASSO):

minimizați  Loss(w)  cu restricția  ||w||_1 <= t

Forma echivalentă fără restricție:
minimizați  Loss(w) + lambda * ||w||_1

Restricția ||w||_1 <= t definește un romb (un pătrat rotit în 2D).

Proprietate	Restricție L2 (cerc)	Restricție L1 (romb)
Forma restricției	Cerc (sferă în dimensiuni mai mari)	Romb (pătrat rotit în 2D)
Locul în care atinge curba de nivel a pierderii	Frontieră netedă — orice punct de pe cerc	Colț — aliniat cu o axă
Comportamentul soluției	Ponderile sunt mici, dar nenule	Unele ponderi sunt exact zero (soluție rară)
Rezultat	Micșorarea ponderilor	Selectarea caracteristicilor

Aceasta explică de ce L1 produce modele rare (selectarea caracteristicilor), în timp ce L2 doar micșorează ponderile. Rombul are colțurile aliniate cu axele. Curbele de nivel ale pierderii au șanse mai mari să atingă un colț, ceea ce face ca una sau mai multe ponderi să fie exact zero.

Notă tehnică a traducerii: formele cu restricție și cele penalizate sunt echivalente printr-o corespondență potrivită între t și lambda numai sub ipoteze adecvate; corespondența nu este neapărat unică în cazuri degenerate.

Dualitate

Fiecare problemă de optimizare cu restricții (problema primală) are o problemă însoțitoare (problema duală). Pentru problemele convexe care satisfac condiții de regularitate precum condiția Slater, valorile optime primală și duală coincid. Aceasta este dualitatea puternică.

Funcția duală lagrangiană:

Primală: minimizați f(x) cu restricția g(x) <= 0
Lagrangian: L(x, lambda) = f(x) + lambda * g(x)
Funcția duală: d(lambda) = min_x L(x, lambda)
Problema duală: maximizați d(lambda) cu restricția lambda >= 0

De ce contează dualitatea:

• Problema duală este uneori mai ușor de rezolvat decât cea primală
• SVM-urile sunt rezolvate în forma duală, în care problema depinde de produse scalare între punctele de date (ceea ce permite trucul nucleului)
• Problema duală oferă o limită inferioară pentru optimul primal, utilă la verificarea calității soluției

Pentru SVM-uri, în mod concret:

Primală: găsiți w, b care maximizează marginea 2/||w|| cu restricția
         y_i(w^T x_i + b) >= 1 pentru orice i

Duală:  maximizați sum(alpha_i) - 0.5 * sum_ij(alpha_i * alpha_j * y_i * y_j * x_i^T x_j)
        cu restricțiile alpha_i >= 0 și sum(alpha_i * y_i) = 0

Problema duală conține numai produsele scalare x_i^T x_j.
Înlocuiți x_i^T x_j cu K(x_i, x_j) pentru a obține trucul nucleului.

De ce funcționează învățarea profundă în pofida neconvexității

Funcțiile de pierdere ale rețelelor neuronale sunt profund neconvexe. După orice criteriu clasic, optimizarea lor ar trebui să eșueze. Totuși, coborârea stochastică pe gradient găsește în mod fiabil soluții bune. Mai mulți factori explică acest fenomen.

Majoritatea minimelor locale sunt suficient de bune. În spațiile cu multe dimensiuni, punctele critice aleatoare (în care gradientul este zero) sunt în mare parte puncte de șa, nu minime locale. Puținele minime locale existente tind să aibă valori ale pierderii apropiate de minimul global. Blocarea într-un minim local foarte slab este puțin probabilă atunci când spațiul parametrilor are milioane de dimensiuni.

Punctele de șa, nu minimele locale, sunt obstacolul real. Într-o funcție cu n parametri, un punct de șa are direcții de curbură atât pozitivă, cât și negativă. Pentru un punct critic aleatoriu dintr-un spațiu cu multe dimensiuni, probabilitatea ca toate cele n valori proprii să fie pozitive (minim local) este aproximativ 2^(-n). Aproape toate punctele critice sunt puncte de șa. Zgomotul din SGD ajută la evadarea din acestea.

Notă tehnică a traducerii: estimarea 2^(-n) este o euristică ce ar presupune, în esență, semne independente și echiprobabile ale valorilor proprii. Hessienele rețelelor neuronale nu satisfac în general această ipoteză, astfel încât afirmația nu trebuie interpretată ca probabilitate universală sau demonstrație formală.

Supraparametrizarea netezește peisajul. Rețelele cu mai mulți parametri decât exemple de antrenare au suprafețe de pierdere mai netede și mai conectate. Rețelele mai late au mai puține minime locale slabe. Rezultatul este contraintuitiv, dar coerent cu observațiile empirice.

Notă tehnică a traducerii: afirmația originală nu este o consecință universală a simplului fapt că numărul parametrilor depășește numărul exemplelor. Conectivitatea minimelor și absența barierelor nefavorabile au fost demonstrate numai pentru anumite arhitecturi, funcții de pierdere și regimuri de lățime; supraparametrizarea singură nu garantează un peisaj neted.

Structura peisajului pierderii:

Proprietate	Spațiu cu puține dimensiuni	Spațiu cu multe dimensiuni
Peisaj	Multe vârfuri și văi izolate	Văi conectate lin
Minime	Multe minime locale izolate	Puține minime locale slabe; majoritatea sunt aproape optime
Navigare	Minimul global este greu de găsit	Multe trasee duc la soluții bune
Puncte critice	Amestec de minime locale și puncte de șa	Predomină covârșitor punctele de șa, nu minimele locale

Zgomotul stochastic acționează ca regularizare implicită. SGD cu miniloturi adaugă zgomot, ceea ce împiedică stabilizarea în minime ascuțite. Minimele ascuțite supraînvață; cele plate generalizează. Zgomotul orientează optimizarea către regiuni plate ale peisajului pierderii.

Notă tehnică a traducerii: legătura simplă „minim ascuțit = generalizare slabă” nu este invariantă la reparametrizare și nu constituie o regulă universală. Zgomotul SGD poate introduce o preferință implicită utilă, dar efectul depinde de arhitectură, parametrizare, dimensiunea minilotului și programul ratei de învățare.

Metode de ordinul al doilea în practică

Metoda Newton pură este nepractică pentru modelele mari. Mai multe aproximări fac utilizabile informațiile de ordinul al doilea.

L-BFGS (Limited-memory BFGS): aproximează inversa Hessianei folosind ultimele m diferențe de gradient. Necesită O(mn) memorie în loc de O(n^2) și a fost concepută pentru probleme de optimizare la scară mare. Utilitatea practică depinde de costul evaluării funcției și gradientului, de proprietățile problemei și de căutarea liniară. Este folosită în învățarea automată clasică (regresie logistică, CRF-uri), dar mai rar în învățarea profundă la scară mare.

Notă tehnică a traducerii: pragul de aproximativ 10.000 de parametri din original nu este o limită a algoritmului. L-BFGS poate fi aplicată și problemelor cu mult mai multe variabile; limita efectivă este determinată de memorie, costul funcției, condiționare și implementare.

Gradientul natural: folosește matricea de informație Fisher (Hessiana așteptată a log-verosimilității, cu convenția de semn adecvată) în locul Hessianei standard. Astfel ține cont de geometria distribuțiilor de probabilitate. K-FAC (Kronecker-Factored Approximate Curvature) aproximează matricea Fisher prin produse Kronecker, ceea ce o face practică pentru rețele neuronale.

Optimizare fără Hessiană: folosește metoda gradientului conjugat pentru a rezolva Hx = g fără a forma vreodată H. Necesită numai produse Hessiană-vector, care pot fi calculate în timp O(n) prin diferențiere automată pentru o singură evaluare, până la constantele costului modelului.

Aproximări diagonale: momentul al doilea din Adam este uneori interpretat euristic drept informație diagonală despre curbură. AdaHessian extinde această idee folosind elemente diagonale efective ale Hessianei prin estimatorul Hutchinson.

Notă tehnică a traducerii: Adam estimează media mobilă a pătratelor gradienților, nu diagonala Hessianei. Cele două mărimi pot fi corelate în anumite contexte, dar nu sunt în general egale; clasificarea lui Adam drept metodă de ordinul al doilea este doar o analogie.

Metodă	Memorie	Cost pe pas	Când se folosește
Coborâre pe gradient	O(n)	O(n)	Referință, modele mari
Metoda lui Newton	O(n^2)	O(n^3)	Probleme convexe mici
L-BFGS	O(mn)	O(mn)	Probleme convexe medii
Adam	O(n)	O(n)	Alegerea implicită pentru învățarea profundă
K-FAC	O(n)	O(n) pe strat	Cercetare, antrenare cu miniloturi mari

Notă tehnică a traducerii: complexitatea K-FAC depinde de dimensiunile straturilor și de factorizarea folosită; memoria și costul nu sunt universal O(n), chiar dacă sunt mult sub costul Hessianei dense în aplicațiile vizate.

convex-vs-nonconvex

Construiți

Pasul 1: verificator de convexitate

Construiți o funcție care testează empiric convexitatea prin eșantionarea unor puncte și verificarea definiției.

import random
import math

def check_convexity(f, dim, bounds=(-5, 5), samples=1000):
    violations = 0
    for _ in range(samples):
        x = [random.uniform(*bounds) for _ in range(dim)]
        y = [random.uniform(*bounds) for _ in range(dim)]
        t = random.uniform(0, 1)
        mid = [t * xi + (1 - t) * yi for xi, yi in zip(x, y)]
        lhs = f(mid)
        rhs = t * f(x) + (1 - t) * f(y)
        if lhs > rhs + 1e-10:
            violations += 1
    return violations == 0, violations

Notă tehnică a traducerii: acest verificator poate demonstra empiric neconvexitatea dacă găsește o încălcare, dar absența încălcărilor într-un eșantion finit nu demonstrează convexitatea pe întregul domeniu.

Pasul 2: metoda lui Newton în 2D

Implementați metoda lui Newton folosind o Hessiană explicită. Comparați viteza de convergență cu cea a coborârii pe gradient.

def newtons_method(f, grad_f, hessian_f, x0, steps=50, tol=1e-12):
    x = list(x0)
    history = [x[:]]
    for _ in range(steps):
        g = grad_f(x)
        H = hessian_f(x)
        det = H[0][0] * H[1][1] - H[0][1] * H[1][0]
        if abs(det) < 1e-15:
            break
        H_inv = [
            [H[1][1] / det, -H[0][1] / det],
            [-H[1][0] / det, H[0][0] / det],
        ]
        dx = [
            H_inv[0][0] * g[0] + H_inv[0][1] * g[1],
            H_inv[1][0] * g[0] + H_inv[1][1] * g[1],
        ]
        x = [x[0] - dx[0], x[1] - dx[1]]
        history.append(x[:])
        if sum(gi ** 2 for gi in g) < tol:
            break
    return history

Pasul 3: rezolvarea cu multiplicatori Lagrange

Rezolvați optimizarea cu restricții aplicând coborârea pe gradient asupra variabilelor primale și ascensiunea asupra multiplicatorului din Lagrangian.

def lagrange_solve(f_grad, g_val, g_grad, x0, lr=0.01,
                   lr_lambda=0.01, steps=5000):
    x = list(x0)
    lam = 0.0
    history = []
    for _ in range(steps):
        fg = f_grad(x)
        gv = g_val(x)
        gg = g_grad(x)
        x = [
            xi - lr * (fgi + lam * ggi)
            for xi, fgi, ggi in zip(x, fg, gg)
        ]
        lam = lam + lr_lambda * gv
        history.append((x[:], lam, gv))
    return history

Notă tehnică a traducerii: actualizarea afișată este o schemă primal-duală simplă, nu o coborâre în toate variabilele Lagrangianului: pentru o restricție de egalitate, lambda este actualizat prin ascensiune. Convergența ei nu este garantată pentru orice problemă și orice rată de învățare.

Pasul 4: comparați metodele de ordinul întâi și al doilea

Rulați coborârea pe gradient și metoda lui Newton pe aceeași funcție pătratică. Numărați pașii până la convergență.

def quadratic(x):
    return 5 * x[0] ** 2 + x[1] ** 2

def quadratic_grad(x):
    return [10 * x[0], 2 * x[1]]

def quadratic_hessian(x):
    return [[10, 0], [0, 2]]

Metoda lui Newton va converge într-un singur pas (este exactă pentru funcțiile pătratice cu Hessiană nesingulară). Coborârea pe gradient poate necesita numeroși pași, deoarece valorile proprii ale Hessianei diferă cu un factor de 5, ceea ce creează o vale alungită; numărul exact depinde de rata de învățare și de criteriul de oprire.

Folosiți

Analiza convexității se aplică direct atunci când alegeți modele și rezolvitoare pentru învățarea automată.

Pentru probleme convexe (regresie logistică, SVM-uri, LASSO):

• Folosiți rezolvitoare dedicate (liblinear, CVXPY, scipy.optimize.minimize cu method='L-BFGS-B')
• Așteptați-vă la o soluție globală; unicitatea necesită convexitate strictă sau condiții suplimentare
• Metodele de ordinul al doilea sunt practice și rapide

Pentru probleme neconvexe (rețele neuronale):

• Folosiți metode de ordinul întâi (SGD, Adam)
• Acceptați că soluția depinde de inițializare și de caracterul aleatoriu
• Folosiți supraparametrizarea, zgomotul și programele ratei de învățare ca forme de regularizare implicită
• Nu pierdeți timpul căutând minimul global. Un minim local bun este suficient.

from scipy.optimize import minimize

result = minimize(
    fun=lambda w: sum((y - X @ w) ** 2) + 0.1 * sum(w ** 2),
    x0=np.zeros(d),
    method='L-BFGS-B',
    jac=lambda w: -2 * X.T @ (y - X @ w) + 0.2 * w,
)

Notă tehnică a traducerii: fragmentul original folosește np.zeros(d), dar nu importă NumPy sub aliasul np în acest bloc. Rulat independent, va produce NameError; presupune existența anterioară a instrucțiunii import numpy as np, precum și a variabilelor X, y și d. Blocul executabil a fost păstrat exact.

Pentru SVM-uri, formularea duală vă permite să folosiți trucul nucleului:

from sklearn.svm import SVC

svm = SVC(kernel='rbf', C=1.0)
svm.fit(X_train, y_train)
print(f"Support vectors: {svm.n_support_}")

Exerciții

1. Galerie de convexitate. Testați convexitatea acestor funcții cu ajutorul verificatorului: f(x) = x^4, f(x) = sin(x), f(x,y) = x^2 + y^2, f(x,y) = x*y, f(x) = max(x, 0). Explicați de ce fiecare rezultat este logic.

2. Cursa dintre Newton și coborârea pe gradient. Rulați ambele metode pe f(x,y) = 50*x^2 + y^2, pornind din punctul (10, 10). De câți pași are nevoie fiecare pentru a ajunge la o pierdere < 1e-10? Ce se întâmplă cu coborârea pe gradient când crește numărul de condiționare (raportul dintre cea mai mare și cea mai mică valoare proprie a Hessianei)?

3. Geometria multiplicatorului Lagrange. Minimizați f(x,y) = (x-3)^2 + (y-3)^2 cu restricția x + 2y = 4. Verificați soluția confirmând că gradientul lui f este paralel cu gradientul lui g în punctul soluției.

4. Restricție de regularizare. Implementați optimizarea cu restricție L1: minimizați (x-3)^2 + (y-2)^2 cu restricția |x| + |y| <= 1. Arătați că soluția are o coordonată egală cu zero (raritate produsă de restricția în formă de romb).

5. Analiza valorilor proprii ale Hessianei. Calculați Hessiana funcției Rosenbrock în (1,1) și în (-1,1). Calculați valorile proprii în ambele puncte. Ce vă spun acestea despre curbura în minim, comparativ cu cea departe de el?

Termeni-cheie

Termen	Semnificație
Mulțime convexă	O mulțime în care segmentul dintre oricare două puncte ale mulțimii rămâne în interiorul ei
Funcție convexă	O funcție pentru care segmentul dintre oricare două puncte de pe grafic se află deasupra graficului sau pe acesta. Pentru funcții de două ori diferențiabile pe un domeniu convex adecvat, Hessiana este pozitiv semidefinită peste tot
Minim local	Un punct mai jos decât toate punctele din vecinătate. Pentru funcțiile convexe, fiecare minim local este global
Minim global	Cel mai jos punct al unei funcții pe întregul său domeniu
Matrice Hessiană	Matricea tuturor derivatelor parțiale de ordinul al doilea. Codifică informații despre curbură
Pozitiv semidefinită	O matrice ale cărei valori proprii sunt toate nenegative. Analogul multidimensional al condiției „derivata a doua >= 0”
Număr de condiționare	Raportul dintre cea mai mare și cea mai mică valoare proprie relevantă a Hessianei. Un număr mare înseamnă văi alungite și coborâre lentă pe gradient
Metoda lui Newton	Optimizator de ordinul al doilea care folosește inversa Hessianei pentru direcția și mărimea pasului. Are convergență pătratică în apropierea minimului, sub ipotezele necesare
Multiplicator Lagrange	Variabilă introdusă pentru a transforma o problemă de optimizare cu restricții într-un sistem staționar al Lagrangianului
Condiții KKT	Condiții necesare pentru optimalitate cu restricții de tip inegalitate, sub calificări adecvate. Generalizează multiplicatorii Lagrange
Complementaritate	La soluție, fie o restricție este activă, fie multiplicatorul ei este zero
Dualitate	Fiecare problemă cu restricții are o problemă duală lagrangiană însoțitoare; dualul oferă limite pentru problema primală
Dualitate puternică	Valorile optime primală și duală sunt egale. Este valabilă, de exemplu, pentru probleme convexe care satisfac condiția Slater
L-BFGS	Metodă aproximativă de ordinul al doilea care stochează ultimele m diferențe de gradient în locul Hessianei complete
Punct de șa	Punct în care gradientul este zero, dar care este minim în unele direcții și maxim în altele
Supraparametrizare	Folosirea unui număr de parametri mai mare decât numărul exemplelor de antrenare. Poate modifica geometria peisajului pierderii și reduce minimele locale slabe

Lecturi suplimentare

• Boyd & Vandenberghe: Convex Optimization — manualul standard, disponibil gratuit online
• Bottou, Curtis, Nocedal: Optimization Methods for Large-Scale Machine Learning (2018) — leagă teoria optimizării convexe de practica învățării profunde
• Choromanska et al.: The Loss Surfaces of Multilayer Networks (2015) — explică de ce peisajele neconvexe ale rețelelor neuronale nu sunt atât de problematice pe cât par
• Nocedal & Wright: Numerical Optimization — referință cuprinzătoare pentru metoda lui Newton, L-BFGS și optimizarea cu restricții

---

Sursă: Convex Optimization — original

Navigare: înapoi: 01.17 — Sisteme liniare · Faza 1 — Fundamente matematice · Catalog complet · în continuare: 01.19 — Numere complexe pentru inteligența artificială.