Symbolic optimization of algebraic functions

ABSTRACT

This paper attempts to establish a new framework of symbolic optimization of algebraic functions that is relevant to possibly a wide variety of practical application areas. The crucial aspects of the framework are (i) the suitable use of algebraic methods coupled with the discovery and exploitation of structural properties of the problem in the conversion process into the framework, and (ii) the feasibility of algebraic methods when performing the optimization. As an example an algebraic approach is developed for the discrete-time polynomial spectral factorization problem that illustrates the significance and relevance of the proposed framework. A numerical example of a particular control problem is also included to demonstrate the development.

REFERENCES

• 1: H. Anai, S. Hara, M. Kanno, and K. Yokoyama. Parametric polynomial spectral factorization using the sum of roots and its application to a control design problem. Technical Report METR 2008-04, Department of Mathematical Informatics, The University of Tokyo, January 2008. Also submitted to the Journal of Symbolic Computation.
• 2: H. Anai, H. Yanami, K. Sakabe, and S. Hara. Fixed-structure robust controller synthesis based on symbolic-numeric computation: Design algorithms with a CACSD toolbox (invited paper). In Proceedings of CCA/ISIC/CACSD 2004, pages 1540--1545, Taipei, Taiwan, 2004.
• 3: B. D. O. Anderson, N. K. Bose, and E. I. Jury. Output feedback stabilization and related problems-solution via decision methods. IEEE Transactions on Automatic Control, AC-20(1):53--66, February 1975.
• 4: Saugata Basu , Richard Pollack , Marie-Françoise Roy, Algorithms in Real Algebraic Geometry (Algorithms and Computation in Mathematics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 5: Christopher W. Brown, QEPCAD B: a program for computing with semi-algebraic sets using CADs, ACM SIGSAM Bulletin, v.37 n.4, December 2003 [doi>10.1145/968708.968710]
• 6: J. Chen and R. H. Middleton, editors. IEEE Transactions on Automatic Control: Special Section on New Developments and Applications in Performance Limitation of Feedback Control, volume 48, number 8. IEEE Control Systems Society, August 2003.
• 7: Arjeh M. Cohen, Computer Algebra in Industry: Problem Solving in Practice: Proceedings of the 1991 Scafi Seminar at Cwi, Amsterdam, John Wiley & Sons, Inc., New York, NY, 1993
• 8: George E. Collins, Hauptvortrag: Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.134-183, May 20-23, 1975
• 9: George E. Collins , Hoon Hong, Partial cylindrical algebraic decomposition for quantifier elimination, Journal of Symbolic Computation, v.12 n.3, p.299-328, Sept. 1991 [doi>10.1016/S0747-7171(08)80152-6]
• 10: Andreas Dolzmann , Andreas Seidl , Thomas Sturm, Efficient projection orders for CAD, Proceedings of the 2004 international symposium on Symbolic and algebraic computation, p.111-118, July 04-07, 2004, Santander, Spain [doi>10.1145/1005285.1005303]
• 11: Peter Dorato , Wei Yang , Chaouki Abdallah, Robust multi-objective feedback design by quantifier elimination, Journal of Symbolic Computation, v.24 n.2, p.153-159, August 1997 [doi>10.1006/jsco.1997.0120]
• 12: B. Dumitrescu. Positive Trigonometric Polynomials and Signal Processing Applications. Signals and Communication Technology. Springer, Dordrecht, The Netherlands, 2007.
• 13: I. A. Fotiou, P. Rostalski, P. A. Parrilo, and M. Morari. Parametric optimization and optimal control using algebraic geometry methods. International Journal of Control, 79(11):1340--1358, November 2006.
• 14: L. Gonzalez-Vega, T. Recio, H. Lombardi, and M.-F. Roy. Sturm-Habicht sequences determinants and real roots of univariate polynomials. In B. Caviness and J. Johnson, editors, Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and Monographs in Symbolic Computation, pages 300--316. Springer, Wien, New York, 1998.
• 15: Bernard Hanzon , J. M. Maciejowski, Constructive algebra methods for the L2-problem for stable linear systems, Automatica (Journal of IFAC), v.32 n.12, p.1645-1657, Dec. 1996 [doi>10.1016/S0005-1098(96)80002-1]
• 16: H. Hoon and R. Liska, editors. Journal of Symbolic Computation: Special Issue on Application of Quantifier Elimination, volume 24, number 2. Academic Press, August 1997.
• 17: M. Kanno, H. Anai, and K. Yokoyama. On the relationship between the sum of roots with positive real parts and polynomial spectral factorization. In T. Boyanov et al., editors, Numerical Methods and Applications - 6th International Conference, NMA 2006, Borovets, Bulgaria, August, 2006, Revised Papers, volume 4310 of Lecture Notes in Computer Science, pages 320--328. Springer-Verlag, Heidelberg, 2007.
• 18: M. Kanno, S. Gandy, H. Anai, and K. Yokoyama. Optimizing the maximal real root of a polynomial by a special cylindrical algebraic decomposition. Presented at Mathematical Aspects of Computer and Information Sciences 2007, Paris, France, December 2007.
• 19: M. Kanno, S. Hara, H. Anai, and K. Yokoyama. Sum of roots, polynomial spectral factorization, and control performance limitations. In Proceedings of the 46th IEEE Conference on Decision and Control, pages 2968--2973, New Orleans, Louisiana USA, December 2007.
• 20: Masaaki Kanno , Kazuhiro Yokoyama , Hirokazu Anai , Shinji Hara, Parametric optimization in control using the sum of roots for parametric polynomial spectral factorization, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada [doi>10.1145/1277548.1277578]
• 21: M. Kanno, K. Yokoyama, H. Anai, and S. Hara. Symbolic optimization of algebraic functions. Technical Report METR 2008, Department of Mathematical Informatics, The University of Tokyo, April 2008.
• 22: V. KuÇcera. A tutorial on H2 control theory: The continuous time case. In M. J. Grimble and V. KuÇcera, editors, Polynomial Methods for Control Systems Design, pages 1--55. Springer, London, 1996.
• 23: Daniel Lazard , Fabrice Rouillier, Solving parametric polynomial systems, Journal of Symbolic Computation, v.42 n.6, p.636-667, June, 2007 [doi>10.1016/j.jsc.2007.01.007]
• 24: Antonio Montes, A new algorithm for discussing Gröbner bases with parameters, Journal of Symbolic Computation, v.33 n.2, p.183-208, February 2002 [doi>10.1006/jsco.2001.0504]
• 25: Masayuki Noro , Kazuhiro Yokoyama, A modular method to compute the rational univariate representation of zero-dimensional ideals, Journal of Symbolic Computation, v.28 n.1-2, p.243-263, July/Aug. 1999 [doi>10.1006/jsco.1999.0275]
• 26: Katsuhiko Ogata, Discrete-time control systems (2nd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 27: H. Park. Optimal design of synthesis filters in multidimensional perfect reconstruction FIR filter banks using Grobner bases. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 49(6):843--851, June 2002.
• 28: A. H. Sayed and T. Kailath. A survey of spectral factorization methods. Numerical Linear Algebra with Applications, 8(6-7):467--496, September-November 2001.
• 29: Akira Suzuki , Yosuke Sato, A simple algorithm to compute comprehensive Gröbner bases using Gröbner bases, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy [doi>10.1145/1145768.1145821]
• 30: H. Tanaka, M. Kanno, and K. Tsumura. Expressions for discrete-time H2 control performance limitations based on poles and zeros. In Proceedings of the SICE 8th Annual Conference on Control Systems (CD-Rom), Kyoto, Japan, March 2008.
• 31: Volker Weispfenning, Simulation and optimization by quantifier elimination, Journal of Symbolic Computation, v.24 n.2, p.189-208, August 1997 [doi>10.1006/jsco.1997.0122]
• 32: V. Weispfenning. A new approach to quantifier elimination for real algebra. In B. Caviness and J. Johnson, editors, Quantifier Elimination and Cylindrical Algebraic Decomposition, Texts and Monographs in Symbolic Computation, pages 376--392. Springer, Wien, 1998.
• 33: Kazuhiro Yokoyama , Masayuki Noro , Taku Takeshima, Solutions of systems of algebraic equations and linear maps on residue class rings, Journal of Symbolic Computation, v.14 n.4, p.399-417, Oct. 1992 [doi>10.1016/0747-7171(92)90014-U]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms

Additional Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING

General Terms:
Algorithms, Experimentation

Keywords:
groebner basis, parametric optimization, polynomial spectral factorization, quantifier elimination