Algoritmen en methoden voor onvoorwaardelijke optimalisatie. Methoden voor onvoorwaardelijke en voorwaardelijke optimalisatie
Optimalisatie is het proces van het vinden van een uiterste (globaal maximum of minimum) van een bepaalde functie of het kiezen van de beste (optimale) optie uit een verscheidenheid aan mogelijke. De meest betrouwbare manier om de beste optie te vinden is een vergelijkende beoordeling van alle mogelijke opties (alternatieven). Als het aantal alternatieven groot is, worden meestal wiskundige programmeermethoden gebruikt om de beste te vinden. Deze methoden kunnen worden toegepast als er een strikte probleemstelling is: een set variabelen is ingesteld, het gebied van hun mogelijke verandering is ingesteld (beperkingen zijn ingesteld) en het type doelfunctie (de functie waarvan het uiterste moet worden gevonden) van deze variabelen wordt bepaald. Dit laatste is een kwantitatieve maat (criterium) om de mate van realisatie van het doel te beoordelen.
Het probleem van onbeperkte optimalisatie is om het minimum of maximum van een functie te vinden zonder enige beperking. Ondanks het feit dat de meeste praktische optimalisatieproblemen beperkingen hebben, is de studie van onbeperkte optimalisatiemethoden vanuit verschillende gezichtspunten belangrijk. Veel algoritmen voor het oplossen van een beperkt probleem houden in dat het wordt teruggebracht tot een reeks onbeperkte optimalisatieproblemen. Een andere klasse van methoden is gebaseerd op het vinden van een geschikte richting en de daaropvolgende minimalisering in deze richting. De rechtvaardiging van onbeperkte optimalisatiemethoden kan natuurlijk worden uitgebreid tot de rechtvaardiging van procedures voor het oplossen van problemen met beperkingen.
Het probleem van voorwaardelijke optimalisatie is het vinden van de minimale of maximale waarde van de scalaire functie f(x) van n-dimensionale vectorargumenten. De oplossing van het probleem is gebaseerd op een lineaire of kwadratische benadering van de doelfunctie om de incrementen x1, ..., xn bij elke iteratie te bepalen. Er zijn ook benaderende methoden voor het oplossen van niet-lineaire problemen. Dit zijn methoden gebaseerd op de stuksgewijs lineaire benaderingsmethode. De nauwkeurigheid van het vinden van oplossingen hangt af van het aantal intervallen waarop we een oplossing vinden voor een lineair probleem dat zo dicht mogelijk bij een niet-lineair probleem ligt. Deze methode maakt het mogelijk om berekeningen uit te voeren met de simplex-methode. In lineaire modellen zijn de coëfficiënten van de objectieve functie doorgaans constant en niet afhankelijk van de waarde van de variabelen. Er zijn echter een aantal problemen waarbij de kosten niet-lineair afhankelijk zijn van het volume.
Oplossingsalgoritme:
- 1. Het werk begint met het construeren van een reguliere simplex in de ruimte van onafhankelijke variabelen en het schatten van de waarden van de objectieve functie op elk van de hoekpunten van de simplex.
- 2. Het hoekpunt wordt bepaald - de grootste waarde van de functie.
- 3. Het hoekpunt wordt geprojecteerd door het zwaartepunt van de resterende hoekpunten naar een nieuw punt, dat wordt gebruikt als het hoekpunt van de nieuwe simplex.
- 4. Als de functie soepel genoeg afneemt, gaan de iteraties door totdat ofwel het min-punt is bedekt of de cyclische beweging over 2 of meer simplexen begint.
- 5. Het zoeken eindigt wanneer ofwel de afmetingen van de simplex ofwel de verschillen tussen de waarden van de functie op de hoekpunten voldoende klein blijven.
Taak: capaciteitsoptimalisatie. Minimale kosten realiseren voor de fabricage van een container van 2750 liter voor het opslaan van zand.
Z = C1X1 + C2X2 + C3X3 + C4X4 + C5X5 min;
waarbij: X1 - hoeveelheid vereist metaal, kg;
C1 - metaalkosten, wrijven / kg;
X2 - massa van vereiste elektroden, kg;
C2 - kosten van elektroden, wrijven/kg;
X3 - de hoeveelheid verbruikte elektriciteit, kWh;
C3 - kosten van elektriciteit, wrijven/kWh;
X4 - werktijd van de lasser, h;
C4 - tarief van de lasser, rub/h;
X5 - bedrijfstijd van de lift, h;
C5 - betaling voor de lift, wrijven / h.
1. Vind het optimale oppervlak van de container:
F = 2ab+2bh+2ah min (1)
waarbij V=2750 liter.
x1=16.331; x2=10.99
Het minimum van de functie werd verkregen tijdens het optimalisatieproces met de Box-methode - 1196.065 dm2
In overeenstemming met GOST 19903 - 74 accepteren we:
h=16,50 dm, b=10,00 dm.
Laten we a van (1) uitdrukken en krijgen:
Bereken de optimale dikte van de metalen plaat
Laten we kiezen voor gewoon koolstofstaal St2sp
Voor dit staal 320 MPa, ;
Massa zand.
Belasting op de wand van de tank van het grootste gebied:
We berekenen de belasting per 1 lineaire centimeter van een plaat van 100 cm breed:
De wanddikte bepalen we op basis van de conditie:
waarbij: l de lengte van de plaat is (bij voorkeur de grootste om een extra veiligheidsmarge te laten);
q - belasting per 1 lineaire centimeter, kg/cm;
Dikte metaalplaat, m
De maximaal toelaatbare spanning van het metaal, N/mm2.
We drukken uit (2) de wanddikte uit:
Aangezien 320 MPa = 3263 kg/cm2
Massa van metaal
waarbij: F - tankoppervlak, m2;
Metalen wanddikte, m;
Metaaldichtheid, kg/m3.
De prijs van St2sp-staal is ongeveer 38 roebel/kg.
2. Laslengte:
Laten we elektroden gebruiken voor roestvrij staal "UONI-13/45"
Prijs 88,66 roebel / kg;
waar: Sweld - dwarsdoorsnede van de lasverbinding, m2;
l is de lengte van de las, m;
Dichtheid van neergeslagen metaal, kg/m3.
3. Lastijd:
waarbij l de lengte van de las is, m;
v - lassnelheid, m/h.
Totaal stroomverbruik:
Рsom = 5 17 = 85 kWh;
De kosten van elektriciteit zijn 5,7 roebel / kWh.
4. Voor handmatig booglassen bedragen de kosten van hulp-, voorbereidende en laatste tijd en tijd voor onderhoud aan de werkplek gemiddeld 40 - 60%. Laten we de gemiddelde waarde van 50% gebruiken.
Totale tijd:
Betaling voor een lasser van de categorie VI - 270 roebel / uur.
Plus een tariefcoëfficiënt van 17% voor werken in een afgesloten slecht geventileerde ruimte:
Het salaris van de assistent is 60% van het salaris van de lasser:
8055 0,6 = 4833 roebel.
Totaal: 8055 + 4833 = 12888 roebel.
5. Er is een kraan nodig om de metalen platen vast te houden tijdens het lassen, de metalen platen te laden en te lossen en de afgewerkte container zelf.
Om de hele constructie te "grijpen", moet de lasser ongeveer 30% van de naden aanbrengen.
Betaling voor de kraan - 1000 roebel / uur.
De totale kosten van de container.
5. Multidimensionale optimalisatie
Lineair programmeren
Optimalisatie is een doelgerichte activiteit, die bestaat uit het behalen van de beste resultaten onder de juiste omstandigheden.
Het kwantificeren van de kwaliteit die wordt geoptimaliseerd heet optimaliteitscriterium of objectieve functie .Het kan worden geschreven als:
|
(5.1) |
waarbij x 1 , x 2 , … , x neezijn enkele parameters van het optimalisatieobject.
Er zijn twee soorten optimalisatieproblemen: onvoorwaardelijk en voorwaardelijk.
onvoorwaardelijke taak optimalisatie bestaat uit het vinden van het maximum of minimum van de reële functie (5.1) vannwerkelijke variabelen en het bepalen van de juiste argumentwaarden.
Conditionele optimalisatieproblemen , of problemen met beperkingen, zijn die bij de formulering waarvan beperkingen worden opgelegd aan de waarden van de argumenten in de vorm van gelijkheden of ongelijkheden.
De oplossing van optimalisatieproblemen waarbij het optimaliteitscriterium een lineaire functie is van onafhankelijke variabelen (dat wil zeggen, het bevat deze variabelen in de eerste graad) met lineaire beperkingen daarop is het onderwerp lineair programmeren.
Het woord "programmeren" weerspiegelt hier het uiteindelijke doel van het onderzoek - het bepalen van het optimale plan of optimale programma, op basis waarvan de beste, optimale optie wordt gekozen uit de vele mogelijke opties voor het onderzochte proces.
Een voorbeeld zo'n taak is probleem van optimale verdeling van grondstoffen tussen verschillende industrieën tegen de maximale productiekosten.
Laat twee soorten producten gemaakt worden van twee soorten grondstoffen.
Geef aan: x 1, x 2 - het aantal eenheden van producten van respectievelijk de eerste en de tweede soort; c 1 , c 2 zijn eenheidsprijzen van producten van respectievelijk de eerste en de tweede soort. Dan zijn de totale kosten van alle producten::
|
|
(5.2) |
Als gevolg van de productie is het wenselijk dat de totale productiekosten maximaal zijn.R (x 1 , x 2 ) is de objectieve functie in dit probleem.
b 1 , b 2 - de hoeveelheid beschikbare grondstoffen van de eerste en tweede soort;aij- aantal eenheden i het soort grondstof dat nodig is om een eenheid te producerenje type product.
Aangezien het verbruik van deze hulpbron de totale hoeveelheid niet kan overschrijden, noteren we de beperkende voorwaarden voor hulpbronnen:
|
|
(5.3) |
met betrekking tot variabelen x 1, x 2 we kunnen ook zeggen dat ze niet-negatief en oneindig zijn.:
|
(5.4) |
Onder de reeks oplossingen voor het systeem van ongelijkheden (5.3) en (5.4), is het nodig om een dergelijke oplossing te vinden ( x 1, x 2 ), waarvoor de functieRzijn hoogste waarde bereikt.
De zogenaamde transporttaken (taken van optimale organisatie van de levering van goederen, grondstoffen of producten vanuit verschillende magazijnen naar meerdere bestemmingen met een minimum aan transportkosten) en een aantal andere zijn in een vergelijkbare vorm geformuleerd.
Grafische methode voor het oplossen van een lineair programmeerprobleem.
Laat het nodig zijn om te vinden x 1 en x 2 , bevredigend systeem van ongelijkheden:
|
|
(5.5) |
en voorwaarden niet-negativiteit:
|
(5.6) |
voor welke functie?
|
|
(5. 7 ) |
een maximum bereikt.
Oplossing.
Laten we het systeem van rechthoekige coördinaten inbouwen x 1 Os 2 gebied van haalbare oplossingen voor het probleem (Fig. 11). Om dit te doen, waarbij we elk van de ongelijkheden (5.5) vervangen door een gelijkheid, construeren we relevant hem een grenslijn:
(i = 1, 2, … , r)
Rijst. elf
Deze lijn verdeelt het hele vlak in twee halve vlakken. Voor coördinaten x 1, x 2 enig punt MAAR een halfvlak, geldt de volgende ongelijkheid:
en voor de coördinaten van elk punt BIJ het andere halfvlak, de tegenovergestelde ongelijkheid:
De coördinaten van elk punt van de grenslijn voldoen aan de vergelijking:
Om te bepalen aan welke kant van de grenslijn het halve vlak dat overeenkomt met de gegeven ongelijkheid zich bevindt, volstaat het om een willekeurig punt (het eenvoudigste punt O(0;0)). Als, bij het vervangen van de coördinaten in de linkerkant van de ongelijkheid, wordt voldaan, dan wordt het halve vlak naar het testpunt gedraaid, als de ongelijkheid niet wordt voldaan, dan wordt het corresponderende halve vlak in de tegenovergestelde richting gedraaid. De richting van het halve vlak is in de tekening gearceerd weergegeven. ongelijkheden:
komen overeen met het halve vlak dat zich rechts van de ordinaat-as en boven de abscis-as bevindt.
In de figuur construeren we grenslijnen en halve vlakken die overeenkomen met alle ongelijkheden.
Het gemeenschappelijke deel (kruispunt) van al deze halve vlakken zal het gebied zijn van haalbare oplossingen voor dit probleem.
Bij het construeren van het domein van haalbare oplossingen kan, afhankelijk van het specifieke type systeem van beperkingen (ongelijkheden) op variabelen, een van de volgende vier gevallen optreden:
Rijst. 12. Het gebied van haalbare oplossingen is leeg, wat overeenkomt met de inconsistentie van het systeem van ongelijkheden; geen oplossing
Rijst. 13. Het gebied van toegestane oplossingen wordt weergegeven door één punt A, wat overeenkomt met de enige oplossing voor het systeem
Rijst. 14. Het gebied van haalbare oplossingen is beperkt, weergegeven als een convexe veelhoek. Er zijn oneindig veel mogelijke oplossingen
Rijst. 15. Het gebied van toelaatbare oplossingen is onbeperkt, in de vorm van een convex veelhoekig gebied. Er zijn oneindig veel mogelijke oplossingen
Grafische weergave van de objectieve functie
tegen een vaste waardeRdefinieert een rechte lijn, en bij het veranderenR- familie van parallelle lijnen met parameterR. Voor alle punten die op een van de lijnen liggen, is de functie R neemt één bepaalde waarde aan, dus deze lijnen heten niveau lijnen voor de R-functie.
Verloopvector:
loodrechtnaar de niveaulijnen, toont de richting van de toenameR.
Het probleem van het vinden van een optimale oplossing voor het systeem van ongelijkheden (5.5) waarvoor de doelfunctieR(5.7) bereikt een maximum, reduceert geometrisch tot het bepalen in het gebied van haalbare oplossingen het punt waardoor de niveaulijn zal gaan, overeenkomend met de grootste waarde van de parameterR
Rijst. 16
Als het domein van haalbare oplossingen een convexe veelhoek is, dan is het extremum van de functieR wordt bereikt op ten minste een van de hoekpunten van deze veelhoek.
Als de extreme waardeRwordt bereikt op twee hoekpunten, dan wordt dezelfde extreme waarde bereikt op elk punt op het segment dat deze twee hoekpunten verbindt. In dit geval wordt gezegd dat de taak alternatief optimum .
In het geval van een onbegrensd gebied, het extremum van de functieRofwel bestaat niet, of wordt bereikt op een van de hoekpunten van het gebied, of heeft een alternatief optimum.
Voorbeeld.
Laat het nodig zijn om de waarden te vinden x 1 en x 2 , voldoen aan het systeem van ongelijkheden:
en voorwaarden niet-negativiteit:
voor welke functie:
een maximum bereikt.
Oplossing.
Laten we elk van de ongelijkheden vervangen door een gelijkheid en de grenslijnen construeren:
Rijst. 17
Laten we de halve vlakken bepalen die overeenkomen met deze ongelijkheden door het punt (0;0) te "testen". Rekening houdend met niet-negativiteit x 1 en x 2 we verkrijgen het gebied van haalbare oplossingen van dit probleem in de vorm van een convexe veelhoek OAVDE.
Op het gebied van haalbare oplossingen vinden we de optimale oplossing door de gradiëntvector te construeren
laten zienoplopende richtingR.
De optimale oplossing komt overeen met het punt BIJ, waarvan de coördinaten grafisch kunnen worden bepaald of door een stelsel van twee vergelijkingen op te lossen die overeenkomen met de grenslijnen AB en VD:
Antwoorden: x1 = 2; x 2 \u003d 6; Rmax = 22.
Taken. Vind de positie van het uiterste punt en de uiterste waarde van de doelfunctie
onder bepaalde beperkingen.
|
Tabel 9 |
|||||
|
Extreem |
Beperkingen |
||||
|
M bijl |
|
||||
|
Max |
|
||||
|
|
|||||
|
; ; |
|||||
|
;
;
|
|||||
|
| |||||
; 
;
; ;
;
;
;
;
;
Taak 1. Vind
Probleem 1 wordt gereduceerd tot het oplossen van het stelsel vergelijkingen:
en het onderzoeken van de waarde van het tweede differentieel:
bij de oplossingspunten van vergelijkingen (8.3).
Als de kwadratische vorm (8.4) in een punt negatief-definitief is, dan bereikt hij daar zijn maximale waarde, en als hij positief-definitief is, dan zijn minimumwaarde.
Voorbeeld:
Het stelsel vergelijkingen heeft oplossingen:
Het punt (-1/3.0) is het maximum punt en het punt (1/3.2) is het minimum punt.
Taak 2. Vind
onder voorwaarden:
Probleem 2 wordt opgelost door de Lagrange-multipliermethode. Om dit te doen, vinden we een oplossing voor het systeem (t + p) vergelijkingen:
Voorbeeld. Zoek de zijden van een rechthoek met een maximale oppervlakte ingeschreven in een cirkel: . De oppervlakte A van een rechthoek is te schrijven als: A = 4xy dan
Taak 3. Vind:
onder voorwaarden:
Deze taak omvat een breed scala aan taken gedefinieerd door functies f en .
Als ze lineair zijn, dan is het probleem een lineair programmeerprobleem.
Een taak3 a.
onder voorwaarden
Het wordt opgelost door de simplex-methode, die, met behulp van het apparaat van lineaire algebra, een doelgerichte opsomming uitvoert van de hoekpunten van het veelvlak gedefinieerd door (8.13).
Simplex methode (bestaat uit twee fasen):
Fase 1. Het vinden van de referentieoplossing x (0) .
De drageroplossing is een van de punten van het veelvlak (8.13).
Fase 2. De optimale oplossing vinden.
De optimale oplossing wordt gevonden door opeenvolgende telling van de hoekpunten van het veelvlak (8.13), waarbij de waarde van de doelfunctie z niet bij elke stap afneemt, namelijk:
Een speciaal geval van een lineair programmeerprobleem is het zogenaamde transportprobleem.
transport taak. Laat de punten magazijnen bevatten waarin goederen respectievelijk in hoeveelheden worden opgeslagen. In de punten staan consumenten die deze goederen respectievelijk in hoeveelheden moeten leveren. noem c ij de kosten van het vervoer van een vrachteenheid tussen punten
We onderzoeken de werking van het transport door consumenten van goederen in hoeveelheden die voldoende zijn om aan de behoeften van consumenten te voldoen. Geef aan door de hoeveelheid goederen die vanaf het punt wordt vervoerd a i naar paragraaf b j .
Om aan de behoeften van de consument te voldoen, is het noodzakelijk dat de waarden X ij voldeed aan de voorwaarden:
Tegelijkertijd vanuit magazijn a; u kunt geen producten in grotere hoeveelheden afhalen dan er beschikbaar zijn. Dit betekent dat de gezochte waarden moeten voldoen aan het systeem van ongelijkheden:
Voldoe aan de voorwaarden (8.14), (8.15), dat wil zeggen: maak een vervoersplan dat op oneindig veel manieren voldoet aan de wensen van de consument. Om ervoor te zorgen dat de operationeel onderzoeker een bepaalde oplossing kiest, dat wil zeggen, bepaalde X ij, moet er een selectieregel worden geformuleerd, bepaald door een criterium dat ons subjectieve idee van het doel weerspiegelt.
Het probleem van het criterium wordt onafhankelijk van de studie van de operatie opgelost - het criterium moet worden bepaald door de operationele kant. In dit probleem zal een van de mogelijke criteria de transportkosten zijn. Het is als volgt gedefinieerd:
Vervolgens wordt het transportprobleem geformuleerd als een lineair programmeerprobleem: de grootheden bepalen die voldoen aan de beperkingen (8.14), (8.15) en de functie (8.16) de minimumwaarde geven. Beperking (8.15) is een evenwichtsvoorwaarde; voorwaarde (8.14) kan het doel van de operatie worden genoemd, omdat de bedoeling van de operatie is om aan de behoeften van consumenten te voldoen.
Deze twee voorwaarden vormen in wezen het operatiemodel. De uitvoering van de operatie zal afhangen van de criteria op basis waarvan de verwezenlijking van het doel van de operatie zal worden gegarandeerd. Het criterium kan in verschillende rollen voorkomen. Het kan zowel fungeren als een manier om het doel te formaliseren en als een principe voor het kiezen van acties uit de toegestane, dat wil zeggen, acties die voldoen aan de beperkingen.
Een van de bekende methoden voor het oplossen van het transportprobleem is de methode van potentialen.
In de eerste fase van het oplossen van het probleem wordt een eerste transportplan opgesteld dat voldoet aan
beperkingen (8.14), (8.15). Als (dat wil zeggen, de totale behoefte niet samenvalt met de totale voorraden producten in magazijnen), dan wordt een fictief verbruikspunt of een fictief magazijn met een transportkost gelijk aan nul in aanmerking genomen. Voor de nieuwe taak valt de totale hoeveelheid goederen in magazijnen samen met hun totale vraag. Vervolgens wordt op een of andere manier (bijvoorbeeld het kleinste element of de noordwestelijke hoek) het oorspronkelijke plan gevonden. Bij de volgende stap van de procedure van het verkregen plan, wordt een systeem van speciale kenmerken - potentiëlen gebouwd. Een noodzakelijke en voldoende voorwaarde voor een optimaal plan is de potentie ervan. De procedure voor het verfijnen van het plan wordt uitgevoerd totdat het potentieel (optimaal) wordt.
Taak 3b. In het algemeen wordt het probleem (8.10 - 8.11) een niet-lineair programmeerprobleem genoemd. Beschouw het in een meer geaccepteerde vorm:
onder voorwaarden
Om dit probleem op te lossen, worden zogenaamde relaxatiemethoden gebruikt. Het proces van het construeren van een reeks punten wordt relaxatie genoemd als:
Afdalingsmethoden (algemeen schema). Alle daalmethoden voor het oplossen van het onbeperkte optimalisatieprobleem (8.17) verschillen ofwel in de keuze van de daalrichting of in de manier van bewegen in de daalrichting. De afdalingsmethodes bestaan uit de volgende sequentieconstructieprocedure: { x k }.
Een willekeurig punt wordt gekozen als initiële benadering x 0 . Opeenvolgende benaderingen worden gebouwd volgens het volgende schema:
Punt x k de richting van de afdaling is gekozen - s k ;
Vind (k + 1) -de benadering met de formule:
waarbij als waarde een willekeurig getal kiest dat voldoet aan de ongelijkheid
waarbij getal een willekeurig getal is zodanig dat 
Bij de meeste afdalingsmethoden wordt de waarde van tot gelijk aan één gekozen. Om k te bepalen, moet men dus het probleem van eendimensionale minimalisering oplossen.
Gradiënt afdaling methode. Aangezien de antigradiënt de richting aangeeft van de snelste afname in de functie f(x), dan is het natuurlijk om vanaf het punt te bewegen X k in deze richting. Een afdalingsmethode, waarbij het de gradiëntdalingsmethode wordt genoemd. Als, dan wordt het ontspanningsproces de steilste afdalingsmethode genoemd.
De methode van geconjugeerde richtingen. In lineaire algebra staat deze methode bekend als de geconjugeerde gradiëntmethode voor het oplossen van stelsels van lineaire algebraïsche vergelijkingen AH=b, en daarom, als een methode om de kwadratische functie te minimaliseren
Methode schema:
Als = 0, dan verandert dit schema in het schema van de steilste afdalingsmethode. Juiste keuze van hoeveelheid t k garandeert de convergentie van de methode van geconjugeerde richtingen met een snelheid van dezelfde orde als in de methoden voor gradiëntafdaling en zorgt ervoor dat het aantal iteraties in kwadratische afdaling eindig is (bijvoorbeeld ).
Coördineren afdaling. Bij elke iteratie als de richting van de afdaling − s k de richting langs een van de coördinaatassen is gekozen. De methode heeft een convergentiesnelheid van het minimalisatieproces van orde 0 (1/m). Bovendien hangt het in wezen af van de dimensie van de ruimte.
Methode schema:
waar is de coördinaatvector
Als op het punt x k er is informatie over het gedrag van de functiegradiënt f(x), bijvoorbeeld:
dan als de richting van de afdaling s k je kunt de coördinaatvector nemen e j . In dit geval is de convergentiesnelheid van de methode n keer kleiner dan bij gradiëntdaling.
In de beginfase van het minimalisatieproces kan de methode van cyclische coördinaatgewijze afdaling worden gebruikt, wanneer de afdaling voor het eerst wordt uitgevoerd in de richting e 1 , dan op e 2, enz. tot e P , waarna de hele cyclus opnieuw wordt herhaald. Veelbelovend dan de vorige is de gecoördineerde afdaling, waarbij de afdalingsrichtingen willekeurig worden gekozen. Met deze benadering van de richtingskeuze zijn er a priori schattingen die de functie garanderen f(x) Met met een waarschijnlijkheid die neigt naar eenheid als , de convergentie van het proces met een snelheid in de orde van 0 (1/m).
Methode schema:
Bij elke stap van het proces wordt willekeurig een getal gekozen uit n getallen (1, 2, ..., n) j(k) en als s k de eenheidscoördinaatvector is gekozen e j ( k ) , waarna de afdaling wordt uitgevoerd:
Willekeurige afdalingsmethode.s k, die een uniforme verdeling op deze bol gehoorzaamt, en dan volgens het element berekend in de kde stap van het proces X tot bepaald:
De convergentiesnelheid van de random-descent-methode is n keer lager dan die van de gradiënt-descent-methode, maar n keer hoger dan die van de random-coördinaat-afdalingsmethode. De weloverwogen afdalingsmethoden zijn ook toepasbaar op niet noodzakelijk convexe functies en garanderen hun convergentie onder zeer kleine beperkingen (zoals de afwezigheid van lokale minima).
Ontspanningsmethoden van wiskundig programmeren. Laten we terugkeren naar Opgave 36 ((8.17) – (8.18)):
onder voorwaarden
Bij optimalisatieproblemen met beperkingen hangt de keuze van de daalrichting samen met de noodzaak om constant te controleren of de nieuwe waarde X k +1 zou hetzelfde moeten zijn als voorheen x k voldoen aan een systeem van beperkingen X.
Voorwaardelijke gradiëntmethode. Bij deze methode is het idee om de afdalingsrichting te kiezen als volgt: op het punt X tot lineariseer de functie f(x), een lineaire functie bouwen en vervolgens minimaliseren f(x) op de set X, vind een punt ja k . Daarna wordt aangenomen en verder in deze richting wordt een afdaling uitgevoerd, zodat
Dus, om de richting te vinden - s k, moet men het probleem oplossen van het minimaliseren van een lineaire functie op de verzameling X. Als een X wordt op zijn beurt gegeven door lineaire beperkingen, dan wordt het een lineair programmeerprobleem.
Methode van mogelijke richtingen. Methode-idee: tussen alle mogelijke richtingen op een punt X tot kies degene waarlangs de functie f(x) het snelst afneemt en vervolgens in deze richting afdaalt.
Richting - s bij het punt X X wordt genoemd mogelijk als er een nummer bestaat zodanig dat voor alle. Om een mogelijke richting te vinden, is het nodig om het lineaire programmeerprobleem op te lossen, of het eenvoudigste kwadratische programmeerprobleem:
Onder voorwaarden:
Laat de oplossing voor dit probleem zijn. Voorwaarde (8.25) garandeert dat de richting mogelijk is. Voorwaarde (8.26) zorgt voor de maximale waarde (, dat wil zeggen, tussen alle mogelijke richtingen - s, richting - biedt de snelste afname in de functie f(x). Voorwaarde (8.27) elimineert de onbegrensdheid van de oplossing van het probleem. De mogelijke richtingen methode is bestand tegen mogelijke rekenfouten. Het is echter moeilijk om de mate van convergentie in het algemene geval in te schatten, en dit probleem blijft nog steeds onopgelost.
willekeurige zoekmethode. De implementatie van de bovenstaande minimaliseringsmethoden is over het algemeen erg arbeidsintensief, behalve in de eenvoudigste gevallen, wanneer de reeks beperkingen een eenvoudige geometrische structuur heeft (het is bijvoorbeeld een multidimensionaal parallellepipedum). In het algemeen kan de willekeurige zoekmethode veelbelovend zijn, wanneer de afdaalrichting willekeurig wordt gekozen. In dit geval zullen we aanzienlijk verliezen in de mate van convergentie, maar de eenvoud van het kiezen van de richting kan deze verliezen compenseren in termen van de totale arbeidskosten voor het oplossen van het minimaliseringsprobleem.
Methode schema:
Op de n-dimensionale eenheidsbol gecentreerd op de oorsprong, wordt een willekeurig punt gekozen r k, die een uniforme verdeling op deze bol gehoorzaamt, en dan is de afdalingsrichting s k van de voorwaarden
wordt gekozen als de initiële benadering. Volgens het punt berekend bij elke iteratie x k wordt gebouwd ( k+ 1)e punt x k +1 :
Elk getal van = dat voldoet aan de ongelijkheid wordt gekozen als:
De convergentie van deze methode is bewezen onder zeer losse beperkingen op de functie f (bult) en veel beperkingen X (convexiteit en sluiting).
Van de nulde-orde optimalisatiemethoden in CAD worden de Rosenbrock-methoden, configuraties, vervormbare veelvlakken en willekeurige zoekmethoden gebruikt. Methoden die derivaten gebruiken, omvatten methoden van de steilste afdaling, geconjugeerde gradiënten, variabele metrieken.
De methode van Rosenbrock is een verbeterde versie van coördinatenafdaling.
Coördinaat afdalingsmethode gekenmerkt door de keuze van zoekrichtingen op hun beurt langs alle coördinaatassen, wordt de stap berekend op basis van eendimensionale optimalisatie, het zoekterminatiecriterium, waar is de gespecificeerde nauwkeurigheid van het bepalen van het lokale extremum, is de afmeting van de ruimte van gecontroleerde parameters. Het coördinaatgewijze afdalingstraject voor een voorbeeld van een tweedimensionale ruimte van gecontroleerde parameters wordt getoond in Fig. 1, waar zijn de punten op het zoektraject, zijn de gecontroleerde parameters. De objectieve functie wordt weergegeven door zijn lijnen van gelijk niveau, nabij elke lijn wordt de bijbehorende waarde geschreven. Uiteraard is er een minimum punt.
Rijst. 1. Coördineer het afdalingstraject
Bij gebruik van de gecoördineerde afdalingsmethode is de kans groot dat de zoekopdracht "vastloopt" op de bodem van het ravijn, ver van het uiterste punt. Op afb. 2 laat zien dat na het raken van het punt dat zich op de bodem van het ravijn bevindt, verdere stappen alleen mogelijk zijn in de richtingen of , maar ze leiden tot een verslechtering van de doelfunctie. Daarom eindigt de zoekopdracht op het punt .
Notitie 1
Een ravijn is een deel van de ruimte van gecontroleerde parameters, waarin er zwakke veranderingen zijn in de afgeleiden van de objectieve functie in één richting en significante veranderingen met een tekenverandering in sommige andere richtingen. Het teken van de afgeleide verandert op punten die bij de bodem van het ravijn horen.
Rijst. 3. Traject van coördinaatsgewijze afdaling met een gunstige oriëntatie van de coördinaatassen
Rosenbrock-methode: bestaat uit een zodanige rotatie van de coördinaatassen dat een ervan quasi-parallel aan de bodem van het ravijn blijkt te zijn. Een dergelijke rotatie wordt uitgevoerd op basis van gegevens die zijn verkregen na een reeks coördinaat-daalstappen. De positie van de nieuwe assen kan worden verkregen door een lineaire transformatie van de oude assen: de as valt in richting samen met de vector; de overige assen worden gekozen uit de voorwaarde van orthogonaliteit op en op elkaar.
Een andere succesvolle wijziging van de coördinaatafdaling is: configuratie methode:(Hook-Jeeves). In overeenstemming met deze methode wordt eerst de gebruikelijke reeks stappen van coördinatendaling uitgevoerd, daarna wordt een extra stap in de richting van de vector genomen, zoals weergegeven in Fig. 4, waar een extra stap wordt uitgevoerd in de richting van de vector , die leidt naar het punt .
Rijst. 4. Illustratie van de configuratiemethode
Een extremum vinden vervormbare veelvlakmethode:(Nelder-Mead) is gebaseerd op de constructie van een veelvlak met hoekpunten bij elke zoekstap, waarbij de afmeting van de ruimte van gecontroleerde parameters is. Aan het begin van het zoeken worden deze hoekpunten willekeurig gekozen; bij volgende stappen is de keuze onderworpen aan de regels van de methode.
Deze regels zijn geïllustreerd in Fig. 5 over het voorbeeld van een tweedimensionaal optimalisatieprobleem. De hoekpunten van de originele driehoek zijn geselecteerd: , , . Het nieuwe hoekpunt bevindt zich op de straal getrokken van het slechtste hoekpunt (van het hoekpunt met de hoogste waarde van de doelfunctie) door het zwaartepunt van het veelvlak, en het wordt aanbevolen om te kiezen op een afstand van , gelijk aan . De nieuwe top vervangt de slechtste top. Als blijkt dat het de beste waarde heeft van de objectieve functie tussen de hoekpunten van het veelvlak, dan wordt de afstand vergroot. In de figuur is dit precies de situatie en de stijging geeft een punt. In een nieuw veelvlak met hoekpunten , , is het slechtste hoekpunt ; op dezelfde manier krijgt men een hoekpunt , dan een hoekpunt , enzovoort. Als het nieuwe hoekpunt slechter blijkt te zijn, dan moet het beste hoekpunt in het veelvlak worden gehouden en moeten de lengtes van alle randen worden verminderd, bijvoorbeeld met de helft (het veelvlak samentrekken tot het beste hoekpunt). Het zoeken stopt wanneer aan de voorwaarde voor het verkleinen van het veelvlak tot een bepaalde grens is voldaan.
de stap wordt gekozen om optimaal te zijn met behulp van eendimensionale optimalisatie.
Bij gebruik van de steilste afdalingsmethode, zoals bij de meeste andere methoden, wordt de zoekefficiëntie aanzienlijk verminderd in ravijnsituaties. Het zoektraject neemt een zigzagvorm aan met langzame voortgang langs de bodem van het ravijn naar het uiterste. Om de efficiëntie van gradiëntmethoden te vergroten, worden verschillende trucs gebruikt.
Een van de methoden die worden gebruikt in geconjugeerde gradiëntmethode:(ook wel de Fletcher-Reeves-methode genoemd) is gebaseerd op het concept van conjugatie van vectoren. Vectoren en worden -conjugaat genoemd als , waar een positief bepaalde vierkante matrix is van dezelfde orde als de grootte van de vectoren en (een speciaal geval van conjugatie is de orthogonaliteit van vectoren wanneer is de identiteitsmatrix van orde ), een rij is vector, is een kolomvector.
Een kenmerk van geconjugeerde richtingen voor , waar is de Hessische matrix , in problemen met een kwadratische doelfunctie is als volgt: eendimensionale minimalisatie achtereenvolgens langs geconjugeerde richtingen maakt het mogelijk om het uiterste punt in niet meer dan stappen te vinden.
Opmerking 2:
De Hessische matrix is de matrix van tweede partiële afgeleiden van de doelfunctie met betrekking tot gecontroleerde parameters.
De reden om de zoekopdracht in -adjoint richtingen te gebruiken is dat voor functies () van algemene vorm een kwadratische benadering kan worden toegepast, wat zich in de praktijk vertaalt in het uitvoeren van de zoekopdracht in meer dan stappen.
Het zoeken naar een extremum wordt uitgevoerd volgens de formule
waar is een coëfficiënt. Bovendien wordt rekening gehouden met de vervoegingsvoorwaarde
Aangezien de stap wordt berekend op basis van de eendimensionale optimalisatievoorwaarde, moet eerst de relatie
Het zoekalgoritme wordt teruggebracht tot het toepassen van formule (3) totdat aan de voorwaarde voor het einde van de berekeningen is voldaan
Om de coëfficiënt te bepalen, los het stelsel vergelijkingen (2)-(7) op door in (4) de waarden van (3) en van (2) te vervangen:
of
waar
en rekening houdend met (6) en (7)
Expressie (10) is een stelsel van lineaire algebraïsche vergelijkingen. De wortel is een andere benadering van de oplossing
Als het proces convergeert, wordt de oplossing bereikt in een klein aantal iteraties, waarvan het einde de vervulling van de voorwaarde is
waar
Dat is waarom
Er kan worden aangetoond dat neigt naar , — naar als , waar is de dimensie van de ruimte van gecontroleerde parameters. Na de stappen moet je opnieuw beginnen met.
Taak 1. Vind
waarbij x = (x 1 .. xn) e E p
Dit probleem wordt gereduceerd tot het oplossen van het stelsel vergelijkingen
en de studie van de waarde van het tweede differentieel
op de punten (a-|, (*2, a n) oplossingen van vergelijkingen (7.3).
Als de kwadratische vorm (7.4) in een punt negatief-definitief is, dan bereikt hij daar zijn maximale waarde, en als hij positief-definitief is, dan zijn minimumwaarde.
Voorbeeld: 
Het stelsel vergelijkingen heeft oplossingen:
Het punt (-1; 3.0) is het hoogtepunt en het punt (1; 3.2) is het dieptepunt.
Een taak 2. Zoek
onder voorwaarden: 
Dit probleem 2 wordt opgelost door de methode van Lagrange-multipliers, waarvoor de oplossing van het systeem wordt gevonden (t + p) vergelijkingen:
Voorbeeld 2 Vind de zijden van een rechthoek met maximale oppervlakte ingeschreven in een cirkel 
Oppervlakte L van een rechthoek
kan worden geschreven als: MAAR= 4xy, dan
waar 
Een taak 3. Zoek onder voorwaarden:
Dit probleem omvat een breed scala aan formuleringen die worden bepaald door de functies f en vgl. Als ze lineair zijn, dan is het probleem een lineair programmeerprobleem.
Taak voor.
onder voorwaarden
Het wordt opgelost door de simplex-methode , die, met behulp van het apparaat van lineaire algebra, een doelgerichte opsomming uitvoert van de hoekpunten van het veelvlak gedefinieerd door (7.13).
Simplex methode bestaat uit twee fasen.
Fase 1. Het vinden van de referentieoplossing x^ 0). De drageroplossing is een van de punten van het veelvlak (7.13).
Fase 2. De optimale oplossing vinden. Het wordt gevonden door opeenvolgende telling van de hoekpunten van het veelvlak (7.13), waarbij de waarde van de doelfunctie z niet bij elke stap afneemt, dat wil zeggen:
Een speciaal geval van een lineair programmeerprobleem is het zogenaamde transportprobleem.
transport taak. Laat in de punten a-1, a 2, .... a l er magazijnen zijn waarin goederen zijn opgeslagen in de hoeveelheid van respectievelijk x 1, x 2, ..., x l. In de punten b-|, b 2 ,..., b m zijn er consumenten die deze goederen moeten leveren in hoeveelheden y- y 2 , y t respectievelijk. noem Cjj kosten van het vervoer van een vrachteenheid tussen de punten a-| en bij.
We onderzoeken de werking van het vervoeren van goederen door consumenten in hoeveelheden die voldoende zijn om aan de behoeften van de klanten te voldoen. Aanduiden door Hu de hoeveelheid goederen die van punt a naar punt b wordt vervoerd.
Om aan de behoeften van de consument te voldoen, is het noodzakelijk dat de waarden x, y voldoen aan de voorwaarden:
Tegelijkertijd is het onmogelijk om producten uit het magazijn te halen in een grotere hoeveelheid dan daar beschikbaar is. Dit betekent dat de gezochte waarden moeten voldoen aan het systeem van ongelijkheden:
Voldoen aan voorwaarden (7.14), (7.15), d.w.z. er zijn talloze manieren om een vervoersplan te maken dat aansluit bij de wensen van de consument. Om ervoor te zorgen dat de operationeel onderzoeker een bepaalde optimale oplossing kiest, d.w.z. benoem bepaalde Xjj, er moet een selectieregel worden geformuleerd, bepaald door een criterium dat ons subjectieve idee van het doel weerspiegelt.
Het probleem van het criterium wordt onafhankelijk van de studie van de operatie opgelost - het criterium moet worden bepaald door de operationele kant. In het onderhavige probleem zal een van de mogelijke criteria de transportkosten zijn. Zij is
Vervolgens wordt het transportprobleem geformuleerd als een lineair programmeerprobleem: om de waarden x, y > 0 te bepalen die voldoen aan de beperkingen (7.14), (7.15) en de minimale waarde aan de functie (7.16) te leveren. Beperking (7.15) is een evenwichtsvoorwaarde; voorwaarde (7.14) kan het doel van de operatie worden genoemd, omdat de bedoeling van de operatie is om aan de behoeften van consumenten te voldoen.
De aanduiding van twee voorwaarden vormt in wezen het operatiemodel. De uitvoering van de operatie zal afhangen van de criteria op basis waarvan de verwezenlijking van het doel van de operatie zal worden gegarandeerd. Het criterium kan in verschillende rollen voorkomen. Het kan zowel dienen als een manier om het doel te formaliseren, en als een principe voor het kiezen van acties uit de toegestane, d.w.z. voldoen aan de beperkingen.
Een van de bekende methoden voor het oplossen van het transportprobleem is de potentiële methode, waarvan het schema als volgt is.
In de eerste fase van het oplossen van het probleem wordt een eerste transportplan opgesteld dat voldoet aan de randvoorwaarden (7.14), (7.15). Als een
(d.w.z. de totale behoefte valt niet samen met de totale voorraad producten in magazijnen), dan wordt een fictief verbruikspunt in overweging genomen 
of fictief magazijn
met de transportkosten gelijk aan nul. Voor de nieuwe taak valt de totale hoeveelheid goederen in magazijnen samen met hun totale vraag. Vervolgens wordt op een of andere manier (bijvoorbeeld het kleinste element of de noordwestelijke hoek) het oorspronkelijke plan gevonden. Bij de volgende stap van de procedure van het verkregen plan, wordt een systeem van speciale kenmerken - potentiëlen gebouwd. Een noodzakelijke en voldoende voorwaarde voor een optimaal plan is de potentie ervan. De procedure voor het verfijnen van het plan wordt herhaald totdat het plan potentieel (optimaal) wordt.
Een taak 36. In het algemene geval wordt probleem (7.10-7.11) een niet-lineair programmeerprobleem genoemd. Beschouw het in de vorm
onder voorwaarden
Om dit probleem op te lossen, worden zogenaamde relaxatiemethoden gebruikt. Het proces van het construeren van een reeks punten wordt relaxatie genoemd als:
Afdalingsmethoden (algemeen schema). Alle daalmethoden bij het oplossen van het onbeperkte optimalisatieprobleem (7.17) verschillen in de keuze van de daalrichting of in de manier van bewegen in de daalrichting. De afdalingsmethodes bestaan uit de volgende sequentieconstructieprocedure: (x tot ).
Als initiële benadering wordt een willekeurig punt Xq gekozen. Opeenvolgende benaderingen worden gebouwd volgens het volgende schema:
- punt x k de richting van de afdaling is gekozen - Sk;
- vind (tot+ 1)de benadering door de formule
waar als een hoeveelheid $ naar kies een willekeurig getal dat aan de ongelijkheid voldoet
waar nummer X naar - elk getal zodanig dat 0 X k min f(x k - $ Sk).
Bij de meeste afdalingsmethoden is de hoeveelheid X k gelijk aan één wordt gekozen. Om te bepalen (3^) moet men dus het probleem van eendimensionale minimalisering oplossen.
Gradiënt afdaling methode. Omdat de anti-gradiënt is: G(xk) geeft de richting aan van de snelste afname van de functie f(x), dan is het natuurlijk om vanaf het punt te bewegen x naar door deze richting. De afdalingsmethode waarin S k \u003d f "(x k) de gradiëntafdalingsmethode genoemd. Als een X k= 1, dan wordt het relaxatieproces de steilste afdalingsmethode genoemd.
De methode van geconjugeerde richtingen. BIJ in lineaire algebra staat deze methode bekend als de geconjugeerde gradiëntmethode voor het oplossen van stelsels van lineaire algebraïsche vergelijkingen OH= b, en daarom als een methode om de kwadratische functie te minimaliseren f(x) =((Dx - b)) 2 .
Methode schema:
Als een fk = 0, dan verandert dit schema in het schema van de steilste afdalingsmethode. Juiste keuze van hoeveelheid t k garandeert de convergentie van de methode van geconjugeerde richtingen met een snelheid van dezelfde orde als bij gradiëntafdalingsmethoden, en zorgt ervoor dat het aantal iteraties in kwadratische afdaling eindig is (bijvoorbeeld
Coördineren afdaling. Bij elke iteratie als de richting van afdaling S k de richting langs een van de coördinaatassen is geselecteerd. De methode heeft een convergentiesnelheid van het minimalisatieproces van orde 0 (1 //77), en het hangt in wezen af van de afmeting van de ruimte.
Methode schema:
waar 
coördinaat Vector,
Als op het punt x k er is informatie over het gedrag van de functiegradiënt f(x), bijvoorbeeld,
dan als de richting van de afdaling S k we kunnen de coördinaatvector ey nemen. In dit geval is de convergentiesnelheid van de methode in P keer minder dan bij gradiëntafdaling.
In de beginfase van het minimaliseringsproces kan de methode van cyclische coördinaatgewijze afdaling worden gebruikt, wanneer de afdaling eerst wordt uitgevoerd in de richting e-|, vervolgens langs β2, enzovoort. tot ep, waarna de hele cyclus wordt herhaald. Veelbelovend dan beschreven is de coördinaat afdaling, waarbij de richting van de afdaling willekeurig wordt gekozen. Met deze benadering van de richtingskeuze zijn er a priori schattingen die de functie garanderen f(x) met een waarschijnlijkheid die neigt naar eenheid als het proces convergeert met een snelheid in de orde van 0 (1 .) 1t).
Methode schema:
Bij elke stap van het proces van P cijfers (1, 2, ..., P) een nummer wordt willekeurig gekozen j(k) en als s k er wordt een eenheidscoördinaatvector gekozen ws, waarna de afdaling wordt uitgevoerd:
Willekeurige afdalingsmethode. Op de n-dimensionale eenheidsbol gecentreerd op de oorsprong, wordt een willekeurig punt gekozen sk, onderworpen aan een uniforme verdeling op deze bol, en dan volgens het element berekend in de i-de stap van het proces x k bepaald xk+] :
De convergentiesnelheid van de methode van willekeurige afdaling in P keer minder dan de gradiëntafdalingsmethode, maar in P keer groter is dan die van de willekeurige coördinatenafdalingsmethode. De weloverwogen afdalingsmethoden zijn ook toepasbaar op niet noodzakelijk convexe functies en garanderen hun convergentie onder zeer kleine beperkingen (zoals de afwezigheid van lokale minima).
Ontspanningsmethoden van wiskundig programmeren. Laten we terugkeren naar probleem 36 ((7.17) - (7.18)):
onder voorwaarden
Bij optimalisatieproblemen met beperkingen hangt de keuze van de daalrichting samen met de noodzaak om constant te controleren of de nieuwe waarde x tot +" zou hetzelfde moeten zijn als voorheen xk, voldoen aan het restrictiesysteem X.
Voorwaardelijke gradiëntmethode. BIJ Bij deze methode is het idee om de afdalingsrichting te kiezen als volgt: op het punt x k lineariseer de functie
f(x), een lineaire functie bouwen f(x) = f (x k) + (y "(x k), x-x k), en dan minimaliseren f(x) op de set X, vind een punt bij k. Daarna wordt aangenomen dat S k \u003d y k - x k en verder in deze richting de afdaling uitvoeren Xk+ 1\u003d x k - $ k (x k -y k), zodat gX.
Dus, om een richting te vinden S k men zou het probleem van het minimaliseren van een lineaire functie op een verzameling X moeten oplossen. Als X op zijn beurt wordt gegeven door lineaire beperkingen, dan wordt het een lineair programmeerprobleem.
Methode van mogelijke richtingen. Het idee van de methode: kies uit alle mogelijke richtingen op het punt xk degene waarlangs de functie f(x) het snelst afneemt en vervolgens in deze richting afdaalt.
Richting s bij het punt X e X wordt aangeroepen mogelijk als er een getal (3 > 0) bestaat zodat X- (3s e X voor iedereen (3 g . Om een mogelijke richting te vinden, is het noodzakelijk om een lineair programmeerprobleem of het eenvoudigste kwadratische programmeerprobleem op te lossen: a?=> min onder voorwaarden
Laten d tot en s k- de oplossing voor dit probleem. Voorwaarde (7.25) garandeert dat de richting s k mogelijk. Voorwaarde (7.26) zorgt voor de maximale waarde van (/"( xk),s), die. tussen alle mogelijke richtingen s, richting s k zorgt voor het snelste verval van de functie f(x). Voorwaarde (7.27) elimineert de onbegrensdheid van de oplossing van het probleem. De mogelijke richtingen methode is bestand tegen mogelijke rekenfouten. Het is echter moeilijk om de mate van convergentie in het algemene geval in te schatten, en dit probleem blijft nog steeds onopgelost.
willekeurige zoekmethode. De implementatie van de hierboven geschetste minimaliseringsmethoden is over het algemeen erg arbeidsintensief, behalve in de eenvoudigste gevallen, wanneer de reeks beperkingen een eenvoudige geometrische structuur heeft (het is bijvoorbeeld een multidimensionaal parallellepipedum). In het algemeen kan de willekeurige zoekmethode veelbelovend zijn, wanneer de afdaalrichting willekeurig wordt gekozen. In dit geval zal er een aanzienlijk verlies zijn in de convergentiesnelheid, maar de eenvoud van het kiezen van de richting kan deze verliezen compenseren in termen van de totale arbeidskosten voor het oplossen van het minimaliseringsprobleem.
Methode schema:
op de n-dimensionale eenheidsbol gecentreerd op de oorsprong, wordt een willekeurig punt gekozen gu gehoorzamen aan een uniforme verdeling op deze bol, en dan de richting van afdaling - s^ van voorwaarden
Als eerste benadering kiezen we: xs e X. Volgens het punt berekend bij elke iteratie X? in opbouw (k + 1)e punt x^+j:
Elk nummer van 
de ongelijkheid bevredigen
De convergentie van deze methode is bewezen onder zeer losse beperkingen op de functie / (convexiteit) en de reeks beperkingen X(convexiteit en sluiting).
