Parallel algorithms for nonlinear optimization

Abstract

Paralel hesaplama mimarilerinin kolayca erişilebilir bir teknoloji haline gelmesi sonucu, paralel algoritma tasarımı konusu optimizasyon alanında güncelliğini korumaktadır. Bu tez, paralel doğrusal olmayan programlama algoritmaları tasarlamaya yönelik bir yaklaşımı konu almaktadır. Yaklaşımın ana fikri, mevcut yöntemleri doğrudan paralelleştirmek yerine, paralel hesaplamadan faydalanarak yeni algoritmalar tasarlamaktır. Dolayısıyla, önce yaklaşımımıza uygun bir tasarım çerçevesi veriyor ve sonra dabu çerçevede kalan farklı algoritmalar sunuyoruz.Tasarladığımız örnek algoritmalar ya mevcut yöntemlere ait prosedürleri çokbaşlamalı bir yapı içerisinde kullanmaktadırlar, ya da tamamen bu tezde geliştirilmiş yeni paralel yöntemlerdir. Bu şekilde, algoritmaların (değişik seviyelerde) yapısal paralelliğinin, elde edilen algoritmalar iyi bir çözüm performansına sahip olacak şekilde nasıl başarılabileceğini göstermeye çalışıyoruz. Çalışmamızı önerilen algoritmaların yakınsamaispatları ile tamamlıyoruz.

Parallel algorithm design is a very active research topic in optimization as parallel computer architectures have recently become easily accessible. This thesis is about an approach for designing parallel nonlinear programming algorithms. The main idea is to benefit from parallelization in designing new algorithms rather than considering direct parallelizations of the existing methods. We give a general framework following ourapproach, and then, give distinct algorithms that fit into this framework.The example algorithms we have designed either use procedures of existing methods within a multistart scheme, or they are completely new inherently parallel algorithms. In doing so, we try to show how it is possible to achieve parallelism in algorithm structure (at different levels) so that the resulting algorithms have a good solution performance in terms of robustness, quality of steps, and scalability. We complement our discussion with convergence proofs of the proposed algorithms.