Analysis of different norms and corresponding Lipschitz constants for global optimization

Abstract

The paper discusses how the used norm and corresponding Lipschitz constant influence the speed of algorithms for global optimization. For this reason Lipschitz constants corresponding to different norms were estimated. Different test functions for global optimization were solved using branch‐and‐bound algorithm for Lipschitz optimization with different norms. Experiments have shown that the best results are achieved when combination of extreme (infinite and first) and sometimes Euclidean norms is used. Skirtingų normų ir jas atitinkančių lipšico konstantų analizė globaliai optimizacijai Santrauka Šiame darbe ištirta, kaip įvairios normos ir jas atitinkančios Lipšico konstantos veikia globalios optimizacijos algoritmų greičius. Šiam tikslui buvo įvertintos įvairias normas atitinkančios Lipšico konstantos. Šakų ir rėžių algoritmas buvo naudojamas globalaus maksimumo paieškai. Eksperimento rezultatai parodė, kad geriausi rezultatai gaunami, kai Lipšico viršutiniam rėžiui įvertinti naudojamas kraštinių (begalinės ir pirmosios) normų junginys dvimačiam atvejui ir jų junginys su euklidine norma trimačiam atvejui. Reikšminiai žodžiai: globali optimizacija, šakų ir rėžių algoritmas, Lipšico optimizacija, normos, Lipšico konstanta. First Published Online: 21 Oct 2010

Keywords

• global optimization
• branch-and-bound algorithms
• Lipschitz optimization
• different norms
• Lipschitz constant