Global optimization for the biaffine matrix inequality problem.

*(English)*Zbl 0844.90083Summary: It has recently been shown that an extremely wide array of robust controller design problems may be reduced to the problem of finding a feasible point under a Biaffine Matrix Inequality (BMI) constraint. The BMI feasibility problem is the bilinear version of the Linear (Affine) Matrix Inequality (LMI) feasibility problem, and may also be viewed as a bilinear extension to the Semidefinite Programming (SDP) problem. The BMI problem may be approached as a biconvex global optimization problem of minimizing the maximum eigenvalue of a biaffine combination of symmetric matrices. This paper presents a branch and bound global optimization algorithm for the BMI. A simple numerical example is included. The robust control problem, i.e., the synthesis of a controller for a dynamical physical system which guarantees stability and performance in the face of significant modelling error and worst-case disturbance inputs, is frequently encountered in a variety of complex engineering applications including the design of aircraft, satellites, chemical plants, and other precision positioning and tracking systems.

##### Keywords:

bilinear matrix inequalities; linear matrix inequalities; robust control; robust controller design; biconvex global optimization; branch and bound global optimization##### Software:

LMI toolbox
PDF
BibTeX
XML
Cite

\textit{K.-C. Goh} et al., J. Glob. Optim. 7, No. 4, 365--380 (1995; Zbl 0844.90083)

Full Text:
DOI

##### References:

[1] | F.A. Al-Khayyal. Jointly constrained bilinear programs and related problems: An overview.Computers and Mathematics with Applications, 19(11):53-62, 1990. · Zbl 0706.90074 · doi:10.1016/0898-1221(90)90148-D |

[2] | F.A. Al-Khayyal and J.E. Falk. Jointly constrained biconvex programming.Mathematics of Operations Research, 8(2):273-286, May 1983. · Zbl 0521.90087 · doi:10.1287/moor.8.2.273 |

[3] | F. Alizadeh.Combinatorial Optimization with Interior Point Methods and Semidefinite Matrices. PhD thesis, University of Minnesota, October 1991. |

[4] | V. Balakrishnan and S. Boyd. Global optimization in control system analysis and synthesis. In C.T. Leondes, editor,Control and Dynamic Systems, volume 53. Academic Press, 1992. · Zbl 0795.93040 |

[5] | V. Balakrishnan, S. Boyd, and S. Balemi. Computing the minimum stability degree of parameter-dependent linear systems. In S.P. Bhattacharyya and L.H. Keel, editors,Control of Uncertain Dynamic Systems, pages 359-378. CRC Press, Inc., Boca Raton, FL., 1991. · Zbl 0844.93062 |

[6] | B.R. Barmish, C.A. Floudas, C.V. Hollot, and R. Tempo. A global linear programming solution to some open robustness problems including matrix polytope stability.University of Wisconsin-Madison Tech. Report, ECE-94-13, 1994. |

[7] | S.P. Boyd and L. El Ghaoui. Method of centers for minimizing generalized eigenvalues.Linear Algebra and its Applications, 188-189:63-111, 1993. · Zbl 0781.65051 · doi:10.1016/0024-3795(93)90465-Z |

[8] | S.P. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan.Linear Matrix Inequalities in Systems and Control Theory. S.I.A.M. Publications, Philadelphia, PA, 1994. · Zbl 0816.93004 |

[9] | J. David.Algorithms for Analysis and Design of Robust Controllers. PhD thesis, Katholieke Universiteit Leuven, Belgium, 1994. |

[10] | R.E. De Gaston and M.G. Safonov. Exact calculation of the multivariable stability margin.IEEE Trans, on Automatic Control, AC-33:156-171, 1988. · Zbl 0674.93036 |

[11] | P. Dorato, editor.Robust Control. IEEE Press, New York, 1987. · Zbl 0625.93026 |

[12] | J.C. Doyle. Synthesis of robust controllersand filters with structured plant uncertainty. InProc. IEEE Conf. on Decision and Control, San Antonio, TX, December 1983. IEEE Press. |

[13] | L. El Ghaoui and P. Gahinet. Rank minimization under lmi constraints: A framework for output feedback problems. InProceedings of 1993 European Control Conference, Groningen, pages 1176-1179, 1993. |

[14] | M.K.H. Fan, A.L. Tits, and J.C. Doyle. Robustness in the presence of mixed parametric uncertainty and unmodelled dynamics.IEEE Trans, on Automatic Control, AC-36(1):25-38, January 1991. · Zbl 0722.93055 · doi:10.1109/9.62265 |

[15] | A.V. Fiacco and G.P. McCormick.Nonlinear Programming: Sequential Unconstrained Minimization Techniques. John Wiley and Sons, Inc., New York, NY, 1968. · Zbl 0193.18805 |

[16] | C.A. Floudas and V. Visweswaran. A global optimization algorithm for certain classes of nonconvex NLPs, ? I. Theory.Computers and Chemical Engineering, 14(12): 1397-1417, 1990. · doi:10.1016/0098-1354(90)80020-C |

[17] | P. Gahinet, A. Nemirovskii, A.J. Laub, and M. Chilali.The LMI Control Toolbox, Beta Release. Mathworks Inc., Natick, MA, November 1994. |

[18] | M.R. Garey and D.S. Johnson.Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., New York, 1979. · Zbl 0411.68039 |

[19] | A.M. Geoffrion. Generalized Benders decomposition.Journal of Optimization Theory and Applications, 10(4):237-260, 1972. · Zbl 0229.90024 · doi:10.1007/BF00934810 |

[20] | K.C. Goh.Robust Control Synthesis via Bilinear Matrix Inequalities. PhD thesis, University of Southern California, Los Angeles, CA., May 1995. |

[21] | K.C. Goh, M.G. Safonov, and J.H. Ly. Robust synthesis via bilinear matrix inequalities.International Journal of Robust and Nonlinear Control, January 1995. Submitted to the Special Issue on Linear Matrix Inequalities in Control Theory and Applications. · Zbl 0861.93015 |

[22] | K.C. Goh, M.G. Safonov, and G.P. Papavassilopoulos. A global optimization approach for the BMI problem. InProc. IEEE Conf. on Decision and Control, pages 2009-2014, Lake Buena Vista, FL., 1994. |

[23] | K.C. Goh, L. Turan, M.G. Safonov, G.P. Papavassilopoulos, and J.H. Ly. Biaffine Matrix Inequality properties and computational methods. InProc. American Control Conf., pages 850-855, Baltimore, MD., 1994. IEEE Press. |

[24] | R.A. Horn and C.R. Johnson.Matrix Analysis. Cambridge University Press, 1985. · Zbl 0576.15001 |

[25] | R. Horst and H. Tuy.Global Optimization: Deterministic Approaches. Springer-Verlag, Berlin, second, revised edition, 1993. · Zbl 0704.90057 |

[26] | P. Huard. Resolution of mathematical programming with nonlinear constraints by the method of centers. In J. Abadie, editor,Nonlinear Programming. North-Holland Publishing Company, Amsterdam, 1967. · Zbl 0157.49701 |

[27] | F. Jarre. A interior point method for minimizing the maximum eigenvalue of a linear combination of matrices.SIAM J. Control and Optimization, 31(5):1360-1377, September 1993. · Zbl 0780.65023 · doi:10.1137/0331064 |

[28] | A.S. Nemirovskii and D.B. Yudin.Problem Complexity and Method Efficiency in Optimization. John Wiley and Sons, Chichester, England, 1983. English translation by E.R. Dawson. |

[29] | Yu. Nesterov and A. Nemirovskii.Interior-Point Polynomial Algorithms in Convex Programming. SIAM Publications, Philadelphia, PA, 1994. · Zbl 0824.90112 |

[30] | M. Newlin and P.M. Young. Mixed ? problems and branch and bound techniques. InProc. IEEE Conf. on Decision and Control, pages 3175-3180, Tucson.AZ., December 16-18, 1992. IEEE Press. |

[31] | C.H. Papadimitriou and K. Steiglitz.Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall Inc., Englewood Cliffs, NJ, 1982. · Zbl 0503.90060 |

[32] | A.H.G. Rinnooy Kan and G.T. Timmer. Stochastic global optimization methods, Part I: Clustering methods; and Part II: Multi level methods.Mathematical Programming, 39:27-56,57-78, 1987. · Zbl 0634.90066 · doi:10.1007/BF02592070 |

[33] | M.G. Safonov.L ? optimal sensitivity vs. stability margin. InProc. IEEE Conf. on Decision and Control, San Antonio, TX, December 1983. IEEE Press. |

[34] | M.G. Safonov and R.Y. Chiang. Real/ComplexK m-Synthesis without curve fitting. In C.T. Leondes, editor,Control and Dynamic Systems. Academic Press, 1993. · Zbl 0822.93031 |

[35] | M.G. Safonov, K.C. Goh, and J.H. Ly. Controller synthesis via Bilinear Matrix Inequalities. InProc. American Control Conf., pages 45-49, Baltimore, MD., June 29 ?July 1, 1994. IEEE Press. |

[36] | O. Toker and H. Ozbay. On the NP-hardness of solving bilinear matrix inequalities and simultaneous stabilization with static output feedback. InProc. American Control Conf., Seattle, WA, 1995. Submitted for consideration. · Zbl 0839.93030 |

[37] | L. Vandenberghe and S.P. Boyd.PDP: Software for Positive Definite Programming, User’s Guide, Version 0.9, October 1994. |

[38] | L. Vandenberghe and S.P. Boyd. Semidefinite programming.Technical Report, I.S.L., Stanford University, November 1994. · Zbl 0845.65023 |

[39] | R.E. Wendell and A.P. Hurter. Minimization of a non-separable objective function subject to disjoint constraints.Operations Research, 24(4):643-657, July?August 1976. · Zbl 0347.90044 · doi:10.1287/opre.24.4.643 |

[40] | M.H. Wright. Interior methods for constrained optimization.Acta Numerica, pages 341-407, 1991. · Zbl 0766.65053 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.