On Two Problems for Matrix Polytopes


We consider two problems from stability theory of matrix polytopes: the existence of common quadratic Lyapunov functions and the existence of a stable member. We show the applicability of the gradient algorithm and give a new sufficient condition for the second problem. A number of examples are considered.

Share and Cite:

Yılmaz, Ş. and Büyükköroğlu, T. (2014) On Two Problems for Matrix Polytopes. Applied Mathematics, 5, 2650-2656. doi: 10.4236/am.2014.517253.

1. Introduction

Consider the switched system


where,. In Equation (1), the matrix switches among matrices.

Switching signal is piecewise continuous from the right function and the switching times are arbitrary. For the switched system (1) with initial condition and with switching signal denotes the solution by.

Definition 1. The origin is uniformly asymptotically stable (UAS) for the system (1) if for every there exists such that for every signal and initial state with, the inequality is satisfied for all and uniformly on

If all systems in (1) share a common quadratic Lyapunov function (CQLF) then the switched

system is UAS (T denotes the transpose).

In this case there exists a common such that


and is called a common solution to the set of Lyapunov matrix inequalities (2).

The problem of existence of common positive definite solution of (2) has been studied in a lot of works (see [1] -[9] and references therein). Numerical solution for common via nondifferentiable convex optimization has been discussed in [10] .

In the first part of the paper, the problem of existence of CQLF is investigated by Kelley’s method. This method is applied when CQLF problem is treated as a convex optimization problem.

Second part of the paper is devoted to the following question:

Let be a compact, for the matrix is a real matrix. Is there a Hurwitz stable member (all eigenvalues lie in the open left half plane) in the family

or equivalently is there such that is stable? This problem is one of the hard and important problems in control theory (see [11] ). Numerical solution of this problem is considered in [12] . In this paper we reduce this problem to a non-convex optimization problem.

2. Common Quadratic Lyapunov Function

For the switched system

consider the problem of determination of CQLF where. We are going to investigate it by Kelley’s cutting-plane method. This method gives new sufficient condition (Theorem 2) and new algorithm (Algorithm 1) which is more effective in comparison with the algorithm from [10] .

Consider the problem of existence of a common such that

. (3)

Let be and be an symmetric matrix defined as



If there exists such that and then the matrix is required solution. This problem can be reduced to the minimization of a convex function under convex constraints.

Consider the following convex minimization problem


Let be a convex set and be convex function. The vector is said to be a subgradient of at if for all


The set of all subgradients of at is denoted by. If is an interior point of then the set is nonempty and convex. The following proposition follows from nondifferentiable optimization theory.

Proposition 1. Let be defined as


where is compact, is continuous and differentiable in. Then

where is the set of all maximizing elements in (6), i.e.


If for a given the maximizing element is unique, i.e. then is differentiable at and its gradient is

In the case of the Function (4)

If for the given the maximizing is unique and is a simple eigenvalues, the differentiability of at the point is guaranteed [13] .

We investigate problem (5) by Kelley’s cutting-plane method.

This method converts the problem (5) to the problem


where, , ,.

Let be a starting point and be distinct points.

At the th iteration, the cutting-plane algorithm solves the following LP problem


where denotes a subgradient of at.

Let be the minimizer of the problem (8).

If satisfies the inequality, where is a tolerance then is an approx-

imate solution of the problem (7).

Otherwise define as the index for the most negative, update the constraints in (8) by including the linear constraint

and repeat the procedure.

Recall that our aim is to find such that and, but not the solution of the minimization problem (5), (7).

Theorem 2. If there exists such that

where is the minimizer of the problem (8), then the matrix is a common solution to (3).


and by (5), is a common solution to (3).

For the problem (5), (7) Kelley’s method gives the following

Algorithm 1.

Step 1. Take an initial point. Compute and. If and stop; otherwise continue.

Step 2. Determine by solving LP problem in (8). If and then stop; otherwise continue. Set, update the constraints in (8) and repeat the procedure.

Example 1. Consider the switched system


are Hurwitz stable matrices.

Choose the initial point, then

, and

We obtain by solving LP problem in (8). Calculations give the following Table 1, and

Since and,

Table 1. Kelley’s algorithm for Example 1.

is a common positive definite solution for

3. Stable Member in a Polytope

This part is devoted to the following question: Given a matrix family where is a compact, is there a stable matrix in this family?

In [12] , a numerical algorithm has been proposed for a stable member in the affine matrix family. In this algorithm the uncertainty vector varies in the whole space. On the other hand we consider the case where varies in a box and use the gradient algorithm for minimization of the nonconvex maximum eigenvalue function. By choosing appropriate step-size, we obtain the convergence.

Let be a basis for the subspace of symmetric matrices and


Consider the problem

Theorem 3. There is a stable matrix in the family if and only if


By Lyapunov theorem, the matrix is stable.

Example 2. Consider the family of matrices


For, is unstable. We apply the gradient algorithm to find a stable member in the family.

Let and. So


Maximum eigenvalue of this matrix and its corresponding unit eigenvector are

respectively. Gradient of the function at is

The first tencomponent of the vector should be on the ten dimensional unit sphere. Therefore and

After 4 steps, we get

and. Therefore is stable.

4. Conclusion

Two important problems from control theory are considered: the existence of common quadratic Lyapunov functions for switched linear systems and the existence of a stable member in a matrix polytope. We obtain new conditions which give new effective computational algorithms.


*Corresponding author.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] Boyd, S. and Yang, Q. (1989) Structured and Simultaneous Lyapunov Functions for System Stability Problems. International Journal of Control, 49, 2215-2240.
[2] Büyükköroglu, T., Esen, Ö. and Dzhafarov, V. (2011) Common Lyapunov Functions for Some Special Classes of Stable Systems. IEEE Transactions on Automatic Control, 56, 1963-1967.
[3] Cheng, D., Guo, L. and Huang, J. (2003) On Quadratic Lyapunov Functions. IEEE Transactions on Automatic Control, 48, 885-890.
[4] Dayawansa, W.P. and Martin, C.F. (1999) A Converse Lyapunov Theorem for a Class of Dynamical Systems Which Undergo Switching. IEEE Transactions on Automatic Control, 44, 751-760.
[5] King, C. and Shorten, R. (2004) A Singularity Test for the Existence of Common Quadratic Lyapunov Functions for Pairs of Stable LTI Systems. Proceedings of the American Control Conference, Boston, 30 June-2 July 2004, 3881-3884.
[6] Mason, O. and Shorten, R. (2006) On the Simultaneous Diagonal Stability of a Pair of Positive Linear Systems. Linear Algebra and Its Applications, 413, 13-23.
[7] Narendra, K.S. and Balakrishnan, J. (1994) A Common Lyapunov Function for Stable LTI Systems with Commuting A-Matrices. IEEE Transactions on Automatic Control, 39, 2469-2471.
[8] Shorten, R.N. and Narendra, K.S. (2002) Necessary and Sufficient Conditions for the Existence of a Common Quadratic Lyapunov Function for a Finite Number of Stable Second Order Linear Time-Invariant Systems. International Journal of Adaptive Control and Signal Processing, 16, 709-728.
[9] Shorten, R.N., Mason, O., Cairbre, F.O. and Curran, P. (2004) A Unifying Framework for the SISO Circle Criterion and Other Quadratic Stability Criteria. International Journal of Control, 77, 1-8.
[10] Liberzon, D. and Tempo, R. (2004) Common Lyapunov Functions and Gradient Algorithms. IEEE Transactions on Automatic Control, 49, 990-994.
[11] Polyak, B.T. and Shcherbakov, P.S. (2005) Hard Problems in Linear Control Theory: Possible Approaches to Solution. Automation and Remote Control, 66, 681-718.
[12] Polyak, B.T. and Shcherbakov, P.S. (1999) Numerical Search of Stable or Unstable Element in Matrix or Polynomial Families: A Unified Approach to Robustness Analysis and Stabilization. Robustness in Identification and Control Lecture Notes in Control and Information Sciences, 245, 344-358.
[13] Horn, R.A. and Johnson, C.R. (1985) Matrix Analysis. Cambridge University Press, Cambridge.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.