Utafiti huu unaeleza utekelezaji wa Matlab wa algoriti ya arc-search infeasible interior-point kwa linear programming, ambayo mpaka wake wa iteresheni za kipolinomia umetolewa kama O(√nL). arcLP hutatua tatizo la kawaida la kupunguza \(c^Tx\) chini ya masharti \(Ax=b\) na \(x\ge0\), huku programu ikijumuisha pre-processing, uchaguzi wa nukta ya kuanzia, utatuzi wa mifumo sparse ya Cholesky, pembe ya hatua ya arc-search, centering parameter, utunzaji wa degeneracy, post-processing na ukaguzi wa mwisho wa optimality.

Katika quality control, arcLP ililinganishwa na utekelezaji wa Matlab wa Mehrotra predictor-corrector kwa matatizo ya Netlib kwa kutumia nukta zilezile za kuanzia, pre/post-processing sawa na termination criteria sawa. Hesabu ya moja kwa moja ya jedwali lenye matatizo 51 inaonyesha arcLP ilitumia iteresheni chache katika matatizo 24, idadi sawa katika 11 na iteresheni nyingi katika 16. Jumla ni iteresheni 1084 kwa arcLP dhidi ya 1099 kwa Mehrotra. Equality-constraint residual ilikuwa ndogo kwa arcLP katika matatizo 34, sawa katika moja na kubwa katika 16.

Kikomo muhimu cha tafsiri ni kwamba Software Metapaper hii ya 2026 haitoi upya uthibitisho kamili wa mpaka wa O(√nL). Hoja hiyo ya kinadharia inaelekezwa kwenye kazi ya awali; mchango wa moja kwa moja wa makala hii ni utekelezaji wa programu, mikakati ya numerical computation na benchmark testing.

Tatizo la primal na dual

\[ \min c^Tx,\qquad Ax=b,\quad x\ge0. \tag{1} \]

Ambapo \(A\in\mathbb{R}^{m\times n}\), \(b\in\mathbb{R}^m\), \(c\in\mathbb{R}^n\), na \(x\in\mathbb{R}^n\).

Dual yake ni:

\[ \max b^T\lambda,\qquad A^T\lambda+s=c,\quad s\ge0. \tag{2} \]

Interior-point algorithm huanza na \((x^0,s^0)>0\) na huweka \(x^k,s^k\) zikiwa chanya katika iteresheni zote.

Uchaguzi wa nukta ya kuanzia

\[ \max\left\{ \|Ax^0-b\|, \|A^T\lambda^0+s^0-c\|, \frac{(x^0)^Ts^0}{n} \right\}. \tag{3} \]

Programu hutengeneza candidates mbili kwa mbinu zilizotajwa katika chanzo na huchagua ile yenye thamani ndogo ya kipimo hiki.

Uwiano wa ukubwa wa vipengele vya A

\[ \frac{\max |A_{i,j}|} {\min\{|A_{k,l}|:A_{k,l}\neq0\}}. \tag{4} \]

Makala inaeleza kuwa general matrix scaling haikuonyesha faida ya jumla ya computational efficiency katika uchambuzi wa awali, hivyo scaling haijaingizwa kama hatua ya kawaida. Hata hivyo uwiano huu hutumiwa kuamua kama kanuni fulani ya pre-processing inahitajika. Maelezo ya mapema ya `calRatioCondition(A)` na sehemu ya baadaye kuhusu kutotumia scaling hayalingani kikamilifu katika maneno, hivyo tofauti hiyo inapaswa kuhifadhiwa.

Sparse Cholesky linear algebra

\[ AD^2A^Tu=L\Lambda L^Tu=v. \tag{5} \]

Kwa mujibu wa chanzo, kutatua mifumo ya aina hii ndiyo gharama kuu ya computational work ya algoriti.

Degenerate solutions

arcLP ina optional procedure ya kushughulikia degenerate solutions. Parameter \(d=1\) hutumia utaratibu huu, wakati \(d=0\) ni chaguo la kawaida lisiloutumia. `makeAfull(...)` inaweza kutumia Markowitz pivot criterion kuondoa dependent rows huku ikijaribu kuhifadhi sparsity.

Arc-search angle na centering parameter

Badala ya kusonga kwenye mstari ulionyooka pekee kuelekea optimizer, arcLP hutumia trajectory ya arc. Step angle inaweza kuhesabiwa analytically. Centering parameter \(\sigma_k\) huchaguliwa kwa specialized Golden Section search. Chanzo kinasema classical Golden Section hupunguza interval hadi takriban 0.618 ya urefu wake, ilhali utaratibu uliotumiwa hapa huipunguza hadi 0.5 katika kila iteration.

\[ \alpha_k=\min\{0.9999\alpha_k,\;0.99\pi/2\}<0.99\pi/2. \]

Rescaling hii inalenga kuzuia \(x^k\) na \(s^k\) zisikaribie sifuri haraka mno katika iterations za mwanzo na kupunguza matatizo ya numerical stability.

Kugundua unbounded na infeasible instances

Kwa unboundedness, mojawapo ya checks ni:

\[ \max_i|x_i|>10^{10}. \]

Kwa infeasibility, mojawapo ni:

\[ \max_i|\lambda_i|>10^{10}. \]

Kutopatikana kwa step size inayohifadhi positivity ya \(x,s\) huku ikipunguza duality gap pia hutumiwa kama indicator. Makala yenyewe inaita matokeo ya checks hizi “reasonable detection” baada ya numerical tests; kwa hiyo hazipaswi kutafsiriwa kama uthibitisho wa universal classification kwa kila LP.

Termination criterion

\[ \frac{\|r_b^k\|}{\max\{1,\|b\|\}}+ \frac{\|r_c^k\|}{\max\{1,\|c\|\}}+ \frac{\mu_k}{\max\{1,|c^Tx^k|,|b^T\lambda^k|\}} <10^{-8}, \]

\[ r_b^k=Ax^k-b,\qquad r_c^k=A^T\lambda^k+s^k-c. \]

Programu pia inaweza kusimama ikiwa primal na dual step sizes zote ziko chini ya \(10^{-8}\), au chini ya masharti mengine ya numerical deterioration yaliyoainishwa na chanzo.

Utafiti unasema nini, na hausomi nini?

Utafiti unaonyesha kuwa arcLP ni Matlab solver inayofanya kazi, imepata optimal solutions katika benchmark zilizoripotiwa na inaweza kushindana computationally na Mehrotra implementation. Hata hivyo hauonyeshi kuwa arcLP ni bora katika kila tatizo, kila computer architecture au dhidi ya kila commercial solver. Pia makala hii haijarudia proof kamili ya O(√nL).

Umuhimu unaowezekana katika Afrika Mashariki

Utafiti haukutumia dataset maalumu ya Afrika Mashariki. Hata hivyo linear programming ni msingi wa matatizo ya optimization katika mipango ya nishati, logistics, usafiri, uzalishaji, allocation ya rasilimali na operations research. Kwa hiyo arcLP inaweza kuwa muhimu katika teaching na methodological research katika vyuo vikuu na taasisi za utafiti za Afrika Mashariki. Matumizi katika mifumo halisi yanahitaji validation ya ndani kulingana na ukubwa wa tatizo, computational infrastructure, data quality na software integration; matokeo ya Netlib hayawezi kuhamishwa moja kwa moja kuwa ahadi ya performance katika mfumo wowote wa eneo hili.

Mbinu na Matokeo ya Utafiti

[x,obj,kk,infe,lambda,s,exflag]=arcLP(A,b,c,d,tol,iter)

Mfano rahisi

\[ \min x_1,\qquad x_1+x_2=5,\quad x_1,x_2\ge0. \]

Kwa \(A=[1\;1]\), \(b=5\), \(c=[1\;0]^T\), chanzo kinaripoti arcLP kupata \(x^*=[0\;5]^T\) katika iterations tano.

Matokeo kamili ya Netlib yaliyoripotiwa

Jedwali linaonyesha faida na hasara zote mbili. Mfano, Qap15+ ina 44 dhidi ya 28 iterations na residual 1.5e–05 dhidi ya 8.4e–08 kwa faida ya arcLP; lakini Degen3* ina 22 dhidi ya 35 iterations na residual 1.2e–09 dhidi ya 8.6e–08 kwa faida ya Mehrotra. Hivyo hitimisho sahihi ni computational competitiveness, si universal dominance.

Maelezo ya Chanzo na Mbinu

Mwandishi: Yaguang Yang, Independent Researcher, US.

DOI: 10.5334/jors.674.

Jarida: Journal of Open Research Software, 14(1):57.

Mchapishaji: Ubiquity Press.

Tarehe ya uchapishaji: 12 Agosti 2026.

Aina: Software Metapaper iliyopitia peer review.

Leseni ya makala: CC BY 4.0. Leseni ya software: BSD 3-Clause.

Software version: 1.0. Tarehe ya software imeandikwa “08/02/2026” katika chanzo; kwa kuwa format haijaelezwa, haibadilishwi kuwa tafsiri moja ya siku/mwezi.

Funding: JORS iliondoa publication fee; hakuna separate research grant iliyoripotiwa.

Competing interests: mwandishi ametangaza kuwa hana competing interests.

Kikomo cha kisayansi: proof kamili ya O(√nL) na performance-profile analysis iliyorejelewa haijatolewa upya katika makala hii. Numerical benchmark inaunga mkono competitiveness ya arcLP, si superiority katika kila hali.