Dynamic solvers for linear and quadratic optimization

Abstract

In this study, a dynamic solver for linearly constrained linear and quadratic optimization problems, called gradient projection network, is introduced. The system is gradient based. Gradient dynamical systems are described by a set of differential equations in a state equation form whose vector field is produced by the gradient of a scalar function, called energy. These systems do not have complex dynamics like oscillation so that any bounded solution of them converges to one of the equilibrium points which are indeed extreme of the associated energy function. As a consequence of their dynamical properties, gradient systems have been widely used as natural models for solving unconstrained minimization problems by considering the cost function as the energy. Constrained minimization problems can also be solved in the same way, by adding to the cost some penalty function terms representing constraint violations. In the proposed dynamics, feasibility of solutions is satisfied by utilizing the concept of projection to feasible region. Because of projection operation the proposed dynamics is discontinuous, so it is not gradient but has the properties similar to that of gradient systems. To show this, La Salle's Invariance 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.

Özet

Bu çalışmada, eniyileme (optimization) kuramındaki geleneksel gradyan izdüşürme (projeksiyon) yöntemi temel alınarak doğrusal kısıtlı (linearly constrained), doğrusal (linear) ve dördün (quadratic) eniyileme problemleri için gradyan izdüşürmeli ağ (gradient projecting network) olarak adlandırılan yeni bir çözümleyici tanıtılmaktadır. Bu dinamik system, gradyan izdüşürme yönteminin (gradient projection method) sürekli hal gerçeklemesidir. Gradyan izdüşürme işleminden dolayı önerilen çözümleyicinin sağ tarafı, gradyan ya da gradyan-gibi (quasi-gradient) sistemlerden farklı olarak, süreksiz yapıdadır. Buna rağmen önerilen ağ, gradyan ve gradyan-gibi sistemlerin yakınsama özelliklerine sahiptir. Tanıtılan sistemin yakınsayan olduğu, yani, her bir çözümün denge noktasında sonlandığı La Salle'nin değişmez küme teoreminin, sağ tarafı süreksiz sistemler için genişletilmesi ile gösterilmiştir.