Theoretical and experimental analysis of a saddle point algorithm for linear programming
Doğrusal programlama için bir eyer noktası algoritmasının kuramsal ve deneysel analizi
- Tez No: 50483
- Danışmanlar: DOÇ.DR. İ. KUBAN ALTINEL
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Algoritmalar, Doğrusal programlama, Lagrange fonksiyonları, Algorithms, Linear programming, Lagrange function
- Yıl: 1996
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
Bu tezde, doğrusal bir amaç fonksiyonunun doğrusal eşitlik ve eşitsizliklerden oluşan kısıtlar kümesi üzerinde eniyilenmesi olarak tanımlanan doğrusal programlama problemleri için, Shang Yi tarafından geliştirilen ve Eyer Noktası Algoritması olarak isimlendirilen bir algoritmanın kuramsal temelleri ile test problemleri üzerindeki deneysel başarımı incelenmiştir. Algoritma, bir doğrusal programlama problemine ait Lagrange fonksiyonundan bir dönüşümle elde edilen fonksiyonun belirlediği yüzeyin eyer noktasını Eniyi Kontrol Kuramı 'ndan bilinen formüller yardımıyla bulur. Bu eyer noktası, doğrusal programlama probleminin eniyi birincil (primal) ve eniyi çifteş (dual) çözümünü içermektedir. Karlin ve Uzawa'nin teoremlerine göre, çözümü olan bir dışbükey programlama probleminin eniyi çözümü ve bu çözüme ait Lagrange çarpanları, programın Lagrange fonksiyonunun eyer noktasını oluştururlar. Bu ifadenin tersi de ek bazı varsayımlar altında doğrudur; çözümlü bir dışbükey programlama probleminin Lagrange fonksiyonunun eyer noktası, o programın eniyi çözümünü ve bu çözüme ait Lagrange çarpanlarını* verir. Shang Yı'nin algoritması her türlü doğrusal programın aynı zamanda bir dışbükey program olduğu gerçeğinden yola çıkmakta ve Lagrange fonksiyonundan bir dönüşümle elde edilen fonksiyonun eyer noktasını bularak doğrusal programa ait birincil ve çifteş problemleri eşzamanda çözmektedir. Eyer Noktası Algoritması'nın yakınsama hızı da bu tezde ele alınmıştır. Algoritma üzerinde yapılan deneyler, yakınsama hızının pratikte çok düşük olduğunu ortaya koymuştur. Bu bulgu, Shang Yı'nin bazı varsayımlara dayananarak algoritmanın kuramsal hızı için önerdiği çokterimli irade üe çelişmektedir. V 14-
Özet (Çeviri)
ABSTRACT In this thesis, theoretical background of a“Saddle Point Algorithm”and its experimental performance have been analyzed. This algorithm which is developed by Shang Yi solves linear programming problems. Using a set of formulae from Optimal Control Theory, the algorithm finds the saddle point of a saddle surface obtained by transforming the Lagrange function of a given linear programming problem. This saddle point covers both the optimal primal and dual solutions. According to Karlin and Uzawa's Theorems, an optimal solution of a feasible convex programming problem and its corresponding Lagrange multipliers constitute the saddle point of the program's Lagrange function. The reverse of this statement is also true under some additional assumptions. At this point, departing from the fact that any linear program is also a convex program, Shang Yi developed an approach that solves simultaneously primal and dual problems of a linear program by finding the saddle point of its Lagrange function. The speed of convergence of the Saddle Point Algorithm has also been discussed. Experimentation with the algorithm has shown that the algorithm is much slower than Shang Yi's claim. This observation contradicts the polynomial expression derived for the algorithm's theoretical speed of convergence.
Benzer Tezler
- Çift diyodlu simetrik olmayan bir gunn osilatörünün çalışma karakteristiklerinin teorik ve deneysel incelenmesi
Theoretical and experimental analysis of an asymmetrically loaded two-diode gunn oscillator
CEVDET IŞIK
Doktora
Türkçe
1985
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF. DR. BİNGÜL YAZGAN
- Zorlanmış köşe akışlarının stokes rejiminde teorik ve deneysel incelenmesi
Theoretical and experimantal analysis of forced corner flows for the stokes regime
EMİN FUAD KENT
- Çivi kanatlı düzlem levhalarından ısı transferinin teorik ve deneysel incelenmesi
Başlık çevirisi yok
SUNA KARGICI
Doktora
Türkçe
1993
Makine MühendisliğiSelçuk ÜniversitesiMakine Ana Bilim Dalı
PROF. DR. AKBAY TUĞAN GÖKÇE
- Buckling and poot buckling analysis of composite I sections
Kompozit I kesitlerin burkulma ve burkulma sonrası analizi
MELİH PAPİLA
