research-article

Symbolic optimization of algebraic functions

Authors:

Kazuhiro Yokoyama,

Shinji HaraAuthors Info & Claims

ISSAC '08: Proceedings of the twenty-first international symposium on Symbolic and algebraic computation

Pages 147 - 154

https://doi.org/10.1145/1390768.1390791

Published: 20 July 2008 Publication History

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.

Digital Library

[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]

S. Basu, R. Pollack, and M.-F. Roy. Algorithms in Real Algebraic Geometry, volume 10 of Algorithms and Computation in Mathematics. Springer-Verlag, Berlin, 2nd edition, 2006.

Digital Library

[5]

C. W. Brown. Qepcad b: A program for computing with semi-algebraic sets using CADs. ACM SIGSAM Bulletin, 37(4):97--108, December 2003.

Digital Library

[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]

A. M. Cohen, editor. Computer Algebra in Industry: Problem Solving in Practice. John Wiley & Sons, Chichester, 1993.

Digital Library

[8]

G. Collins. Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In H. Brakhage, editor, Automata Theory and Formal Languages - 2nd GI Conference, volume 33 of Lecture Notes in Computer Science, pages 134--183. Springer-Verlag, Berlin, 1975.

Digital Library

[9]

G. E. Collins and H. Hong. Partial cylindrical algebraic decomposition for quantifier elimination. Journal of Symbolic Computation, 12(3):299--328, September 1991.

Digital Library

[10]

A. Dolzmann, A. Seidl, and T. Sturm. Efficient projection orders for CAD. In Proceedings of the ACM SIGSAM International Symposium on Symbolic and Algebraic Computation, ISSAC2004, pages 111--118. ACM Press, 2004.

Digital Library

[11]

P. Dorato, W. Yang, and C. Abdallah. Robust multi-objective feedback design by quantifier elimination. Journal of Symbolic Computation, 24(2):153--159, August 1997.

Digital Library

[12]

B. Dumitrescu. Positive Trigonometric Polynomials and Signal Processing Applications. Signals and Communication Technology. Springer, Dordrecht, The Netherlands, 2007.

Digital Library

[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]

B. Hanzon and J. M. Maciejowski. Constructive algebra methods for the L2-problem for stable linear systems. Automatica, 32(12):1645--1657, December 1996.

Digital Library

[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.

Digital Library

[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]

M. Kanno, K. Yokoyama, H. Anai, and S. Hara. Parametric optimization in control using the sum of roots for parametric polynomial spectral factorization. In Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 2007, pages 211--218, Waterloo, Ontario, Canada, July-August 2007.

Digital Library

[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.

Digital Library

[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]

D. Lazard and F. Rouillier. Solving parametric polynomial systems. Journal of Symbolic Computation, 42(6):636--667, June 2007.

Digital Library

[24]

A. Montes. A new algorithm for discussing Gr¨obner bases with parameters. Journal of Symbolic Computation, 33(2):183--208, February 2002.

Digital Library

[25]

M. Noro and K. Yokoyama. A modular method to compute the rational univariate representation of zero-dimensional ideals. Journal of Symbolic Computation, 28(1-2):243--264, July 1999.

Digital Library

[26]

K. Ogata. Discrete-time control systems. Prentice-Hall International, London, 2nd edition, 1995.

Digital Library

[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]

A. Suzuki and Y. Sato. A simple algorithm to compute comprehensive Grobner bases using Grobner bases. In Proceedings of the ACM SIGSAM International Symposium on Symbolic and Algebraic Computation, ISSAC2006, pages 326--331. ACM Press, 2006.

Digital Library

[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]

V. Weispfenning. Simulation and optimization by quantifier elimination. Journal of Symbolic Computation, 24(2):189--208, August 1997.

Digital Library

[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]

K. Yokoyama, M. Noro, and T. Takeshima. Solutions of systems of algebraic equations and linear maps on residue class rings. Journal of Symbolic Computation, 14(4):399--417, October 1992.

Digital Library

Cited By

Antal ECsendes TVirágh J(2013)Nonlinear transformations for the simplification of unconstrained nonlinear optimization problemsCentral European Journal of Operations Research10.1007/s10100-013-0310-y21:4(665-684)Online publication date: 29-Jun-2013
https://doi.org/10.1007/s10100-013-0310-y
Zhao HZhan NKapur DLarsen K(2012)A “Hybrid” Approach for Synthesizing Optimal Controllers of Hybrid Systems: A Case Study of the Oil Pump Industrial ExampleFM 2012: Formal Methods10.1007/978-3-642-32759-9_38(471-485)Online publication date: 2012
https://doi.org/10.1007/978-3-642-32759-9_38
Kanno MAnai H(2009)Computer algebra for guaranteed accuracy. How does it help?Japan Journal of Industrial and Applied Mathematics10.1007/BF0318654726:2-3(517-530)Online publication date: Oct-2009
https://doi.org/10.1007/BF03186547
Show More Cited By

Index Terms

Symbolic optimization of algebraic functions
1. Applied computing
  1. Physical sciences and engineering
2. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms

Recommendations

Parametric optimization in control using the sum of roots for parametric polynomial spectral factorization
ISSAC '07: Proceedings of the 2007 international symposium on Symbolic and algebraic computation

This paper proposes an algebraic approach for parametric optimization which can be utilized for various problems in signal processing and control.The approach exploits the relationship between the sum of roots and polynomial spectral factorization and ...
Parametric polynomial spectral factorization using the sum of roots and its application to a control design problem

This paper presents an algebraic approach to polynomial spectral factorization, an important mathematical tool in signal processing and control. The approach exploits an intriguing relationship between the theory of Grobner bases and polynomial spectral ...
Algebraic Functions

Let A be an algebra. We say that the functions f ₁, . . . , f _m : A ⁿ A are algebraic on A provided there is a finite system of term-equalities $${{\bigwedge t_{k}(\overline{x}, \overline{z}) = s_{k}(\overline{x}, \overline{z})}}$$ satisfying that for each $${{\overline{a} \in A^{n}}}$$ , the m -tuple $${{(f_{1}(\overline{a}), \ldots , f_{m}(\overline{a}))}}$$ is the unique solution in A ^m to the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '08: Proceedings of the twenty-first international symposium on Symbolic and algebraic computation

July 2008

348 pages

ISBN:9781595939043

DOI:10.1145/1390768

General Chair:
J. Rafael Sendra
Universidad de Alcalá, Spain
,
Program Chair:
Laureano Gonzalez-Vega
Universidad de Cantabria, Spain

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISSAC '08

Sponsor:

ISSAC '08: International Symposium on Symbolic and Algebraic Computation

July 20 - 23, 2008

Linz/Hagenberg, Austria

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
214
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Antal ECsendes TVirágh J(2013)Nonlinear transformations for the simplification of unconstrained nonlinear optimization problemsCentral European Journal of Operations Research10.1007/s10100-013-0310-y21:4(665-684)Online publication date: 29-Jun-2013
https://doi.org/10.1007/s10100-013-0310-y
Zhao HZhan NKapur DLarsen K(2012)A “Hybrid” Approach for Synthesizing Optimal Controllers of Hybrid Systems: A Case Study of the Oil Pump Industrial ExampleFM 2012: Formal Methods10.1007/978-3-642-32759-9_38(471-485)Online publication date: 2012
https://doi.org/10.1007/978-3-642-32759-9_38
Kanno MAnai H(2009)Computer algebra for guaranteed accuracy. How does it help?Japan Journal of Industrial and Applied Mathematics10.1007/BF0318654726:2-3(517-530)Online publication date: Oct-2009
https://doi.org/10.1007/BF03186547
Tanaka HKanno MTsumura K(2008)Characterization of discrete-time H2 control performance limitation based on poles and zeros2008 47th IEEE Conference on Decision and Control10.1109/CDC.2008.4739004(3700-3705)Online publication date: Dec-2008
https://doi.org/10.1109/CDC.2008.4739004

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents