Avval oddiy savol: ifoda doim musbatmi?

Matematikada ba'zan ifodaning hech qachon manfiy bo'lmasligini isbotlashni xohlaymiz. Masalan, muhandislik modelida energiya miqdori, xato qiymati, risk funksiyasi yoki xarajat hisobi ma'lum shartlarda noldan kichik bo'lmasligi kerak. Kompyuter yordamida optimizatsiyada ham shunga o'xshash savollar tez-tez uchraydi:

«Bu formula har holatda xavfsiz oralikda qoladimi?»
«Bu xarajat funksiyasining eng kichik qiymati nima?»
«Bu tizimning barqarorligini ko'rsatadigan ifoda haqiqatan ham manfiy bo'lmagan tuzilmami?»

Bunday savollarning markazida ko'pincha polinomlar turadi. Polinom — o'zgaruvchilarning darajalari bilan qurilgan matematik ifodalardir. Masalan, x² + y² kabi ifoda polinomdir va doim nol yoki musbatdir. Chunki sonning kvadrati manfiy bo'lishi mumkin emas.

Lekin ishlar doimo shunchalik oddiy emas. O'zgaruvchilar soni va daraja oshgan sari, polinomning har yerda manfiy emasligini tushunish ancha qiyinlashishi mumkin.

Kvadratlar yig'indisi nima degani?

Klassik va kuchli g'oyalardan biri shudir:
Agar polinom boshqa polinomlarning kvadratlari yig'indisi sifatida yozilsa, u manfiy bo'lishi mumkin emas.

Chunki kvadratlar doimo nol yoki musbatdir. Masalan:

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

shaklida yoziladigan p(x) polinomi uchun natija aniq: p(x) manfiy bo'lishi mumkin emas. Bu usul «sum of squares», ya'ni «kvadratlar yig'indisi» deb ataladi.

Bu g'oya ham matematik jihatdan toza, ham kompyuterlar bilan qo'llash mumkin. Chunki polinomning kvadratlar yig'indisi ekanligini tekshirish ma'lum shartlarda yarı tanımlı programlama deb ataladigan optimizatsiya usullari bilan amalga oshirilishi mumkin.

Biroq bu yerda muhim muammo bor:
Har bir manfiy bo'lmagan polinom kvadratlar yig'indisi sifatida yozilmaydi.

Ya'ni polinom haqiqatan ham hech qachon manfiy qiymat olmasligi mumkin; lekin uni bitta kvadratlar yig'indisi kimligi bilan isbotlash mumkin bo'lmasligi mumkin.

Motzkin polinomi nima uchun muhim?

Maqolaning asosiy misollaridan biri Motzkin polinomidir. Bu polinom matematikada mashhur misoldir. Chunki u manfiy bo'lmagan, lekin klassik ma'noda kvadratlar yig'indisi bo'lmagan polinomlardan biridir.

Oddiy qilib aytganda:
Motzkin polinomi haqiqatan ham manfiy bo'lmagan polinomdir; lekin buni bitta standart kvadratlar yig'indisi ifodasi bilan ko'rsatish mumkin emas.

Bu holat o'quvchiga shuni aytadi:

«Bir narsaning to'g'ri bo'lishi bilan uni oson shaklda isbotlay olish bir xil narsa emas.»

Kvadratlar yig'indisi usuli kuchlidir; lekin har bir manfiy bo'lmagan polinomni past xarajat bilan qamrab ololmaydi. Ba'zi hollarda isbotni topish uchun polinom darajasini oshirish kerak bo'ladi. Daraja oshgan sari kompyuter hal qilishi kerak bo'lgan muammo ham tez kattalashishi mumkin.

Bu tadqiqotning g'oyasi nima?

Tadqiqotchilar taklif qilgan asosiy g'oya shudir:

Bitta katta isbot qidirish o'rniga, maydonni qismlarga bo'ling va har bir qism uchun alohida isbot yarating.

Buni kundalik misol bilan o'ylab ko'ramiz. Tog'ning har bir nuqtasida xavfsiz yurish yo'li bor-yo'qligini tekshirmoqchimiz. Butun tog'ni bitta xarita tavsifi bilan isbotlash qiyin bo'lishi mumkin. Buning o'rniga tog'ni hududlarga bo'lib, har bir hudud uchun alohida xavfsizlik nazorati qilish boshqarish osonroq bo'lishi mumkin.

Bu tadqiqotda ham shunga o'xshash matematik yondashuv qo'llaniladi. Polinomning aniqlangan butun maydoni qismlarga bo'linadi. Har bir qismda o'sha hududga xos kvadratlar yig'indisi kimligi quriladi. Barcha qismlar birlashtirilganda poliomning umuman manfiy emasligi xulosasiga kelinadi.

Tadqiqotchilar bu g'oyaga «disjunctive sum of squares» nomini berishadi. Buni «ajratilgan kvadratlar yig'indisi» yoki «qismli kvadratlar yig'indisi isboti» deb tushunish mumkin.

Formulani qanday o'qish kerak?

Maqoladagi asosiy tuzilma texnik ko'rinishi mumkin; biroq mantiqini soddalashtirish mumkin.

Klassik kvadratlar yig'indisi isbotida quyidagiga qarab:

p(x) = kvadratlar yig'indisi

Bu bitta kimlikdir. Agar topilsa, p(x) manfiy emasligi tushuniladi.

Ajratilgan kvadratlar yig'indisi yondashuvida esa quyidagicha o'ylash mumkin:

Maydon bir nechta hududga bo'linadi. Har bir hudud ba'zi shartlar bilan aniqlanadi. Masalan, bir hududda q(x) ≥ 0 bo'lishi mumkin, boshqa hududda -q(x) ≥ 0 bo'lishi mumkin. Bu ikki hudud birgalikda butun maydonni qamrab oladi.

Keyin har bir hudud uchun quyidagi turdagi kimlik qidiriladi:

p(x) = kvadratlar yig'indisi + hudud sharti × kvadratlar yig'indisi

Bu nima uchun ishlaydi?

Chunki o'sha hudud ichida hudud sharti allaqachon manfiy emas. Kvadratlar yig'indisi ham manfiy emas. Demak, o'ng tomondagi ifoda manfiy bo'lishi mumkin emas. O'ng tomondagi ifoda p(x) ga teng bo'lgani uchun p(x) ham o'sha hududda manfiy bo'lishi mumkin emas.

Bu amal barcha hududlar uchun qilinsa, polinomning har yerda manfiy emasligi isbotlangan bo'ladi.

1-rasm nima aytadi?

Maqoladagi 1-rasm Motzkin polinomi uchun uch xil bo'linish g'oyasini ko'rsatadi. Grafiklarda ikki o'lchovli maydon turli rangli qismlarga bo'lingan. Har bir rang poliomning manfiy emasligini isbotlash uchun ishlatiladigan turli past hududni ifodalaydi.

Birinchi bo'lakda maydon x₁x₂ ifodasining belgisiga ko'ra bo'linadi. Ya'ni x₁x₂ ≥ 0 bo'lgan hududlar va x₁x₂ < 0 bo'lgan hududlar alohida baholanadi.

Ikkinchi bo'lakda bo'linish sodda: x₁ ≥ 0 va x₁ < 0 kabi ikki yarim maydon bo'yicha o'ylash mumkin.

Uchinchi bo'lakda esa murakkabroq, egri chegaralari bo'lgan bo'linish ishlatiladi. Bu ham xuddi shu polinom uchun turli bo'linish strategiyalari mumkinligini ko'rsatadi.

Bu rasmning o'quv maqsadidagi xabari shudir:
Polinomning manfiy emasligini isbotlash uchun maydonni faqat bitta usulda bo'lish shart emas. To'g'ri bo'linish tanlanganda, pastroq darajali va boshqarish osonroq isbotlar topilishi mumkin.

«Pastroq daraja» nima uchun muhim?

Polinomlarda daraja oshgan sari hisoblash qiyinlashadi. Kvadratlar yig'indisi usullarida kompyuter hal qilishi kerak bo'lgan matritsalar hajmi ham tez kattalashishi mumkin. Shuning uchun isbotning pastroq darajada qolishi hisoblash nuqtai nazaridan muhim bo'lishi mumkin.

Maqola ajratilgan kvadratlar yig'indisi yondashuvi bilan ba'zi hollarda isbot darajasini poliomning o'z darajasi darajasida past saqlash mumkinligini ko'rsatadigan nazariy natijalar beradi.

Buni soddalashtirsak:

Klassik yondashuvda ba'zan «isbotni topish uchun yuqoriroq darajali ifodalar ishlatish kerak» deyilishi mumkin.
Bu tadqiqot taklif qilgan yondashuv esa «darajani oshirish o'rniga hududlar sonini ko'paytirish mumkin» g'oyasini oldinga qo'yadi.

Ya'ni qiyinlik bitta katta isbotga yuklanish o'rniga bir nechta kichik isbotlarga taqsimlanadi.

Positivstellensatz nima degani?

Maqolada «disjunctive Positivstellensatz» deb ataladigan nazariy natijalar bor. Bu so'z birinchi qarashda og'ir ko'rinishi mumkin; biroq asosiy ma'nosi shudir:

Poliomning musbat yoki manfiy bo'lmaganligini isbotlash uchun qaysi algebraik sertifikatlar yetarli ekanligini aytadigan teoremlar.

Bu tadqiqot bunday teoremlarning ajratilgan, ya'ni qismli versiyasini taqdim etadi. Tadqiqotchilar ma'lum shartlar ostida poliomning manfiy emasligini qismlarga bo'lingan past darajali kvadratlar yig'indisi isbotlari bilan sertifikatlash mumkinligini ko'rsatishadi.

Bu faqat texnik tafsilot emas. Chunki bunday sertifikatlar optimizatsiya muammolarida «bu yechim haqiqatan past chegaradimi?», «bu matritsa ma'lum musbatlik xususiyatiga egami?» yoki «bu modelning xavfsiz hududi qanday isbotlanadi?» kabi savollarda qo'llanilishi mumkin.

Kompyuter nuqtai nazaridan nima o'zgaradi?

Maqola bu yondashuvning kompyuterda yechish tomoniga ham hissa qo'shishi mumkinligini ta'kidlaydi.

Klassik kvadratlar yig'indisi yondashuvlarida ko'pincha bitta katta yarı tanımlı programlama muammosi hal qilinadi. Bu muammolar kattalashgan sari qimmatlashishi mumkin.

Ajratilgan yondashuvda esa har bir hudud uchun alohida isbot qidirilishi mumkin. Bu kichik muammolar ba'zi hollarda parallel hal qilinishi mumkin. Ya'ni turli protsessorlar yoki mashinalar bir vaqtning o'zida turli qismlarning isbotini qidirishlari mumkin.

Tadqiqot shuningdek «o'lchami o'zgarmas yarı tanımlı cheklovlar» g'oyasini ham ta'kidlaydi. Buning ma'nosi shudir: ierarxiya rivojlanganda eng katta matritsa cheklovining hajmi doimiy o'sishi shart emas; buning o'rniga ko'proq hududlar orqali yurish mumkin.

Bu katta hajmdagi optimizatsiya muammolarida potensial muhim afzallik bo'lishi mumkin. Biroq bu har bir muammoda avtomatik ravishda tezroq bo'lishi kerak degani emas. Hududlar soni oshgan sari boshqa xarajatlar ham paydo bo'lishi mumkin.

Optimizatsiyasiz yondashuv nimani anglatadi?

Maqolaning yana bir muhim qismi ba'zi hollarda poliomning manfiy emasligini ko'rsatish uchun optimizatsiyani hal qilmasdan ham ierarxiya qurish mumkinligini tushuntiradi.

Bu yerda g'oya shudir:
Fazo konus yoki simpleks kabi hududlarga bo'linadi. Keyin polinom bu hududlarda ba'zi chiziqli o'zgarishlar bilan qayta yoziladi. Agar o'zgarishdan keyin poliom koeffitsientlari manfiy bo'lmasa, o'sha hududda poliom manfiy emasligi tushuniladi.

Oddiy til bilan:

Polinomni turli koordinata tizimlarida qayta yozamiz. Agar bu yozuvlarda barcha koeffitsientlar mos ravishda manfiy bo'lmagan holga kelsa, bu bizga poliomning tegishli hududda manfiy emasligini ko'rsatadi.

Bu yondashuv doimo eng samarali usul bo'lmasligi mumkin; biroq muhim matematik g'oyani taqdim etadi: isbot faqat optimizatsiya yechuvchisiga bog'liq bo'lishi shart emas. Ba'zi isbotlar mos bo'linish va koeffitsient nazorati bilan ham qurilishi mumkin.

Branch-and-bound nima uchun ishlatiladi?

Maqolada ajratilgan kvadratlar yig'indisi yondashuvining branch-and-bound, ya'ni «bo'l va chekla» usuli bilan birlashtirilishi mumkinligi ham tushuntiriladi.

Branch-and-bound katta muammoni kichik kichik muammolarga bo'ladigan klassik optimizatsiya strategiyasidir. Avval maydon katta qismlar halida o'rganiladi. Agar bir qismda natija yetarlicha aniq bo'lmasa, o'sha qism yanada kichik qismlarga bo'linadi.

Bu tadqiqotda ham shunga o'xshash mantiq bor:

• Avval keng hudud ko'rib chiqiladi.
• Bu hududda yetarli isbot topilmasa, hudud yanada kichik qismlarga bo'linadi.
• Har bir qism uchun past va yuqori chegaralar yangilanadi.
• Yetarli aniqlikka erishilganda jarayon to'xtatiladi.

Bu usul butun maydonni boshidan juda mayda qismlarga bo'lish o'rniga kerakli hududlarni chuqurroq o'rganishga xizmat qiladi. Shunday qilib hisoblash resurslari tanlabroq ishlatilishi mumkin.

Raqamli tajribalar nima deyadi?

Maqoladagi raqamli tajribalar uch asosiy sohaga qaratilgan:

Birinchisi, klassik kvadratlar yig'indisi sinovining minimal qiymatni to'g'ridan-to'g'ri topishda qiynalgan ba'zi mashhur poliomlar ustida sinovlar o'tkaziladi. Motzkin, Robinson va Choi-Lam kabi adabiyotda ma'lum misollar shu doiraga kiradi.

Ikkinchisi, kopozitif matritsa muammolari ko'rib chiqiladi. Kopozitiflik, ayniqsa ba'zi qiyin optimizatsiya va kombinatorial muammolar bilan bog'liq matritsa xususiyatidir.

Uchinchisi, maksimal klik muammosi kabi kombinatorial optimizatsiya bog'lanishlari o'rganiladi. Maksimal klik — grafda har bir tugun bir-biri bilan bog'langan eng katta past guruhni topish muammosidir. Bu muammo kompyuter fanlari nuqtai nazaridan qiyin muammolar qatoriga kiradi.

Tajribalarning umumiy xabari shudir:
Taklif qilingan qismli yondashuv ba'zi qiyin misollarda past darajali yoki boshqarish osonroq sertifikatlar topa oladi va branch-and-bound bilan birgalikda ishlatilishi mumkin.

Biroq bu natijalar barcha muammo sinflarida umumiy samara kafolati sifatida o'qilmasligi kerak. Bu tanlangan matematik va optimizatsiya misollari ustida o'tkazilgan tajribalardir.

Bu nima uchun muhim?

Bu tadqiqot birinchi qarashda juda abstract ko'rinishi mumkin. Biroq asosiy g'oya ko'plab ilmiy va muhandislik sohalarini qiziqtiradi.

Boshqaruv tizimlarida tizimning xavfsiz yoki barqaror ekanligini isbotlash kerak bo'lishi mumkin. Robototda harakat rejasining ma'lum chegaralar ichida qolish-qolmasligi tekshirilishi mumkin. Statistikada yoki mashina o'rganishida ba'zi optimizatsiya muammolarining ishonchli past chegaralari qidirilishi mumkin. Kombinatorial optimizatsiyada juda katta qidiruv maydonlari boshqarish osonroq qismlarga bo'linishi mumkin.

Bu sohalarning umumiy ehtiyoji shudir:
Kompyuter faqat javob berish emas, balki javobning nima uchun ishonchli ekanligini ham isbotlay olishi.

Ajratilgan kvadratlar yig'indisi yondashuvi bunday isbotlarni bitta katta tuzilma o'rniga bir nechta kichik tuzilmalar orqali qurishga harakat qiladi. Bu ham kelajakda yanada kengaytiriladigan va parallel ishlay oladigan matematik sertifikat usullari uchun muhim tadqiqot yo'ni bo'lishi mumkin.

E'tibor berish kerak bo'lgan nuqtalar

Bu tadqiqot nazariy matematika va optimizatsiya sohasidadir. Shuning uchun kundalik amaliy mahsulot kabi talqin qilinmasligi kerak.

Birinchidan, tadqiqot preprint hisoblanadi va hakamlar bahosidan o'tmagan. Topilmalarni akademik jamoa baholashi va boshqa tadqiqotlar bilan qo'llab-quvvatlashi muhim.

Ikkinchidan, yondashuv ba'zi hollarda hisoblash afzalligi berishi mumkin; biroq bu har bir muammoda klassik usullardan tezroq yoki osonroq bo'ladi degani emas. Hududlar sonining oshishi ham alohida hisoblash xarajatini keltirib chiqarishi mumkin.

Uchinchidan, maqoladagi tajribalar ma'lum poliomlar, matritsa muammolari va kombinatorial optimizatsiya misollari ustida o'tkazilgan. Turli muammo o'lchamlari va qo'llanma sohalarida samara alohida o'rganilishi kerak.

To'rtinchi bo'lib, matnda qayd etilgan kvadratlar yig'indisi, yarı tanımlı programlama, Positivstellensatz, kopozitiflik kabi tushunchalar ilg'or darajadagi matematik vositalardir. Bu kontentda maqsad bu vositalarni barcha tafsilotlari bilan o'rgatish emas, balki tadqiqotning asosiy g'oyasini tushunarli qilishdir.

Xulosa

Bu tadqiqot poliomlarning manfiy emasligini isbotlash uchun yangi nuqtai nazarni taqdim etadi. Klassik kvadratlar yig'indisi yondashuvi bitta algebraik kimlik qidiradi, ajratilgan kvadratlar yig'indisi yondashuvi esa maydonni qismlarga bo'lib har bir qism uchun alohida isbot yaratadi.

Bu g'oya, ayniqsa qiyin poliomlarda pastroq darajali isbotlar olish, kichik muammolarni parallel hal qilish va branch-and-bound kabi usullar bilan tanlabroq qidirish imkoniyatiga ega.

Tadqiqotning asosiy xabari shudir:
Ba'zi matematik isbotlar bitta bo'lak sifatida qiyin bo'lishi mumkin; biroq to'g'ri bo'linganda boshqarish osonroq bo'ladi.

Bu nuqtai nazar kelajakda ishonchli optimizatsiya, boshqaruv tizimlari, robototika, statistika va kompyuter yordamida matematik isbotlar uchun yangi usullar ishlab chiqilishiga hissa qo'shishi mumkin.

Manba va usul eslatmasi

Bu kontent Amir Ali Ahmadi, Sanjeeb Dash, Yixuan Hua va Bartolomeo Stellato tomonidan tayyorlangan «Disjunctive Sum of Squares» nomli akademik ish asosida Verianla tahririy formatida mustaqil tayyorlangan.

Bu tadqiqot preprint hisoblanadi va hakamlar bahosidan o'tmagan. Kontent ma'lumot va ta'lim maqsadida tayyorlangan. Matematik optimizatsiya, muhandislik dizayni, boshqaruv tizimi tahlili yoki professional hisoblash maslahati o'rnini bosmaydi.