En ny metode til at løse en række globale optimeringsproblemer udviklet

At skabe yderst effektive tekniske systemer og teknologiske processer, ud over brugen af ​​nye principper, nye materialer, nye fysiske effekter og andre løsninger, der bestemmer den overordnede struktur af det objekt, der skabes, forskere skal vælge den bedste kombination af objektets parametre (geometriske dimensioner, elektriske egenskaber, etc.), da eventuelle ændringer i parametrene med en fast overordnet objektstruktur kan påvirke effektivitetsindikatorerne markant.

I computerstøttet design, test af optioner kan udføres ved at analysere dens matematiske model for forskellige parameterværdier. Efterhånden som modellerne bliver mere og mere komplekse, opstår behovet for et målrettet valg af muligheder i jagten på den optimale (mest effektive) løsning.

Et team af forskere fra Lobachevsky State University of Nizhny Novgorod (UNN) ledet af professor Roman Strongin har studeret de målrettede valg, når de søger efter den optimale løsning. Det indebærer en analyse af en undergruppe af de mulige muligheder med det formål at udelukke åbenlyst lovende sager og koncentrere søgningen om den undergruppe, der indeholder den bedste løsning.

"Når matematiske modeller af de processer, der opstår i et objekt bliver mere komplicerede, effektivitetsegenskaberne vil ikke have egenskaben monotonitet, derfor er lokale søgemetoder utilstrækkelige til at vurdere den bedste løsning, " siger professor Roman Strongin.

De globale søgeprocedurer, der bruges i sådanne problemer (også kaldet multiekstremale optimeringsproblemer) sikrer, at søgningen er målrettet ved at tage hensyn til den begrænsede karakter af ændringen i objektets egenskaber, når ændringerne i dets parametre er begrænsede. Den resulterende matematiske formulering kan tage form af Lipschitz-tilstanden, den ensartede Hölder-tilstand, etc.

Multi-ekstrem optimeringsproblemer tilbyder et snævert omfang af analytiske forskningsmuligheder, og de bliver beregningsmæssigt dyre, når de søger numeriske løsninger, da beregningsomkostningerne vokser eksponentielt med den stigende dimension af problemet.

Ifølge Konstantin Barkalov, Lektor ved UNN-afdelingen for software og supercomputerteknologier, brugen af ​​moderne parallelle computersystemer udvider omfanget af globale optimeringsmetoder. Imidlertid, på samme tid, det stiller udfordringen ved effektivt at parallelisere søgeprocessen.

"Derfor bør hovedindsatsen på dette område koncentreres om at udvikle effektive parallelle metoder til numerisk løsning af multiekstrem optimeringsproblemer og skabe passende software til moderne computersystemer på basis af sådanne metoder, " siger Barkalov.

Som regel, metoderne til global optimering (både sekventiel og parallel) er beregnet til at løse et enkelt optimeringsproblem. For at løse en række q-problemer, problemerne i serien løses sekventielt, den ene efter den anden. Derfor, den optimale estimering i det i-te problem i serien forbliver udefineret, indtil alle foregående problemer i serien (med indekserne 1, 2, . . . , jeg ? 1) er blevet fuldstændig løst. I tilfælde af begrænsede beregningsressourcer, optima-estimaterne i problemerne i + 1, . . . , q vil ikke blive opnået, hvis beregningsressourcerne er opbrugt, mens det i-te problem løses.

Situationer, hvor en række q-problemer skal løses, er ikke ekstraordinære. For eksempel, en række skalære problemer opstår, når man søger et Pareto-sæt til at løse multi-objektive optimeringsproblemer. I dette tilfælde, løsningen af ​​et enkelt skalarproblem svarer til et af Pareto-optimale punkter i et multi-objektivt problem. En række optimeringsproblemer opstår også, når man bruger dimensionsreduktionsmetoder til at løse multidimensionelle optimeringsproblemer. Endelig, en række testproblemer kan også opnås ved hjælp af en bestemt testproblemgenerator.

Forskere mener, at når man løser en række problemer, det er nødvendigt at have første skøn over løsninger på alle problemer på én gang, således at det til enhver tid er muligt at vurdere hensigtsmæssigheden af ​​at fortsætte søgningen. I dette tilfælde, det er ønskeligt at have de optimale estimater for alle problemer med samme nøjagtighed.

At køre mange uafhængige processer i et parallelt computersystem, hver af processerne, der løser et problem fra en serie, har en række ulemper. Først, der vil opstå en ubalance i arbejdsbelastningen mellem processorerne. Hvis løsning af det i-te problem kræver betydeligt færre iterationer af metoden end at løse det j-te problem, den processor, der har til opgave at håndtere det i-te problem, forbliver inaktiv efter at have fuldført opgaven. Sekund, estimaterne af optima opnås med forskellig præcision i forskellige problemer. Enklere problemer vil blive løst med højere præcision, hvorimod præcisionen vil være lavere for mere komplekse problemer.

Formålet med forskningen udført på Lobachevsky University var at udvikle en ny metode til at løse en række globale optimeringsproblemer, der ville sikre:(i) en ensartet belastning af alle de anvendte kerner/processorer; (ii) en ensartet konvergens til løsningerne af alle problemer i serien.

I den teoretiske del af deres papir, UNN-forskere beviste også teoremet om ensartet konvergens af den nye algoritme. Den eksperimentelle del af arbejdet bestod i at løse en række af flere hundrede testproblemer af forskellige dimensioner, og resultaterne har overbevisende vist tilstedeværelsen af ​​ensartet konvergens.

Også UNN-forskere overvejer beregningsintensive globale optimeringsproblemer, til løsning af hvilke supercomputing-systemer med exaflops-ydelse kan kræves. For at overvinde en sådan beregningsmæssig kompleksitet, forskerne foreslår generaliserede parallelle beregningsskemaer, som kan involvere adskillige effektive parallelle algoritmer for global optimering. De foreslåede ordninger omfatter metoder til multilevel-dekomponering af parallelle beregninger for at garantere beregningseffektiviteten af ​​supercomputing-systemer med delte og distribuerede hukommelses-multiprocessorer, der bruger tusindvis af processorer til at imødegå globale optimeringsudfordringer.