Kwanza Swali Rahisi: Je, Kielezo Huwa Chanya Daima?

Katika hisabati wakati mwingine tunataka kuthibitisha kwamba kielezo hakikosi kuwa hasi. Kwa mfano katika mfano wa uhandisi kiasi cha nishati, thamani ya makosa, kazi ya hatari au hesabu ya gharama haipaswi kuwa chini ya sifuri chini ya masharti fulani. Katika uboreshaji unaosaidiwa na kompyuta maswali kama haya pia huonekana mara kwa mara:

«Je, fomula hii hubaki katika kipindi salama katika kila hali?»
«Je, thamani ndogo zaidi ya kazi hii ya gharama ni nini?»
«Je, kielezo kinachoonyesha utulivu wa mfumo huu ni muundo usiohasi kweli?»

Katika maswali kama haya polinomu mara nyingi ndizo kiini. Polinomu ni misemo ya kihisabati iliyojengwa kwa nguvu za vigezo. Kwa mfano kielezo kama x² + y² ni polinomu na daima ni sifuri au chanya. Kwa sababu mraba wa nambari hauwezi kuwa hasi.

Lakini mambo si rahisi kila wakati. Kadri idadi ya vigezo na daraja inavyoongezeka, kuelewa kwamba polinomu haipatikani hasi kila mahali inaweza kuwa ngumu zaidi.

«Jumla ya Miraba» Inamaanisha Nini?

Mojawapo ya mawazo ya jadi na yenye nguvu ni hili:
Ikiwa polinomu inaweza kuandikwa kama jumla ya miraba ya polinomu nyingine, hiyo polinomu haiwezi kuwa hasi.

Kwa sababu miraba daima ni sifuri au chanya. Kwa mfano:

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

Kwa polinomu p(x) inayoweza kuandikwa kwa njia hii matokeo ni wazi: p(x) haiwezi kuwa hasi. Njia hii huitwa «sum of squares», yaani «jumla ya miraba».

Wazo hili ni safi kihisabati na linaweza kutumika na kompyuta. Kwa sababu kuchunguza kama polinomu ni jumla ya miraba kunaweza kufanywa kwa njia za uboreshaji zinazoitwa yarı tanımlı programlama chini ya masharti fulani.

Hata hivyo kuna tatizo muhimu hapa:
Si kila polinomu isiyo hasi inaweza kuandikwa kama jumla ya miraba.

Yaani polinomu inaweza kweli kutochukua thamani hasi; lakini kuithibitisha kwa utambulisho mmoja wa jumla ya miraba inaweza kuwa haiwezekani.

Kwa Nini Polinomu ya Motzkin Ni Muhimu?

Mojawapo ya mifano kuu ya makala ni polinomu ya Motzkin. Polinomu hii ni mfano maarufu katika hisabati. Kwa sababu ni mojawapo ya polinomu zisizo hasi lakini si jumla ya miraba kwa maana ya jadi.

Kwa maneno rahisi:
Polinomu ya Motzkin ni polinomu isiyo hasi kweli; lakini haiwezekani kuonyesha hili kwa kielezo kimoja cha jumla ya miraba cha kawaida.

Hali hii inamwambia msomaji hili:

«Jambo kuwa kweli na uwezo wa kulithibitisha kwa njia rahisi si kitu kimoja.»

Njia ya jumla ya miraba ni yenye nguvu; lakini haiwezi kukamata kila polinomu isiyo hasi kwa gharama ndogo. Katika baadhi ya hali kupata uthibitisho kunahitaji kuongeza daraja la polinomu. Kadri daraja linavyoongezeka tatizo linalopaswa kutatuliwa na kompyuta pia linaweza kukua haraka.

Wazo la Utafiti Huu Ni Nini?

Wazo kuu linalopendekezwa na watafiti ni hili:

Badala ya kutafuta uthibitisho mmoja mkubwa, gawanya eneo na tengeneza uthibitisho tofauti kwa kila sehemu.

Tufikirie kwa mfano wa kila siku. Unataka kuangalia kama kuna njia salama ya kutembea kila sehemu ya mlima. Kuithibitisha mlima mzima kwa maelezo moja ya ramani inaweza kuwa ngumu. Badala yake kugawanya mlima katika maeneo na kufanya ukaguzi wa usalama tofauti kwa kila eneo inaweza kuwa rahisi kudhibiti.

Katika utafiti huu pia njia ya kihisabati kama hiyo inatumika. Eneo lote ambalo polinomu limefafanuliwa linagawanywa katika sehemu. Katika kila sehemu utambulisho wa jumla ya miraba maalum kwa eneo hilo unajengwa. Sehemu zote zikiunganishwa inafikia hitimisho kwamba polinomu kwa ujumla haipatikani hasi.

Watafiti wanaita wazo hili «disjunctive sum of squares». Kwa Kiswahili tunaweza kuifikiria kama «jumla ya miraba iliyotenganishwa» au «uthibitisho wa jumla ya miraba ya sehemu».

Tunapaswa Kusoma Fomula Vipi?

Muundo wa msingi katika makala unaweza kuonekana wa kiufundi; lakini mantiki yake inaweza kurahisishwa.

Katika uthibitisho wa jumla ya miraba ya jadi kinachotafutwa ni hiki:

p(x) = jumla ya miraba

Huu ni utambulisho mmoja. Ikiwa unapatikana, inaeleweka kwamba p(x) haipatikani hasi.

Katika njia ya jumla ya miraba iliyotenganishwa tunafikiria hivi:

Eneo linagawanywa katika maeneo kadhaa. Kila eneo linafafanuliwa kwa masharti fulani. Kwa mfano katika eneo moja q(x) ≥ 0 inaweza kutokea, katika lingine -q(x) ≥ 0 inaweza kutokea. Maeneo haya mawili pamoja yanashughulikia eneo lote.

Kisha kwa kila eneo utambulisho wa aina hii unatafutwa:

p(x) = jumla ya miraba + sharti la eneo × jumla ya miraba

Kwa nini hii inafanya kazi?

Kwa sababu ndani ya eneo hilo sharti la eneo tayari si hasi. Jumla ya miraba pia si hasi. Basi upande wa kulia hauwezi kuwa hasi. Kwa kuwa upande wa kulia ni sawa na p(x), p(x) pia haiwezi kuwa hasi katika eneo hilo.

Ikiwa hatua hii inafanywa kwa maeneo yote, inathibitishwa kwamba polinomu haipatikani hasi kila mahali.

Je, Kielelezo 1 Kinasema Nini?

Kielelezo 1 katika makala kinaonyesha mawazo matatu tofauti ya ugawanyaji kwa polinomu ya Motzkin. Katika grafu eneo la vipimo viwili limegawanywa katika sehemu za rangi tofauti. Kila rangi inawakilisha eneo dogo tofauti linalotumika kuthibitisha kwamba polinomu haipatikani hasi.

Katika sehemu ya kwanza eneo linagawanywa kulingana na ishara ya kielezo x₁x₂. Yaani maeneo ambapo x₁x₂ ≥ 0 na maeneo ambapo x₁x₂ < 0 hutathminiwa tofauti.

Katika sehemu ya pili ugawanyaji ni rahisi zaidi: inaweza kufikiriwa kwa nusu maeneo kama x₁ ≥ 0 na x₁ < 0.

Katika sehemu ya tatu ugawanyaji tata zaidi wenye mipaka ya mviringo unatumika. Hii pia inaonyesha kwamba mikakati tofauti ya ugawanyaji inawezekana kwa polinomu hiyo hiyo.

Ujumbe wa kufundishia wa kielelezo hiki ni huu:
Ili kuthibitisha kwamba polinomu haipatikani hasi hatulazimiki kugawanya eneo kwa njia moja tu. Ugawanyaji sahihi ukichaguliwa, uthibitisho wa daraja la chini na unaodhibitiwa zaidi unaweza kupatikana.

Kwa Nini «Daraja la Chini» Ni Muhimu?

Kadri daraja la polinomu linavyoongezeka hesabu inakuwa ngumu zaidi. Katika njia za jumla ya miraba ukubwa wa matriki ambazo kompyuta inapaswa kutatua pia unaweza kukua haraka. Kwa hiyo kuwa na uthibitisho wa daraja la chini kunaweza kuwa muhimu kwa hesabu.

Makala inatoa matokeo ya nadharia yanayoonyesha kwamba kwa njia ya jumla ya miraba iliyotenganishwa katika baadhi ya hali inawezekana kuweka daraja la uthibitisho chini kama daraja la polinomu mwenyewe.

Tukirahisisha:

Katika njia ya jadi wakati mwingine inaweza kusemwa «lazima tutumie misemo ya daraja la juu zaidi ili kupata uthibitisho».
Njia inayopendekezwa na utafiti huu inasisitiza wazo la «badala ya kuongeza daraja tunaweza kuongeza idadi ya maeneo».

Yaani ugumu hauwekwi kwenye uthibitisho mmoja mkubwa; unagawanywa kwa uthibitisho kadhaa mdogo.

Positivstellensatz Inamaanisha Nini?

Makala ina matokeo ya nadharia yanayoitwa «disjunctive Positivstellensatz». Neno hili linaweza kuonekana nzito kwa mtazamo wa kwanza; lakini maana yake ya msingi ni hii:

Nadharia zinazosema ni cheti gani cha kialjebra kinachotosha kuthibitisha kwamba polinomu ni chanya au si hasi.

Utafiti huu unatoa toleo lililotenganishwa, yaani la sehemu, la nadharia kama hizi. Watafiti wanaonyesha kwamba chini ya masharti fulani inawezekana kuthibitisha kwamba polinomu haipatikani hasi kwa uthibitisho wa jumla ya miraba ya daraja la chini ulio gawanywa katika sehemu.

Hii si tu maelezo ya kiufundi. Kwa sababu cheti kama hizi zinaweza kutumika katika matatizo ya uboreshaji kwa maswali kama «je, suluhisho hili ni chini ya kweli?», «je, matriki hii ina sifa fulani ya kuwa chanya?» au «eneo salama la mfumo huu linathibitishwaje?»

Nini Kinabadilika Kwa Mtazamo wa Kompyuta?

Makala inadai kwamba njia hii inaweza pia kuchangia upande wa utatuzi wa kompyuta.

Katika njia za jumla ya miraba za jadi mara nyingi tatizo moja kubwa la yarı tanımlı programlama hutatuliwa. Matatizo haya yanapokua yanaweza kuwa ghali.

Katika njia iliyotenganishwa uthibitisho tofauti unaweza kutafutwa kwa kila eneo. Matatizo haya madogo katika baadhi ya hali yanaweza kutatuliwa kwa sambamba. Yaani prosesa au mashine tofauti zinaweza kutafuta uthibitisho wa sehemu tofauti kwa wakati mmoja.

Utafiti pia unasisitiza wazo la «vikwazo vya yarı tanımlı vya ukubwa usiobadilika». Maana yake: kadri mfumo wa ngazi unavyoendelea ukubwa wa kikwazo cha matriki kikubwa zaidi hauhitaji kukua kila mara; badala yake inaweza kuendelea kupitia maeneo zaidi.

Hii inaweza kuwa faida muhimu katika matatizo makubwa ya uboreshaji. Hata hivyo haiwezi kusemwa kwamba itakuwa haraka kiotomatiki katika kila tatizo. Kadri idadi ya maeneo inavyoongezeka gharama nyingine pia zinaweza kutokea.

Njia Isiyo na Uboreshaji Inamaanisha Nini?

Sehemu nyingine muhimu ya makala inaeleza kwamba katika baadhi ya hali inawezekana kujenga mfumo wa ngazi bila kutatua uboreshaji ili kuonyesha kwamba polinomu haipatikani hasi.

Wazo hapa ni hili:
Nafasi inagawanywa katika maeneo kama koni au simpleks. Kisha polinomu huandikwa upya katika maeneo haya kwa mabadiliko ya mstari fulani. Ikiwa baada ya mabadiliko kiwango cha polinomu si hasi, inaeleweka kwamba polinomu haipatikani hasi katika eneo hilo.

Kwa maneno rahisi:

Tunaandika upya polinomu katika mifumo tofauti ya kuratibu. Ikiwa katika maandishi haya viwango vyote vinakuwa visivyo hasi kwa njia inayofaa, hii inatuonyesha kwamba polinomu haipatikani hasi katika eneo husika.

Njia hii inaweza isiwe njia bora zaidi kila wakati; lakini inatoa wazo muhimu la kihisabati: uthibitisho hauhitaji kutegemea tu kisuluhishi cha uboreshaji. Baadhi ya uthibitisho pia unaweza kujengwa kwa ugawanyaji unaofaa na ukaguzi wa viwango.

Kwa Nini Branch-and-Bound Inatumika?

Makala pia inaeleza kwamba njia ya jumla ya miraba iliyotenganishwa inaweza kuunganishwa na njia ya branch-and-bound, yaani «tenganisha na pima».

Branch-and-bound ni mkakati wa jadi wa uboreshaji unaogawanya tatizo kubwa katika matatizo madogo. Kwanza eneo linachunguzwa kwa sehemu kubwa. Ikiwa matokeo katika sehemu moja hayatoshi kuwa wazi, sehemu hiyo inagawanywa zaidi.

Katika utafiti huu pia kuna mantiki kama hiyo:

• Kwanza eneo pana linashughulikiwa.
• Ikiwa uthibitisho wa kutosha haujapatikana katika eneo hili, eneo linagawanywa katika sehemu ndogo zaidi.
• Kwa kila sehemu mipaka ya chini na ya juu inasasishwa.
• Mchakato unasimama utakapopatikana usahihi wa kutosha.

Njia hii inatumika kuchunguza zaidi maeneo yanayohitajika badala ya kugawanya eneo lote tangu mwanzo katika sehemu ndogo sana. Hivyo rasilimali za hesabu zinaweza kutumika kwa uchaguzi zaidi.

Je, Majaribio ya Nambari Yanasema Nini?

Majaribio ya nambari katika makala yanalenga maeneo matatu kuu:

Kwanza, majaribio yanafanywa kwenye polinomu maarufu ambapo jaribio la jumla ya miraba la jadi lilipata shida kupata thamani ndogo zaidi moja kwa moja. Mifano inayojulikana katika fasihi kama Motzkin, Robinson na Choi-Lam iko katika upeo huu.

Pili, matatizo ya matriki ya kopozitif yanashughulikiwa. Kopozitiflik ni sifa ya matriki inayohusiana hasa na baadhi ya matatizo magumu ya uboreshaji na ya muunganiko.

Tatu, uhusiano wa uboreshaji wa muunganiko kama tatizo la kliki la juu zaidi unachunguzwa. Kliki la juu zaidi ni tatizo la kupata kikundi kidogo cha juu zaidi katika grafu ambapo kila kituo kimeunganishwa na kingine. Tatizo hili liko kati ya matatizo magumu katika sayansi ya kompyuta.

Ujumbe wa jumla wa majaribio ni huu:
Njia iliyopendekezwa ya sehemu inaweza kupata cheti cha daraja la chini au kinachodhibitiwa zaidi katika baadhi ya mifano magumu na inaweza kutumika pamoja na branch-and-bound.

Hata hivyo matokeo haya hayapaswi kusomwa kama dhamana ya utendaji wa jumla katika madarasa yote ya matatizo. Hizi ni majaribio yaliyofanywa kwenye mifano iliyochaguliwa ya kihisabati na uboreshaji.

Kwa Nini Hii Ni Muhimu?

Utafiti huu unaweza kuonekana abstract sana kwa mtazamo wa kwanza. Lakini wazo kuu linahusisha maeneo mengi ya kisayansi na uhandisi.

Katika mifumo ya udhibiti inaweza kuhitajika kuthibitisha kwamba mfumo ni salama au thabiti. Katika robotiki mpango wa mwendo unaweza kuchunguzwa kama unabaki ndani ya mipaka fulani. Katika takwimu au ujifunzaji wa mashine mipaka ya chini ya kuaminika ya baadhi ya matatizo ya uboreshaji inaweza kutafutwa. Katika uboreshaji wa muunganiko maeneo makubwa ya utafutaji yanaweza kugawanywa katika sehemu zinazodhibitiwa zaidi.

Mahitaji ya pamoja ya maeneo haya ni hili:
Sio tu kwamba kompyuta itoe jibu, bali pia iweze kuthibitisha kwa nini jibu hilo ni la kuaminika.

Njia ya jumla ya miraba iliyotenganishwa inajaribu kujenga uthibitisho kama huo kupitia miundo kadhaa midogo badala ya muundo mmoja mkubwa. Hii pia inaweza kuwa mwelekeo muhimu wa utafiti kwa njia za cheti za kihisabati zinazoweza kupanuka zaidi na kufanya kazi kwa sambamba siku zijazo.

Mambo ya Kuzingatia

Utafiti huu uko katika eneo la hisabati ya nadharia na uboreshaji. Kwa hiyo haupaswi kufasiriwa kama bidhaa ya matumizi ya kila siku.

Kwanza, utafiti ni preprint na haujapitia tathmini ya riwaya. Ni muhimu kwamba matokeo yatakapotathminiwa na jamii ya kitaaluma na kusaidiwa na utafiti mwingine.

Pili, njia inaweza kutoa faida ya hesabu katika baadhi ya hali; lakini hii haimaanishi kwamba itakuwa haraka au rahisi zaidi kuliko njia za jadi katika kila tatizo. Kuongezeka kwa idadi ya maeneo pia kunaweza kuunda gharama tofauti ya hesabu.

Tatu, majaribio katika makala yamefanywa kwenye polinomu maalum, matatizo ya matriki na mifano ya uboreshaji wa muunganiko. Utendaji katika ukubwa tofauti wa matatizo na maeneo ya matumizi unapaswa kuchunguzwa zaidi.

Nne, dhana kama jumla ya miraba, yarı tanımlı programlama, Positivstellensatz, kopozitiflik zinazotajwa katika maandishi ni zana za kihisabati za kiwango cha juu. Lengo katika maudhui haya si kufundisha zana hizi kwa kina, bali kufanya wazo kuu la utafiti liweze kueleweka.

Hitimisho

Utafiti huu unatoa mtazamo mpya wa kuthibitisha kwamba polinomu haipatikani hasi. Njia ya jumla ya miraba ya jadi inatafuta utambulisho mmoja wa kialjebra, njia ya jumla ya miraba iliyotenganishwa inagawanya eneo na kutengeneza uthibitisho tofauti kwa kila sehemu.

Wazo hili lina uwezo wa kupata uthibitisho wa daraja la chini hasa katika polinomu magumu, kutatua matatizo madogo kwa sambamba na kufanya utafutaji wa uchaguzi zaidi kwa njia kama branch-and-bound.

Ujumbe mkuu wa utafiti ni huu:
Baadhi ya uthibitisho wa kihisabati unaweza kuwa mgumu kama kipande kimoja; lakini unapogawanywa kwa usahihi unaweza kuwa rahisi kudhibiti.

Mtazamo huu unaweza kuchangia maendeleo ya njia mpya kwa uboreshaji wa kuaminika, mifumo ya udhibiti, robotiki, takwimu na uthibitisho wa kihisabati unaosaidiwa na kompyuta siku zijazo.

Chanzo na Dokezo la Mbinu

Maudhui haya yameandaliwa kwa muundo wa kihariri wa Verianla kwa kuzingatia kazi ya kitaaluma «Disjunctive Sum of Squares» iliyotayarishwa na Amir Ali Ahmadi, Sanjeeb Dash, Yixuan Hua na Bartolomeo Stellato.

Utafiti huu ni preprint na haujapitia tathmini ya riwaya. Maudhui yameandaliwa kwa madhumuni ya taarifa na elimu. Hayachukui nafasi ya uboreshaji wa kihisabati, muundo wa uhandisi, uchambuzi wa mfumo wa udhibiti au ushauri wa kitaalamu wa hesabu.