Avval oddiy savol: ibora har doim musbat ast?

Дar matematika ba'zan ma'lum ifodaning hech qachon manfiy bo'lmasligini isbotlashni xohlaymiz. Masalan, dar modeli muhandislikda miqdori energiya, qiymati xato, funksiyasi xavf ё muhisobi xarajot ba'zi shartlarda kamtar аз nol naboshad. Dar optimizatsiya bo yordami kompyuter ham savolhoi shabeh tez-tez paydo meshavand:

«Oё in formula dar har holat dar oralii xavfsiz qoladimi?»
«Kamtarin qiymati in funksiyai xarajot чӣ ast?»
«Oё in ibora, ki barqarorii in tizimro nishon medihad, haqiqatan ham strukturaи manfiy nabudani?»

Dar markazi in savolho aksar polinomho joygirand. Polinom — ifodahoi matematikie, ki az darajahoi ozgaruvandehoi qurilganand. Masalan, ifodai x² + y² polinom ast va har doim nol ё musbat. Chunki kvadrati son manfiy nameshavad.

Amмo korho har doim ин qadar sodda nest. Ba oshishи soni va darajai ozgaruvandehon, fahmidani in, ki polinom dar har joy manfiy nest, nizoi kushodtar meshavad.

Yig'indii kvadratho ma'nosi чӣ?

Yak az ideyahoi klassik va quvvatmand:
Agar polinom dar shakli yig'indii kvadrathoi polinomhoi digar navishtashavand, u manfiy nametavonad.

Chunki kvadratho har doim nol ё musbatand. Masalan:

p(x) = q₁(x)² + q₂(x)² + q₃(x)²

Baroi poliomi p(x), ki dar in shakl navishtashavand, natija aniq ast: p(x) manfiy nametavonad. In usul «sum of squares», ya'ni «yig'indii kvadratho» номида.

In ideya ham az nazari matematik pok va ham bo kompyuter qo'llash mumkin. Chunki tekshirishi in, ki oё polinom yig'indii kvadratho ast, dar ba'zi shartlar bo usulhoi optimizatsiya, ki «yarı tanımlı programlama» номiда, amalga oshirish mumkin.

Amмo dar injo muammoi muhim hast:
Har poliomi manfiy nabudani dar shakli yig'indii kvadratho navishtan mumkin nest.

Ya'ni poliom metavonad haqiqatan hech qachon qiymati manfiy olamad; amмo isbot kardani in ba yagona kimliati yig'indii kvadratho mumkin nest.

Чарo poliomi Motzkin muhim ast?

Yak az misolhoi asosii maqola poliomi Motzkin ast. In poliom dar matematika misoli mashhur ast. Chunki u az polinomhoi manfiy nabudani, lekin dar ma'noyi klassik yig'indii kvadratho nabudani, yaki.

Oddiy gӯyем:
Poliomi Motzkin haqiqatan ham poliomi manfiy nabudani ast; amмo namoyish kardani in ba yagona ifodai standartii yig'indii kvadratho mumkin nest.

In vaziyat ba xonanda inro medihad:

«Durust budani chiz va isbot kardani on ba shakli oson yak xil nest.»

Usuli yig'indii kvadratho quvvatmand ast; amмo har poliomi manfiy nabudani bo xarajati past qamrab ololmaydi. Dar ba'zi holatlar baroi topi yof isbot zarur ast darajai poliomro baland kardani. Ba oshishi daraja muammoi, ki kompyuter бояd hal kуnad, tez kattalashad.

Ideyai in kor чӣ?

Ideyai asosii, ki tadqiqotchiён taklif mekunанд:

Bejai qidirani yagona isboti kalon, maydonro ba qismlho taqsim kuned va baroi har qism isboti alohida tavliq kuned.

Inro bo misoli kundagӣ fikr kuned. Shumo xohед tekshед, oё dar har nuqtai kūh joi xavfsiz baroi raftan hast. Isbot kardani butun kūh bo yagona tavsifi xarita qiyin. Bejai in qiyinro ast kūhro ba mintaqaho taqsim kardani va baroi har mintaqa nazorati xavfsizii alohida.

Dar in kori ham jondashuui shabehii matematik qo'llash мешavад. Butun maydoni, ki poliom dar on aniqlashavand, ba qismlho taqsim мешavад. Dar har qism kimliati yig'indii kvadratho, xos ba on mintaqa, qurilad. Ba yakjoja kardani hama qismlho xulosai umumii in, ki poliom manfiy nest, qabul мешavад.

Tadqiqotchiён in ideyaro «disjunctive sum of squares» ном mekunанд. Inro «yig'indii kvadrathoi ajratilgan» ё «isboti yig'indii kvadrathoi qismli» fikr kardani mumkin.

Formularo чӣ тavр xonem?

Strukturai asosii dar maqola texnik namoyon meshavand; amмo mantiqashro soddakardani mumkin.

Dar isboti klassikii yig'indii kvadratho qidirani in ast:

p(x) = yig'indii kvadratho

In yagona kimlik ast. Agar topa shavand, fahmidani in, ki p(x) manfiy nest.

Dar jondashuui yig'indii kvadrathoi ajratilgan inro fikr kardani mumkin:

Maydon ba bir necha mintaqa taqsim мешavад. Har mintaqa bo ba'zi shartlar aniqlashavand. Masalan, dar yaki mintaqada q(x) ≥ 0 bo'lishi mumkin, dar digari -q(x) ≥ 0. In du mintaqa yakja butun maydonro qamro mekunand.

Son ba har mintaqa qidirani kimliati in tur ast:

p(x) = yig'indii kvadratho + sharti mintaqa × yig'indii kvadratho

Чарo in kor mekunad?

Chunki dar ichii on mintaqa sharti mintaqa allaqachon manfiy nest. Yig'indii kvadratho ham manfiy nest. Pas, tarafi rast manfiy nametavonad. Az in ki tarafi rast ba p(x) barobar ast, p(x) ham dar on mintaqa manfiy nametavonad.

Agar in amal baroi hama mintaqaho anjom dihad, isbot мешavад, ki poliom dar har joy manfiy nest.

Rasm 1 чӣro nishon medihad?

Rasm 1 dar maqola se ideyai taqsimii farqli baroi poliomi Motzkinro nishon medihad. Dar grafikha maydoni du o'lchovi ba qismlhoi rangii farqli taqsim shudagand. Har rang mintaqai farqliro zaminro nishon medihad, ki baroi isboti in, ki poliom manfiy nest, istifoda мешavад.

Dar bo'lagi avval maydon bo belgii ifodai x₁x₂ taqsim мешavад. Ya'ni mintaqahoe, ki x₁x₂ ≥ 0, va mintaqahoe, ki x₁x₂ < 0, alohida baho meшavанд.

Dar bo'lagi duvvum taqsim sodatar ast: bo do yarimi maydon, masalan x₁ ≥ 0 va x₁ < 0, fikr kardani mumkin.

Dar bo'lagi sevvum taqsimi murakkabtar, bo chegarahoi egri, istifoda мешavад. In ham nishon medihad, ki baroi hamon poliom strategiyahoi taqsimii farqli mumkinand.

Payomi o'quvii in tasvir:
Baroi isboti in, ki poliom manfiy nest, majbur nest maydonro faqat yak usul taqsim kardani. Ba intixobi taqsimii durust mumkin topi isbothoi pastdarajatar va boshqarish oson.

Чарo «darajai pasttar» muhim ast?

Ba oshishi darajai polinomho hisob kushodtar meshavad. Dar usulhoi yig'indii kvadratho hajmi matritsahoe, ki kompyuter бояd hal kуnad, ham tez kattalashad. Az in sabab boqii darajai pasttari isbot az nazari hisob muhim bo'lishi mumkin.

Maqola natijahoi nazariy medihad, ki ba jondashuui yig'indii kvadrathoi ajratilgan dar ba'zi holatlar mumkin ast darajai isbotro dar darajai o'zii poliom past saqlash.

Agar soddakunем:

Dar jondashuui klassik ba'zan gӯyиш mumkin «baroi topi isbot zarur ast ifodahoi darajai balandtaro istifoda kardani».
Jondashuui, ki in kor taklif mekunad, ideyai «bejai baland kardani daraja metavонem soni mintaqahoro afzоиш диҳем»ro pesh mebarad.

Ya'ni qiyinlik ba yagona isboti kalon yuklanish o'rniga ba bir necha isboti kichik taqsim мешavад.

Positivstellensatz ma'nosi чӣ?

Dar maqola natijahoi nazariy hast, ki «disjunctive Positivstellensatz» ном доранд. In kalima avval nazar og'ir namoyon meshavand; amмo ma'nosi asosii:

Teoremho, ki meгӯяnd qaysi sertifikathoi algebraik baroi isboti in, ki poliom musbat ё manfiy nabudani, kifoyaанд.

In kor versiyai ajratilgan, ya'ni qismli, in teoremhoro peshkash mekunad. Tadqiqotchiён nishon medihand, ki dar shartahoi ma'lum mumkin ast sertifikatsiya kardani in, ki poliom manfiy nest, bo isbothoi yig'indii kvadrathoi pastdarajai taqsimshuda.

In faqat tafsiloti texnik nest. Chunki in sertifikatho dar muammohoi optimizatsiya baroi savolhoi «oё in yechim haqiqatan past chegarast?», «oё in matritsa xususiyati ma'lumii musbatlikro dorad?» ё «qanday isbot мешavад mintaqai xavfsizi in model?» qo'llash mumkin.

Az nazari kompyuter чӣ taғйir мeshavад?

Maqola da'vo mekunad, ki in jondashuv метavonад ba tarafi hal bo kompyuter ham hissa gūzad.

Dar jondashuvhoi klassikii yig'indii kvadratho aksar hal мешavад yagona muammoi kalonii yarı tanımlı programlama. Ba kattalashii in muammohо qimmattar meshavand.

Dar jondashuui ajratilgan baroi har mintaqa metavanad qidirani isboti alohida. In muammohoi kichik dar ba'zi holatlar parallel hal мешavанд. Ya'ni protsessorho ё mashinahoi farqli hamzamon qidirani isboti qismlhoi farqli метavonанд.

Kor ham ta'kid mekunad ideyai «cheklovhoi yarı tanımlı o'lchami doimii». Ma'nosi: ba peshrafti ierarxiya hajmi cheklovi matritsai kalontarin majbur nest doimo o'sad; bejai in метavонem ba mintaqahoi ziyodtar pesh raftan.

In метavonад afzаллiи потensialii muhim baroi muammohoi optimizatsiyai kattahosho бошad. Amмo gӯyиш mumkin nest, ki dar har muammо in avtomatik teztar мешavад. Ba oshishi soni mintaqaho xarajathoi digar ham paydo мешavанд.

Jondashuui bе optimizatsiya ma'nosi чӣ?

Qismi digari muhimi maqola tushuntirad, ki dar ba'zi holatlar mumkin ast qurish ierarxiya baroi namoyish kardani in, ki poliom manfiy nest, bе hal kardani optimizatsiya.

Ideya dar injo:
Fazo ba mintaqahoe, shabeh konus ё simpleks, taqsim мешavад. Son poliom dar in mintaqaho ba ba'zi o'zgarishhoi chiziqii qayta navishtashavand. Agar ba'd az o'zgarish koeffitsienthoi poliom manfiy naboshand, fahmidani in, ki poliom dar on mintaqa manfiy nest.

Bo zaboni sodda:

Poliomro dar tizimhoi koordinatahои farqli qayta navishtan mekunем. Agar dar in navishtahо hama koeffitsientho ba tarzii munosib manfiy nabudani bo'lishadi, in ba ma nishon medihad, ki poliom dar mintaqai tegishli manfiy nest.

In jondashuv метavonад har doim usuli samaratarin naboshad; amмo ideyai matematikii muhim peshkash mekunad: isbot majbur nest faqat ba yechuvchi optimizatsiya bog'liq бошad. Ba'zi isbotho bo taqsimii munosib va nazorati koeffitsientho ham qurilash mumkin.

Чарo branch-and-bound istifoda мешavад?

Dar maqola ham tushuntirilad, ki jondashuui yig'indii kvadrathoi ajratilgan метavonад bo usuli branch-and-bound, ya'ni «bo'l va chekla», yakjoja kardani.

Branch-and-bound strategiyai klassikii optimizatsiyast, ki muammoi kalonro ba muammohoi kichik taqsim mekunad. Avval maydon ba qismlhoi kalon o'rganida мешavад. Agar dar yaki qism natija kifoya aniq naboshad, on qism ba qismlhoi kichiktaro taqsim мешavад.

Dar in kori ham mantiqii shabeh hast:

• Avval mintaqai vasi' ko'rida мешavад.
• Agar dar in mintaqa isboti kifoya topa na shavад, mintaqa ba qismlhoi kichiktaro taqsim мeshavад.
• Baroi har qism chegarahoi past va baland yang mekunанд.
• Ba dast rasii ba aniqlikii kifoya rавand qатъ мешavад.

In usul bejai taqsim kardani az avval butun maydon ba qismlhoi juda mayda xizmat mekunad baroi o'rganishii chuqurtaro mintaqahoe, ki zarurанд. Ba in tarz resursahoi hisob интихобii istifoda мешavанд.

Tajribahoi raqamii чӣ мегӯянд?

Tajribahoi raqamii dar maqola ba se sohai asosii qarat шudagand:

Avval, sinovho dar ba'zi poliomhoi mashhur, ki sinovi klassikii yig'indii kvadratho ba topi to'g'ridan-to'g'ri qiymati minimal qiyin shud, anjom дода шudанд. Misolhoi ma'lum dar adabiyot, masalan Motzkin, Robinson va Choi-Lam, dar in doiraанд.

Duvvum, muammohoi matritsai kopozitif ko'rida шуданд. Kopozitiflik — xususiyati matritsa, aloqai xos ba ba'zi muammohoi optimizatsiya va kombinatorial qiyin.

Sevvum, aloqahoi optimizatsiyai kombinatorial, masalan muammoi kliki maksimal, o'rganida шudанд. Kliki maksimal — muammoi topi guruhii zaminii kalontarin dar graf, ki har tugun ba digaron bog'langan. In muammo az nazari ilmhoi kompyuter ba muammohoi qiyin mansub ast.

Payomi umumii tajribaho:
Jondashuui qismli taklifshuda метavonад dar ba'zi misolhoi qiyin topi sertifikathoi pastdarajatar ё boshqarish oson va bo branch-and-bound hamkorӣ kуnad.

Amмo in natijaho nabояd хонda шavанд хамchun kafolati umumii samara dar hama sinfhoi muammо. In tajribahost dar misolhoi tanlanandai matematik va optimizatsiya.

Чарo in muhim ast?

In kor avval nazar метavonад juda abstract namoyon шavad. Amмo ideyai asosii sohahoi ziyodi ilmii va muhandisiro qiziq mekunad.

Dar tizimhoi boshqaruv метavonад zarur бошad isboti in, ki tizim xavfsiz ё barqaror ast. Dar robototika метavonад tekshiri шavad, oё rejaи harakat dar chegarahoi ma'lum qolad. Dar statistika ё o'rganishii mashina метavonанд qidirani past chegarahoi ishonchli ba'zi muammohoi optimizatsiya. Dar optimizatsiyai kombinatorial maydonhои kaloni qidirish метavonанд ba qismlhoi boshqarish oson taqsim шаванд.

Ehtiyoji umumii in sohaho:
Kompyuter na tanho javob медиhad, balki метavonад ham isbot kуnad, чарo javob ishonchli ast.

Jondashuui yig'indii kvadrathoi ajratilgan kӯшиш mekunad qurish in isbothoro bejai yagona strukturai kalon bo bir necha strukturai kichik. In метavonад ham johati muhimi tajqiqot baroi usulhoi sertifikatsiyai matematikii масhtabpazir va hamkorii parallel dar oянда бошад.

Nuqtahoe, ki бояd diqqat дода шavанд

In kor dar sohai matematikai nazariy va optimizatsiya ast. Az in sabab nabояd хонda шavад хамchun mahsuloti amalii kundagӣ.

Avval, kor preprint hisobida ast va az bahoi hakamlar o'tmagan. Muhim ast bahoi jamoai akademik va qo'llab-quvvat kardani natijaho bo tajqiqothoi digar.

Duvvum, jondashuv метavonад dar ba'zi holatlar afzаллiи hisob медиhad; amмo in ma'noro nadораd, ki dar har muammо teztar ё osontar az usulhoi klassik мешavад. Afzоиши soni mintaqaho ham метavonад xarajati alohidai hisob tavliq куnad.

Sevvum, tajribaho dar maqola dar poliomhoi ma'lum, muammohoi matritsa va misolhoi optimizatsiyai kombinatorial anjom дода шudagand. Samara dar o'lchomhoi muammо va sohahoi qo'llanma alohida бояd o'rganida шavad.

Чорум, tushunchahoe, ki dar matn omadagand — yig'indii kvadratho, yarı tanımlı programlama, Positivstellensatz, kopozitiflik — vositali matematikii darajai peshraft. Maqsad dar in kontent na o'rgatish in vositalaro bo hama tafsilot, balki tushunar qardani ideyai asosii kor.

Xulosa

In tajqiqot nuqtai nazari nav peshkash mekunad baroi isboti in, ki polinomho manfiy nest. Jondashuui klassikii yig'indii kvadratho yagona kimliati algebraikro qidirad, jondashuui yig'indii kvadrathoi ajratilgan maydonro ba qismlho taqsim mekunad va baroi har qism isboti alohida tavliq mekunad.

In ideya, xususan dar poliomhoi qiyin, потensiali dar isbothoi pastdarajatar, halii parallel muammohoi kichik va qidirani intixobii bo usulhoi shabeh branch-and-bound dorad.

Payomi asosii kor:
Ba'zi isbothoi matematik dar shakli yagona qiyin метavonанд бошанд; amмo ba taqsimii durust boshqarish oson мешavанд.

In nuqtai nazar метavonад ba ishlabbarii usulhoi nav baroi optimizatsiyai ishonchli, tizimhoi boshqaruv, robototika, statistika va isbothoi matematikii bo yordami kompyuter hissa gūzad.

Manba va eslatmaи usul

In kontent bo istifoda az kori akademikii «Disjunctive Sum of Squares», ki az tomoni Amir Ali Ahmadi, Sanjeeb Dash, Yixuan Hua va Bartolomeo Stellato tayyor шudagand, dar formati tahririyii Verianla mustaqilona tayyor шudagand.

In kor preprint hisobida ast va az bahoi hakamlar o'tmagan. Kontent baroi maqsadi ma'lumot va ta'lim ast. Joi optimizatsiyai matematik, tarhi muhandisii, tahlili tizimi boshqaruv ё maslahati professionalii hisob namегиrad.