Bu tədqiqat xətti proqramlaşdırma üçün nəzəri olaraq işlənmiş və polinom iterasiya həddi O(√nL) kimi verilmiş qövs-axtarışlı qeyri-mümkün başlanğıclı daxili nöqtə alqoritmini işlək Matlab proqramına çevirir. arcLP standart formada \(Ax=b,\;x\ge0\) məhdudiyyətləri altında \(c^Tx\) məqsəd funksiyasını minimallaşdırır və ilkin emal, başlanğıc nöqtəsinin seçilməsi, seyrək Cholesky sistemlərinin həlli, qövs addım bucağı, mərkəzləşdirmə parametri, degenerasiya seçimi, son emal və optimalıq yoxlamasını birləşdirir.
Proqram Netlib-in standart xətti proqramlaşdırma sınaqları üzərində Mehrotra predictor-corrector tətbiqi ilə eyni başlanğıc nöqtələri, eyni ilkin/son emal və eyni dayandırma meyarları altında müqayisə edilib. Mənbənin Cədvəl 1-də verdiyi 51 problem üzrə Verianla sayımında arcLP 24 problemdə daha az, 11-də eyni, 16-da isə daha çox iterasiya tələb edir; ümumi iterasiya sayı arcLP üçün 1084, Mehrotra üçün 1099-dur. Bərabərlik məhdudiyyətinin qalıq göstəricisi arcLP-də 34 problemdə daha kiçik, 1 problemdə eyni, 16 problemdə daha böyükdür.
Əsas elmi məhdudiyyət budur ki, bu 2026-cı il proqram metameqaləsi O(√nL) yaxınlaşma sübutunu yenidən çıxarmır. Həmin nəzəri nəticə əvvəlki işə istinadla qəbul edilir; bu məqalənin birbaşa töhfəsi tətbiq arxitekturası, hesablama strategiyaları və benchmark yoxlanışıdır.
Standart xətti proqramlaşdırma modeli
\[ \min c^Tx,\qquad Ax=b,\quad x\ge0. \tag{1} \]
Burada \(A\in\mathbb{R}^{m\times n}\), \(b\in\mathbb{R}^{m}\), \(c\in\mathbb{R}^{n}\), optimallaşdırılan dəyişən isə \(x\in\mathbb{R}^{n}\)-dir.
Dual məsələ:
\[ \max b^T\lambda,\qquad A^T\lambda+s=c,\quad s\ge0. \tag{2} \]
\(\lambda\) dual dəyişənlər, \(s\) dual slack vektorudur. Alqoritm \((x^0,s^0)>0\) daxili nöqtəsindən başlayır və iterasiyalarda \((x^k,s^k)>0\) müsbətliyini qoruyaraq KKT şərtlərinə yaxınlaşır.
Başlanğıc nöqtəsinin seçilməsi
İki namizəd başlanğıc nöqtə üçün aşağıdakı meyar hesablanır:
\[ \max\left\{ \|Ax^0-b\|, \|A^T\lambda^0+s^0-c\|, \frac{(x^0)^Ts^0}{n} \right\}. \tag{3} \]
Daha kiçik qiymət verən namizəd seçilir. Məqsəd başlanğıcdakı primal qalıq, dual qalıq və complementarity səviyyəsini birlikdə nəzərə almaqdır.
Matrisin qiymət diapazonu
\[ \frac{\max |A_{i,j}|} {\min\{|A_{k,l}|:A_{k,l}\neq0\}}. \tag{4} \]
Mənbə ümumi matris scaling əməliyyatının səmərəliliyi artırmadığını və buna görə əsas tətbiqə daxil edilmədiyini bildirir. Bununla yanaşı bu nisbət ilkin emal qaydalarından birinin lazım olub-olmadığını müəyyən etmək üçün istifadə olunur. Məqalənin əvvəlində `calRatioCondition(A)` funksiyasının scaling qərarı ilə əlaqələndirilməsi ilə sonrakı “scaling daxil edilməyib” ifadəsi arasında redaksiya səviyyəsində fərq vardır və bu fərq saxlanmalıdır.
Seyrək Cholesky sistemi
Əsas hesablama yükü belə ifadə olunan sistemlərin həllidir:
\[ AD^2A^Tu=L\Lambda L^Tu=v. \tag{5} \]
\(D\) və \(\Lambda\) diaqonal, \(L\) aşağı üçbucaqlı matrisdir. Mənbə pis şərtlənmiş seyrək sistemlərin idarəsi üçün əvvəlki tətbiq strategiyasından istifadə edir.
Degenerasiya və asılı sətirlər
`makeAfull(...)` funksiyası Markowitz pivot meyarından istifadə edərək xətti asılı sətirləri çıxara və seyrəkliyi qorumağa çalışa bilər. Bununla belə bu əməliyyat standart axında məcburi deyil; degenerasiya ilə bağlı strategiyanın bir hissəsi kimi lazım olduqda istifadə oluna bilər. \(d=1\) degenerasiya prosedurunu aktivləşdirir, \(d=0\) isə standart seçimdir.
Qövs bucağı və mərkəzləşdirmə
arcLP optimallaşdırıcıya düz xətt üzrə deyil, qövs üzrə hərəkət edir. Addım bucağı analitik hesablana bilir. Mərkəzləşdirmə parametri \(\sigma_k\) xüsusi Golden Section axtarışı ilə seçilir. Mənbəyə görə klassik üsul intervalı təxminən 0,618 əmsalla daraldır, istifadə edilən xüsusi prosedur isə hər iterasiyada 0,5 əmsala endirir.
Sayısal sabitlik üçün:
\[ \alpha_k=\min\{0.9999\alpha_k,\;0.99\pi/2\}<0.99\pi/2. \]
Məhdudiyyətsiz və mümkün olmayan instansiyaların aşkarlanması
\[ \max_i|x_i|>10^{10} \]
şərti məhdudiyyətsizliyə,
\[ \max_i|\lambda_i|>10^{10} \]
isə mümkün olmama halına işarə edən heuristik meyar kimi istifadə olunur. Müsbət \(x\) və \(s\)-ni qoruyaraq duality gap-i azaldan addımın tapılmaması da mümkün olmama göstəricisi ola bilər. Bu detektorlar məqalədə “reasonable detection” verən hesablama heuristikaları kimi təqdim edilir; universal tam sertifikat nəzəriyyəsi kimi deyil.
Dayandırma meyarı
\[ \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. \]
Bundan əlavə, həm primal, həm dual addım ölçüləri \(10^{-8}\)-dən kiçik olduqda və müəyyən sayısal pisləşmə hallarında proqram dayana bilər.
Tədqiqat nəyi göstərir, nəyi göstərmir?
Tədqiqat arcLP-nin işlək Matlab LP solveri olduğunu, Netlib sınaqlarında optimum həllər tapdığını və Mehrotra tətbiqi ilə hesablama baxımından rəqabət apara bildiyini göstərir. Lakin arcLP-nin hər problem, hər kompüter və hər kommersiya solverində daha sürətli və ya daha dəqiq olduğunu göstərmir. O(√nL) sübutunun tam törəməsi də bu metameqalənin daxilində verilmir.
Azərbaycan baxımından mümkün əhəmiyyəti
Tədqiqat Azərbaycan məlumatları əsasında aparılmayıb. Bununla belə xətti proqramlaşdırma enerji planlaşdırılması, istehsal, logistika, nəqliyyat, resurs bölgüsü və mühəndislik optimallaşdırmasında əsas vasitələrdəndir. Açıq kodlu Matlab tətbiqi Azərbaycandakı universitetlərdə və tədqiqat qruplarında optimallaşdırma alqoritmlərinin öyrədilməsi və müqayisəsi üçün faydalı ola bilər. Yerli sənaye tətbiqi isə problem ölçüsü, hesablama infrastrukturu, məlumat keyfiyyəti və mövcud proqram sistemləri ilə ayrıca yoxlanmalıdır.
Tədqiqatın Metodu və Nəticələri
Əsas çağırış:[x,obj,kk,infe,lambda,s,exflag]=arcLP(A,b,c,d,tol,iter)
| exflag | Məna |
|---|---|
| 0 | Uğurlu sonlanma |
| 1 | Mənbə API təsvirinə görə mümkün olmayan instansiya |
| 2 | Mənbə API təsvirinə görə məhdudiyyətsiz instansiya |
| 3 | Primal və dual məsələlərin hər ikisinin mümkün olmadığı vəziyyət |
| 4 | A, b və ya c giriş məlumatının natamam olması |
Sadə nümunə
\[ \min x_1,\qquad x_1+x_2=5,\quad x_1,x_2\ge0. \]
\(A=[1\;1]\), \(b=5\), \(c=[1\;0]^T\). Mənbəyə görə arcLP beş iterasiyada \(x^*=[0\;5]^T\) həllini tapır.
Netlib nəticələrinin tam cədvəli
| Problem | Mehrotra iter. | arcLP iter. | Mehrotra obyektiv | arcLP obyektiv | Mehrotra qalıq | arcLP qalıq |
|---|---|---|---|---|---|---|
| Adlittle | 15 | 16 | 2.2549e+05 | 2.2549e+05 | 3.4e–08 | 3.0e–11 |
| Afiro | 9 | 9 | –464.7531 | –464.7531 | 8.0e–12 | 6.2e–13 |
| Agg | 22 | 20 | –3.5992e+07 | –3.5992e+07 | 5.2e–05 | 3.7e–06 |
| Agg2 | 20 | 21 | –2.0239e+07 | –2.0239e+07 | 5.2e–07 | 3.1e–08 |
| Agg3 | 18 | 20 | 1.0312e+07 | 1.0312e+07 | 8.8e–09 | 1.5e–08 |
| Bandm | 22 | 20 | –158.6280 | –158.6280 | 8.3e–10 | 3.6e–11 |
| Beaconfd | 11 | 11 | 3.3592e+04 | 3.3592e+04 | 1.4e–10 | 1.8e–12 |
| Blend | 14 | 14 | –30.8122 | –30.8122 | 4.9e–11 | 1.6e–12 |
| Bnl1 | 35 | 34 | 1.9776e+03 | 1.9776e+03 | 3.4e–09 | 2.9e–09 |
| Bnl2+ | 38 | 35 | 1.8112e+03 | 1.8112e+03 | 9.3e–07 | 3.5e–06 |
| Brandy | 19 | 24 | 1.5185e+03 | 1.5185e+03 | 6.2e–08 | 2.4e–06 |
| Degen2+ | 17 | 19 | –1.4352e+03 | –1.4352e+03 | 2.0e–10 | 5.9e–10 |
| Degen3* | 22 | 35 | –9.8729e+02 | –9.8729e+02 | 1.2e–09 | 8.6e–08 |
| fffff800 | 31 | 28 | 5.5568e+05 | 5.5568e+05 | 7.7e–04 | 3.7e–09 |
| Israel | 29 | 27 | –8.9665e+05 | –8.9664e+05 | 1.8e–08 | 3.4e–08 |
| Lotfi | 18 | 16 | –25.2647 | –25.2646 | 2.7e–07 | 7.8e–09 |
| Maros_r7 | 21 | 20 | 1.4972e+06 | 1.4972e+06 | 6.4e–09 | 1.7e–09 |
| Osa_07+ | 35 | 32 | 5.3578e+05 | 5.3578e+05 | 1.5e–07 | 8.4e–10 |
| Osa_14 | 37 | 42 | 1.1065e+06 | 1.1065e+06 | 3.0e–08 | 5.2e–09 |
| Osa_30 | 36 | 42 | 2.1421e+06 | 2.1421e+06 | 1.3e–08 | 1.3e–08 |
| Qap12 | 24 | 23 | 5.2289e+02 | 5.2289e+02 | 6.2e–09 | 2.9e–10 |
| Qap15+ | 44 | 28 | 1.0410e+03 | 1.0410e+03 | 1.5e–05 | 8.4e–08 |
| Qap8+ | 13 | 12 | 2.0350e+02 | 2.0350e+02 | 7.1e–09 | 6.2e–11 |
| Sc105 | 11 | 11 | –52.2021 | –52.2021 | 9.8e–11 | 2.2e–12 |
| Sc205 | 12 | 12 | –52.2021 | –52.2021 | 8.8e–11 | 4.4e–11 |
| Sc50a | 9 | 10 | –64.5751 | –64.5751 | 8.3e–08 | 8.5e–13 |
| Sc50b | 8 | 10 | –70.0000 | –70.0000 | 9.1e–07 | 3.6e–12 |
| Scagr25 | 18 | 19 | –1.4753e+07 | –1.4753e+07 | 4.6e–09 | 1.7e–08 |
| Scagr7 | 17 | 17 | –2.3314e+06 | –2.3314e+06 | 1.1e–07 | 7.0e–10 |
| Scfxm1+ | 22 | 21 | 1.8417e+04 | 1.8417e+04 | 1.6e–08 | 3.3e–05 |
| Scfxm2 | 26 | 24 | 3.6660e+04 | 3.6660e+04 | 2.6e–08 | 4.8e–05 |
| Scfxm3+ | 23 | 23 | 5.4901e+04 | 5.4901e+04 | 9.8e–08 | 1.2e–04 |
| Scrs8 | 30 | 28 | 9.0430e+02 | 9.0430e+02 | 1.8e–10 | 1.0e–10 |
| Scsd1 | 13 | 11 | 8.6666 | 8.6666 | 8.7e–14 | 3.3e–15 |
| Scsd6 | 16 | 16 | 50.5000 | 50.5000 | 8.6e–15 | 2.6e–13 |
| Scsd8 | 14 | 15 | 9.0500e+02 | 9.0500e+02 | 1.3e–10 | 2.6e–13 |
| Sctap1 | 27 | 20 | 1.4123e+03 | 1.4123e+03 | 0.0031 | 1.4e–11 |
| Sctap2 | 21 | 22 | 1.7248e+03 | 1.7248e+03 | 4.4e–07 | 1.4e–12 |
| Sctap3 | 22 | 21 | 1.4240e+03 | 1.4240e+03 | 5.9e–07 | 1.9e–12 |
| Share1b | 25 | 26 | –7.6589e+04 | –7.6589e+04 | 1.5e–06 | 1.9e–07 |
| Share2b | 15 | 15 | –4.1573e+02 | –4.1573e+02 | 7.9e–10 | 1.4e–10 |
| Ship04l | 18 | 19 | 1.7933e+06 | 1.7933e+06 | 2.9e–11 | 1.3e–10 |
| Ship04s | 20 | 19 | 1.7987e+06 | 1.7987e+06 | 4.5e–09 | 3.1e–10 |
| Ship08l | 22 | 20 | 1.9091e+06 | 1.9090e+06 | 1.0e–10 | 1.8e–11 |
| Ship08s | 20 | 19 | 1.9201e+06 | 1.9201e+06 | 4.5e–12 | 1.7e–09 |
| Ship12l | 21 | 21 | 1.4702e+06 | 1.4702e+06 | 1.0e–08 | 3.0e–10 |
| Ship12s | 19 | 21 | 1.4892e+06 | 1.4892e+06 | 2.1e–13 | 5.0e–11 |
| Stocfor1+ | 14 | 13 | –4.1132e+04 | –4.1132e+04 | 1.1e–10 | 8.6890e–11 |
| Stocfor2 | 22 | 22 | –3.9024e+04 | –3.9024e+04 | 1.6e–09 | 4.3e–09 |
| Stocfor3 | 38 | 37 | –3.9976e+04 | –3.9977e+04 | 6.4e–08 | 7.7e–08 |
| Truss | 26 | 24 | 4.5882e+05 | 4.5882e+05 | 9.5e–06 | 5.2e–07 |
51 problemin sayımında arcLP iterasiya üzrə 24 qələbə, 11 bərabərlik və 16 geridə qalma göstərir. Qalıq göstəricisində isə arcLP 34 problemdə daha aşağı, 1-də eyni, 16-da daha yüksək nəticə verir. Bu paylanma metodun ümumilikdə rəqabətqabiliyyətli olduğunu dəstəkləyir, lakin hər sətirdə üstün olduğunu göstərmir.
Verianla Live: arcLP hesablama axını
Göstərilən mərhələlər mənbədə təsvir edilən əsas proqram arxitekturasına əsaslanır.
| Mərhələ | İzah | Source |
|---|---|---|
| 1. Məlumatların qəbulu | A, b, c və seçim parametrləri qəbul edilir. | Main function |
| 2. İlkin emal | Presolve qaydaları və erkən status yoxlamaları tətbiq olunur. | Pre-process |
| 3. Başlanğıc nöqtə | Denklem (3) üzrə daha yaxşı namizəd seçilir. | Equation 3 |
| 4. Qövs-axtarış iterasiyası | Müsbət x və s qorunaraq qövs addımı və σk seçilir. | Arc-search |
| 5. Seyrək sistem | Cholesky tipli sistem həll edilir. | Equation 5 |
| 6. Dayandırma | Qalıqlar, μ, addım ölçüləri və status meyarları yoxlanır. | Termination criteria |
| 7. Son emal | Nəticə yoxlanır və çıxış dəyişənləri qaytarılır. | Main function |
Mənbə və Metod Qeydi
Orijinal başlıq: ArcLP: A Matlab Implementation of an O(√nL) Arc-search Infeasible Interior-Point Algorithm for Linear Programming.
Müəllif: Yaguang Yang.
Afiliyasiya: Independent Researcher, US.
DOI: 10.5334/jors.674.
Nəşr: Journal of Open Research Software, 14(1):57, Ubiquity Press, 12 avqust 2026.
Rəy statusu: Hakim rəyindən keçmiş Software Metapaper.
Məqalə lisenziyası: CC BY 4.0. Proqram lisenziyası: BSD 3-Clause.
Proqram versiyası: 1.0. Mənbədə proqramın tarix sahəsi “08/02/2026” kimi verildiyindən format şərh edilmədən saxlanılır.
Maliyyələşdirmə: JORS nəşr haqqından imtina edib; ayrıca tədqiqat qrantı göstərilmir.
Maraqların toqquşması: Müəllif belə toqquşma olmadığını bəyan edir.
Elmi məhdudiyyət: O(√nL) sübutunun tam riyazi quruluşu bu yeddi səhifəlik metameqalədə təkrar verilmir. Benchmark nəticələri hesablama rəqabətliliyini dəstəkləyir, universal üstünlüyü deyil.
Şərh yazın
E-poçt ünvanınız yayımlanmayacaq. Məcburi sahələr * ilə işarələnib