Əvvəlcə sadə sual: Bir ifadə həmişə müsbətdirmi?

Riyaziyyatda bəzən bir ifadənin heç vaxt mənfi olmadığını sübut etmək istəyirik. Məsələn, mühəndislik modelində enerji miqdarı, xəta dəyəri, risk funksiyası və ya xərc hesabı müəyyən şərtlərdə sıfırdan kiçik olmamalıdır. Kompüter dəstəkli optimallaşdırmada da oxşar suallar tez-tez yaranır:

“Bu düstur bütün hallarda təhlükəsiz intervalda qalırmı?”
“Bu xərc funksiyasının ən kiçik dəyəri nədir?”
“Bu sistemin dayanıqlığını göstərən ifadə həqiqətən qeyri-mənfi quruluşdurmu?”

Bu tip sualların mərkəzində çox vaxt polinomlar dayanır. Polinom dəyişənlərin qüvvətləri ilə qurulan riyazi ifadədir. Məsələn, x² + y² kimi ifadə polinomdur və həmişə sıfır və ya müsbət olur. Çünki ədədin kvadratı mənfi ola bilməz.

Lakin məsələ həmişə bu qədər sadə deyil. Dəyişənlərin sayı və dərəcə artdıqca polinomun bütün sahədə qeyri-mənfi olduğunu müəyyən etmək xeyli çətinləşə bilər.

Kvadratlar cəmi nə deməkdir?

Klassik və güclü ideyalardan biri belədir:
Əgər polinom başqa polinomların kvadratlarının cəmi kimi yazıla bilirsə, həmin polinom mənfi ola bilməz.

Çünki kvadratlar həmişə sıfır və ya müsbət olur. Məsələn:

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

şəklində yazıla bilən p(x) polinomu üçün nəticə aydındır: p(x) mənfi ola bilməz. Bu üsul “sum of squares”, yəni “kvadratlar cəmi” yanaşması adlanır.

Bu ideya həm riyazi baxımdan səliqəlidir, həm də kompüterlərlə tətbiq oluna bilər. Çünki polinomun kvadratlar cəmi olub-olmadığını araşdırmaq müəyyən şərtlərdə yarımmüəyyən proqramlaşdırma adlanan optimallaşdırma üsulları ilə aparıla bilər.

Lakin burada mühüm problem var:
Hər qeyri-mənfi polinom kvadratlar cəmi kimi yazıla bilmir.

Yəni polinom həqiqətən heç bir yerdə mənfi qiymət almaya bilər, amma bunu tək bir kvadratlar cəmi eyniliyi ilə sübut etmək mümkün olmaya bilər.

Motzkin polinomu niyə vacibdir?

Məqalədə izah olunan əsas nümunələrdən biri Motzkin polinomudur. Bu polinom riyaziyyatda məşhur nümunədir. Çünki qeyri-mənfi olduğu halda klassik mənada kvadratlar cəmi olmayan polinomlardan biridir.

Sadə desək:
Motzkin polinomu həqiqətən qeyri-mənfi polinomdur; lakin bunu tək bir standart kvadratlar cəmi ifadəsi ilə göstərmək mümkün deyil.

Bu vəziyyət oxucuya bunu göstərir:

“Bir şeyin doğru olması ilə onu asan şəkildə sübut edə bilmək eyni şey deyil.”

Kvadratlar cəmi üsulu güclüdür, amma hər qeyri-mənfi polinomu aşağı hesablama xərci ilə əhatə edə bilmir. Bəzi hallarda sübutu tapmaq üçün polinomun dərəcəsini artırmaq lazım gəlir. Dərəcə yüksəldikcə kompüterin həll etməli olduğu problem də sürətlə böyüyə bilər.

Bu tədqiqatın ideyası nədir?

Tədqiqatçıların təklif etdiyi əsas fikir belədir:

Tək bir böyük sübut axtarmaq əvəzinə sahəni hissələrə ayır və hər hissə üçün ayrıca sübut qur.

Bunu gündəlik nümunə ilə düşünək. Bir dağın hər nöqtəsində təhlükəsiz yürüş yolunun olub-olmadığını yoxlamaq istəyirsiniz. Bütün dağı tək bir xəritə izahı ilə sübut etmək çətin ola bilər. Bunun əvəzinə dağı bölgələrə ayırıb hər bölgə üçün ayrıca təhlükəsizlik yoxlaması aparmaq daha idarəolunan ola bilər.

Bu tədqiqatda da oxşar riyazi yanaşmadan istifadə olunur. Polinomun təyin olunduğu bütün sahə hissələrə ayrılır. Hər hissədə həmin bölgəyə məxsus kvadratlar cəmi eyniliyi qurulur. Bütün hissələr birləşdirildikdə isə polinomun ümumilikdə qeyri-mənfi olduğu nəticəsinə gəlinir.

Tədqiqatçılar bu ideyanı “disjunctive sum of squares” adlandırırlar. Azərbaycan dilində bunu “ayrılmış kvadratlar cəmi” və ya “hissələr üzrə kvadratlar cəmi sübutu” kimi düşünmək olar.

Düsturu necə oxumalıyıq?

Məqalədəki əsas quruluş texniki görünə bilər, lakin onun məntiqini sadələşdirmək mümkündür.

Klassik kvadratlar cəmi sübutunda belə bir ifadə axtarılır:

p(x) = kvadratların cəmi

Bu, tək bir eynilikdir. Əgər tapılarsa, p(x)-in qeyri-mənfi olduğu anlaşılır.

Ayrılmış kvadratlar cəmi yanaşmasında isə belə düşünülür:

Sahə bir neçə bölgəyə ayrılır. Hər bölgə müəyyən şərtlərlə təsvir olunur. Məsələn, bir bölgədə q(x) ≥ 0, digər bölgədə isə -q(x) ≥ 0 ola bilər. Bu iki bölgə birlikdə bütün sahəni əhatə edir.

Sonra hər bölgə üçün bu tip eynilik axtarılır:

p(x) = kvadratlar cəmi + bölgə şərti × kvadratlar cəmi

Bu niyə işləyir?

Çünki həmin bölgənin daxilində bölgə şərti artıq qeyri-mənfidir. Kvadratlar cəmi də qeyri-mənfidir. Deməli, sağ tərəf mənfi ola bilməz. Sağ tərəf p(x)-ə bərabər olduğuna görə p(x) də həmin bölgədə mənfi ola bilməz.

Bu əməliyyat bütün bölgələr üçün aparılarsa, polinomun hər yerdə qeyri-mənfi olduğu sübut edilmiş olur.

Şəkil 1 nəyi göstərir?

Məqalədəki Şəkil 1 Motzkin polinomu üçün üç müxtəlif bölmə ideyasını göstərir. Qrafiklərdə ikiölçülü sahə müxtəlif rəngli hissələrə ayrılıb. Hər rəng polinomun qeyri-mənfi olduğunu sübut etmək üçün istifadə olunan fərqli alt bölgəni təmsil edir.

Birinci bölmədə sahə x₁x₂ ifadəsinin işarəsinə görə ayrılır. Yəni x₁x₂ ≥ 0 olan bölgələr və x₁x₂ < 0 olan bölgələr ayrıca qiymətləndirilir.

İkinci bölmədə ayrılma daha sadədir: x₁ ≥ 0 və x₁ < 0 kimi iki yarımsahə üzrə düşünülür.

Üçüncü bölmədə isə daha mürəkkəb, əyrisəl sərhədləri olan ayrılmadan istifadə olunur. Bu da eyni polinom üçün müxtəlif hissələmə strategiyalarının mümkün olduğunu göstərir.

Bu şəklin öyrədici mesajı belədir:
Polinomun qeyri-mənfi olduğunu sübut etmək üçün sahəni yalnız bir üsulla bölmək məcburiyyətində deyilik. Düzgün hissələmə seçildikdə daha aşağı dərəcəli və daha idarəolunan sübutlar tapıla bilər.

“Daha aşağı dərəcə” niyə vacibdir?

Polinomlarda dərəcə artdıqca hesablama çətinləşir. Kvadratlar cəmi üsullarında kompüterin həll etməli olduğu matrislərin ölçüsü də sürətlə böyüyə bilər. Buna görə sübutun daha aşağı dərəcədə qalması hesablama baxımından əhəmiyyətli ola bilər.

Məqalə ayrılmış kvadratlar cəmi yanaşması ilə bəzi hallarda sübutun dərəcəsini polinomun öz dərəcəsi qədər aşağı saxlamağın mümkün olduğunu göstərən nəzəri nəticələr təqdim edir.

Bunu sadələşdirsək:

Klassik yanaşmada bəzən “sübutu tapmaq üçün daha yüksək dərəcəli ifadələrdən istifadə etməliyik” deyilə bilər.
Bu tədqiqatın təklif etdiyi yanaşma isə “dərəcəni artırmaq əvəzinə bölgələrin sayını artıra bilərik” ideyasını önə çıxarır.

Yəni çətinlik tək bir böyük sübuta yüklənmək əvəzinə bir neçə kiçik sübut arasında bölüşdürülür.

Positivstellensatz nə deməkdir?

Məqalədə “disjunctive Positivstellensatz” adlanan nəzəri nəticələr yer alır. Bu termin ilk baxışda ağır görünə bilər, lakin əsas mənası belədir:

Polinomun müsbət və ya qeyri-mənfi olduğunu sübut etmək üçün hansı cəbri sertifikatların kifayət etdiyini bildirən teoremlər.

Bu tədqiqat belə teoremlərin ayrılmış, yəni hissəli versiyasını təqdim edir. Tədqiqatçılar müəyyən şərtlər daxilində polinomun qeyri-mənfi olduğunu hissələrə ayrılmış aşağı dərəcəli kvadratlar cəmi sübutları ilə sertifikatlaşdırmağın mümkün olduğunu göstərirlər.

Bu yalnız texniki detal deyil. Çünki bu cür sertifikatlar optimallaşdırma problemlərində “bu həll həqiqətən aşağı sərhəddirmi?”, “bu matris müəyyən müsbətlik xassəsinə malikdirmi?” və ya “bu modelin təhlükəsiz bölgəsi necə sübut oluna bilər?” kimi suallarda istifadə edilə bilər.

Kompüter baxımından nə dəyişir?

Məqalə bu yanaşmanın kompüterlə həll prosesinə də töhfə verə biləcəyini irəli sürür.

Klassik kvadratlar cəmi yanaşmalarında çox vaxt tək və böyük yarımmüəyyən proqramlaşdırma problemi həll edilir. Bu problemlər böyüdükcə hesablama baxımından bahalı ola bilər.

Ayrılmış yanaşmada isə hər bölgə üçün ayrıca sübut axtarıla bilər. Bu alt problemlər bəzi hallarda paralel həll oluna bilər. Yəni fərqli prosessorlar və ya maşınlar eyni vaxtda fərqli hissələrin sübutunu axtara bilər.

Tədqiqat həmçinin “sabit ölçülü yarımmüəyyən məhdudiyyətlər” ideyasını vurğulayır. Bunun mənası budur: iyerarxiya irəlilədikcə ən böyük matris məhdudiyyətinin ölçüsü davamlı şəkildə böyümək məcburiyyətində olmaya bilər; bunun əvəzinə daha çox bölgə üzrə irəliləmək mümkündür.

Bu, böyükmiqyaslı optimallaşdırma problemlərində potensial olaraq mühüm üstünlükdür. Lakin bunun hər problemdə avtomatik şəkildə daha sürətli olacağını demək olmaz. Bölgələrin sayı artdıqca başqa hesablama xərcləri də yarana bilər.

Optimallaşdırmasız yanaşma nə deməkdir?

Məqalənin digər mühüm hissəsi bəzi hallarda polinomun qeyri-mənfi olduğunu göstərmək üçün optimallaşdırma həll etmədən də iyerarxiya qurmağın mümkün olduğunu izah edir.

Buradakı fikir belədir:
Fəza konus və ya simpleksə bənzər bölgələrə ayrılır. Sonra polinom bu bölgələrdə müəyyən xətti çevirmələrlə yenidən yazılır. Çevirmədən sonra polinomun əmsalları mənfi deyilsə, həmin bölgədə polinomun qeyri-mənfi olduğu nəticəsinə gəlmək olar.

Sadə dillə desək:

Polinomu müxtəlif koordinat sistemlərində yenidən yazırıq. Əgər bu yazılışlarda bütün əmsallar uyğun şəkildə qeyri-mənfi hala gəlirsə, bu bizə polinomun müvafiq bölgədə qeyri-mənfi olduğunu göstərir.

Bu yanaşma həmişə ən səmərəli üsul olmaya bilər, lakin mühüm riyazi fikir təqdim edir: sübut yalnız optimallaşdırma həlledicisindən asılı olmaq məcburiyyətində deyil. Bəzi sübutlar uyğun hissələmə və əmsalların yoxlanması ilə də qurula bilər.

Branch-and-Bound niyə istifadə olunur?

Məqalədə ayrılmış kvadratlar cəmi yanaşmasının branch-and-bound, yəni “budaqlandır və sərhədlə” üsulu ilə birləşdirilə biləcəyi də izah olunur.

Branch-and-bound böyük problemi kiçik alt problemlərə bölən klassik optimallaşdırma strategiyasıdır. Əvvəlcə sahə böyük hissələr şəklində araşdırılır. Əgər bir hissədə nəticə kifayət qədər aydın deyilsə, həmin hissə daha kiçik hissələrə ayrılır.

Bu tədqiqatda da oxşar məntiq var:

• Əvvəlcə geniş bölgə nəzərdən keçirilir.
• Bu bölgədə kifayət qədər sübut tapılmasa, bölgə daha kiçik hissələrə ayrılır.
• Hər hissə üçün aşağı və yuxarı sərhədlər yenilənir.
• Kifayət qədər dəqiqlik əldə edildikdə proses dayandırılır.

Bu üsul bütün sahəni başlanğıcdan çox xırda hissələrə bölmək əvəzinə, yalnız lazım olan bölgələri daha ətraflı araşdırmağa imkan verir. Beləliklə, hesablama resurslarından daha seçici istifadə oluna bilər.

Ədədi təcrübələr nə deyir?

Məqalədəki ədədi təcrübələr üç əsas sahəyə yönəlib:

Birincisi, klassik kvadratlar cəmi testinin minimum dəyəri birbaşa tapmaqda çətinlik çəkdiyi bəzi məşhur polinomlar üzərində təcrübələr aparılır. Motzkin, Robinson və Choi-Lam kimi ədəbiyyatda tanınan nümunələr bu çərçivəyə daxildir.

İkincisi, kopozitiv matris problemləri nəzərdən keçirilir. Kopozitivlik xüsusilə bəzi çətin optimallaşdırma problemləri və kombinator problemlərlə əlaqəli matris xassəsidir.

Üçüncüsü, maksimum klik problemi kimi kombinator optimallaşdırma əlaqələri araşdırılır. Maksimum klik qrafda hər düyünün digərləri ilə əlaqəli olduğu ən böyük alt qrupu tapmaq problemidir. Bu problem kompüter elmi baxımından çətin problemlər arasında yer alır.

Təcrübələrin ümumi mesajı belədir:
Təklif olunan hissəli yanaşma bəzi çətin nümunələrdə aşağı dərəcəli və ya daha idarəolunan sertifikatlar tapa bilir və branch-and-bound ilə birlikdə istifadə oluna bilər.

Lakin bu nəticələr bütün problem sinifləri üçün ümumi performans zəmanəti kimi qəbul edilməməlidir. Bunlar seçilmiş riyazi və optimallaşdırma nümunələri üzərində aparılmış təcrübələrdir.

Bu niyə vacibdir?

Bu tədqiqat ilk baxışda çox abstrakt görünə bilər. Lakin əsas ideya bir çox elmi və mühəndislik sahəsini maraqlandırır.

İdarəetmə sistemlərində sistemin təhlükəsiz və ya dayanıqlı olduğunu sübut etmək lazım gələ bilər. Robototexnikada hərəkət planının müəyyən sərhədlər daxilində qalıb-qalmadığı araşdırıla bilər. Statistikada və ya maşın öyrənməsində bəzi optimallaşdırma problemləri üçün etibarlı aşağı sərhədlər axtarıla bilər. Kombinator optimallaşdırmada çox böyük axtarış sahələri daha idarəolunan hissələrə bölünə bilər.

Bu sahələrin ortaq ehtiyacı budur:
Kompüterin yalnız cavab verməsi deyil, həmin cavabın niyə etibarlı olduğunu da sübut edə bilməsi.

Ayrılmış kvadratlar cəmi yanaşması belə sübutları tək böyük quruluş əvəzinə bir neçə kiçik quruluş üzərindən yaratmağa çalışır. Bu da gələcəkdə daha miqyaslana bilən və paralel işləyə bilən riyazi sertifikat üsulları üçün mühüm tədqiqat istiqaməti ola bilər.

Diqqət edilməli məqamlar

Bu tədqiqat nəzəri riyaziyyat və optimallaşdırma sahəsinə aiddir. Buna görə gündəlik tətbiq məhsulu kimi şərh edilməməlidir.

Birincisi, tədqiqat preprint xarakterlidir və rəyçi qiymətləndirməsindən keçməyib. Nəticələrin akademik ictimaiyyət tərəfindən qiymətləndirilməsi və fərqli tədqiqatlarla dəstəklənməsi vacibdir.

İkincisi, yanaşma bəzi hallarda hesablama üstünlüyü verə bilər; lakin bu, hər problemdə klassik üsullardan daha sürətli və ya daha asan olacağı demək deyil. Bölgələrin sayının artması ayrıca hesablama xərci də yarada bilər.

Üçüncüsü, məqalədəki təcrübələr müəyyən polinomlar, matris problemləri və kombinator optimallaşdırma nümunələri üzərində aparılıb. Fərqli problem ölçülərində və tətbiq sahələrində performans ayrıca araşdırılmalıdır.

Dördüncüsü, yazıda keçən kvadratlar cəmi, yarımmüəyyən proqramlaşdırma, Positivstellensatz, kopozitivlik kimi anlayışlar yüksək səviyyəli riyazi alətlərdir. Bu məzmunda məqsəd həmin alətləri bütün detalları ilə öyrətmək deyil, tədqiqatın əsas ideyasını anlaşıqlı etməkdir.

Nəticə

Bu tədqiqat polinomların qeyri-mənfi olduğunu sübut etmək üçün yeni baxış bucağı təqdim edir. Klassik kvadratlar cəmi yanaşması tək bir cəbri eynilik axtararkən, ayrılmış kvadratlar cəmi yanaşması sahəni hissələrə bölür və hər hissə üçün ayrıca sübut qurur.

Bu ideya xüsusilə çətin polinomlarda daha aşağı dərəcəli sübutlar əldə etmək, alt problemləri paralel həll etmək və branch-and-bound kimi üsullarla daha seçici axtarış aparmaq potensialına malikdir.

Tədqiqatın əsas mesajı budur:
Bəzi riyazi sübutlar tək parça halında çətin ola bilər; lakin düzgün şəkildə bölündükdə daha idarəolunan hala gələ bilər.

Bu baxış gələcəkdə etibarlı optimallaşdırma, idarəetmə sistemləri, robototexnika, statistika və kompüter dəstəkli riyazi sübutlar üçün yeni üsulların hazırlanmasına töhfə verə bilər.

Mənbə və metod qeydi

Bu məzmun Amir Ali Ahmadi, Sanjeeb Dash, Yixuan Hua və Bartolomeo Stellato tərəfindən hazırlanmış “Disjunctive Sum of Squares” adlı akademik tədqiqatdan istifadə edilməklə Verianla redaksiya formatında orijinal şəkildə hazırlanıb.

Bu tədqiqat preprint xarakterlidir və rəyçi qiymətləndirməsindən keçməyib. Məzmun məlumatlandırma və təhsil məqsədi daşıyır. Riyazi optimallaşdırma, mühəndislik dizaynı, idarəetmə sistemi təhlili və ya peşəkar hesablama məsləhətini əvəz etmir.