Date of final exam: 26/02/2001

E-mail: chesi@dii.unisi.it

Tutors: Prof.  A. Tesi, Università di Firenze and A. Vicino, Università di Siena

  ___________________________________________________________________________________________________________

New convexification techniques and their application to the analysis of dynamical systems and vision problems   ___________________________________________________________________________________________________________

Advisor:

Prof.  A. Vicino, Università di Siena

Summary of the thesis

It is a well known fact that a large number of system analysis and control problems amount to computing the minimum and/or the maximum distance from a point to a surface in a finite dimensional space. These optimization problems are called distance problems.

Some examples of such problems are the estimation of the domain of attraction of equilibria of nonlinear systems, the computation of the parametric stability margin for uncertain systems, the computation of the envelope of the frequency response of ellipsoidal plants, the computation of the region of validity of optimal linear controllers for nonlinear systems, and the $D$-stability of real matrices that plays a key role in the analysis of singularly perturbed systems. Distance problems can be found also in the computer vision area. The estimation of the fundamental matrix of a stereo vision system is an example.

Unfortunately, it is also known that the large majority of distance problems are non-convex optimization programs. This implies the possible presence of local optimal solutions in addition to the global ones that, therefore, are in general extremely difficult to obtain with reasonable computational effort.

Recently, powerful convex optimization techniques have been devised for problems in the form of Linear Matrix Inequalities (LMIs). Such techniques have been successfully employed in connection with suitable changes of variables for convexifying some classes of optimization problems. The main purpose of this thesis is to show how LMI techniques can be exploited to solve some classes of distance problems. More specifically, the problem of determining the minimum or the maximum euclidean distance of a point from a polynomial surface in the n-dimensional space is considered. It is first shown that the solution can be achieved via the solution of a one-parameter family of positivity tests on homogeneous forms. In order to perform such tests, an LMI approach is proposed once a suitable change of variables has been performed. This approach leads to the computation of a lower bound to the global minimum and an upper bound to the global maximum. Successively, the problem of establishing the tightness of the introduced lower and upper bounds is considered. In particular, it is shown that the optimality of the computed bounds can be checked by means of a simple test for non-degenerate cases.

Moreover, necessary and sufficient conditions are given for establishing a priori the tightness of the bounds, based on the structure of the distance problem.
 

  _______________________________________