Dynamic solvers for linear and quadratic optimization
Doğrusal ve karesel eniyileme problemleri için dinamik çözümleyiciler
- Tez No: 474195
- Danışmanlar: PROF. DR. CÜNEYT GÜZELİŞ
- Tez Türü: Doktora
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2003
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 108
Özet
Bu tezde, eniyileme kuramındaki geleneksel gradyen izdüşüm yöntemine dayanarak doğrusal kısıtlı, doğrusal ve karesel eniyileme problemleri için, gradyen izdüşüm ağ olarak adlandırılan bir dinamik çözümleyici tanıtılmaktadır. Önerilen gradyen izdüşüm ağı gradyen temelli sistemdir. Gradyen dinamik sistemler durum denklemleri yapısında tanımlı, sağ tarafı enerji olarak anılan bir fonksiyonun gradyeni olan diferansiyel denklem takımıdır. Bu sistemlerin titreşim gibi karmaşık dinamikleri yoktur bu nedenle her sınırlı çözümü, aynı zamanda ilişkili enerji fonksiyonunun büküm noktası da olan bir denge noktasında sonlanır. Öte yandan, gradyen-benzeri sistemler de, gerçekte gradyen sistem olmamakla birlikte aynı dinamik yapıya sahiptirler. Önerilen gradyen izdüşüm dinamiği süreksizdir, gradyen ya da gradyen benzeri değildir fakat gradyen sistemlere benzer özelliklere sahiptir. Bunu göstermek için La Salle'nin değinmez küme kuramı, sağ tarafı süreksiz sistemler için genişletilmekte ve bu genişletilmeye dayanarak önerilen dinamik çözümleyicinin yakınsak olduğu gösterilmektedir, başka bir değişle, her bir çozümü bir denge noktasında sonlanmaktadır. Dinamik özelliklerin sonucu olarak, değer fonksiyonunun enerji gibi ele alınması ile gradyen ve gradyen-benzeri sistemler kısıtsız eniyileme problemlerinin çözümünde geniş olarak kullanılmaktadır. Kısıtlı eniyileme problemleri de benzer yolla çözülebilmektedir. Yaklaşımlardan biri, eniyileme ölçütüne kısıt ihlali durumunda pozitif değer alan bir hata terimi eklemektir. Hopfield-Tank modeli, Kennedy-Chua modeli, Rodriguez-Vazquez modeli ve Zak'ın modelinde bu yaklaşım kullanılmaktadır. Fakat böyle bir yaklaşımda hata terimine ilişkin parametrelerin belirlenmesi zordur ve bazen geçersiz çözümlerin elde edilmesine yol açmaktadır. Kısıtlı problemi kısıtsız probleme dönüştürmede izlenen bir diğer yol, değer fonksiyonuna bir engel bileşeni eklemektir. Bu bileşen, geçerli bölge sınırlarına yaklaşıldıkça sonsuz büyük değer alacak biçimde oluşturulur, böylelikle çözüm geçerli bölgede tutulur. Bu türdeki yaklaşım, çözümleri geçerli bölgenin sınırlarda olan problemler için uygun değildir. Önerilen dinamikte, çözümlerin geçerliliği, geçerli bölgeye izdüşürme fikrinin kullanılması ile sağlanır. Burada, sistemin dinamiği gradyen temellidir, başka bir deyişle, diferansiyel denklemin sağ tarafı enerji olarak adlandırılan skaler fonksiyonun gradyeninden oluşturulur ve eğer çözüm eğrisi kısıtlardan herhangi birini ihlal ederse, ihlal edilen kısıtın belirlediği yüzeye izdüşüm yapılır, böylelikle çözüm bu kist yüzeyinde kalmaya zorlanır. Gradyen izdüşüm ağ'nun denge noktaları ile ilgili kısıtlı eniyileme probleminin büküm noktalar arasındaki ilişki elde edilerek eniyileme probleminin kesin yerel enaz noktalarının gradyen izdüşüm ağı'nın asimptotik kararlı denge noktalarına karşı geldiği gösterilmiştir. Önerilen ağın etkinliği doğrusal ve karesel eniyileme problemleri için Kennedy- Chua, Rodriguez-Vazquez ve Zak'ın ağı ile karşılaştırmalı olarak sınanmıştır. Gradyen izdüşüm ağı ile elde edilen çözümlerin geçerli olduğu ve bu çözümleyicinin Kennedy Chua ağındaki gibi herhangi bir parametre seçimi gerektirmediği gösterilmiştir. Ayrıca Rodriguez Vazquez agindaki gibi yakınsama için adim büyüklüğü ayarlaması gerektirmemektedir. Ek değişken gerektirmemesi nedeniyle de Zak'un ağına göre daha iyidir. Büyük boyutlu problemlerde önerilen ağın etkinliğinin sınanmasi için sonuçlar Hopfield ağı ve hücresel sinir ağa ile elde edilenlerle karşılaştırılmıştır. Sınamalarda doğrusal kısıtlı karesel eniyileme problemi biçiminde tanımlı, kombinatoryal problemlerden engelli ençoklama klik problemi kullanılmıştır. Önerilen ağ ile elde edilen sonuçlar Hopfield ağı sonuçlarından iyi, hücresel sinir ağı sonuçları ile yaklaşık ayni mertebededir.
Özet (Çeviri)
In this thesis, based on classical gradient projection method of optimization theory, a dynamic solver for linearly constrained linear and quadratic optimization problems, called gradient projection network is introduced. The proposed gradient projection network is gradient based system. A gradient dynamical systems are described by a set of differential equations in a state equation form whose right-hand side is the gradient of a function, called energy. These systems do not have complex dynamics like oscillation so that any bounded solution of them converges to one of the equilibria which are indeed extrema of the associated energy function. On the other hand, gradient-like systems which are, in fact, not gradient systems have the same kind of dynamics. The proposed gradient projection dynamics is discontinuous, it is not gradient nor gradient like but have the properties similar to that of gradient systems. To show this, La Salle's invariance set theorem has been extended to a system with discontinuous right-hand side, and based on this extension it is shown that the introduced dynamical solver is convergent, i.e., any trajectory of it ends at one of the equilibria. As a consequence of their dynamical properties, gradient and gradient-like systems have been widely used for solving unconstrained minimization problems by considering the cost function as the energy. Constrained minimization problems can also be solved in the similar way. One of the approaches is an addition to a cost function a penalty term taking positive value in the case of constraint violation. Hopfield-Tank model, Kennedy-Chua model, Rodriguez-Vazquez model and Zak's model utilize this concept. But in this kind of approximation, determining penalty parameters is difficult and sometimes this lead to obtaining unfeasible solutions. Another way of transforming constrained problems to unconstrained ones is by adding a barrier term to cost function. This term is constructed such that to have infinitely large value at borders of feasible region, thus keeping the solutions in the feasible region. This kind of approximation is not appropriate for problems whose solutions are on the borders of feasible region. In the proposed dynamics, feasibility of solutions is satisfied by utilizing the concept of projection to feasible region. Here, the dynamics of the system is gradient based, i.e., the right-hand side of differential equation is produced by the gradient of a scalar function called energy and if the trajectory violates any of the constraints, projection is made on to a surface defined by the violated constraint and thus trajectory is forced to stay on this constraint surface. By deriving the relations between the equilibria of gradient projection network and extrema of related constrained optimization problem, it was shown that a strict local minimum of optimization problem corresponds to an asymptotically stable equilibrium point of gradient projection network. The efficiency of the proposed dynamic is tested comparatively with Kennedy-Chua, Rodriguez-Vazquez and Zak's networks for linear and quadratic problems. It was shown that solutions obtained by gradient projection network are feasible and this solver does not require any parameter choice as in Kennedy-Chua network. Also it does not require stepsize adjusment for convergence as in Rodriguez-Vazquez network. Also, because no extra variables are required it is preferable to Zak's network. For testing the efficiency of proposed network on a problems with high dimension, results are compared with those obtained by Hopfield network and cellular neural network. The problem used in tests is a maximum clique problem with a barrier, a combinatorial problem defined as linearly constrained quadratic optimization problem. It is shown that solution obtained by the proposed network are beter than Hopfield network results and are in incomparable degree with that obtained by cellular neural network.
Benzer Tezler
- Doğrusal olmayan sistemler için model öngörülü kontrol yöntemine ters optimal kontrol yapısının katılması
Injection of inverse optimal control structure to model predictive control method for non-linear systems
LÜTFİ ULUSOY
Doktora
Türkçe
2021
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
PROF. DR. MÜJDE GÜZELKAYA
- Whole-body bound gait control of a quadruped robot equipped with anactive spine joint
Aktif omurga eklemi ile donatılmış dört ayaklı robotta sıçrama yürüyüşünün tüm vücut hareketi kontrolü
ÖMER KEMAL ADAK
Doktora
İngilizce
2021
Mekatronik MühendisliğiSabancı ÜniversitesiMekatronik Ana Bilim Dalı
DOÇ. DR. KEMALETTİN ERBATUR
- PLC ile NMPC uygulaması
NMPC application using PLC
MURAT ERHAN ÇİMEN
Yüksek Lisans
Türkçe
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
DOÇ. DR. YAPRAK YALÇIN
- Bozulabilir mallar için optimal üretim planlaması
Optimal production planning for decaying items
MELDA GÜRSOY
- Model predictive control of quadrotor UAV linear model
Lineer model quadrotor İHA'nın model öngörülü kontrolü
ARDEN KUYUMCU
Yüksek Lisans
İngilizce
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. İSMAİL BAYEZİT