Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials

Details Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials

2006-06-20

arxiv.org/abs/math/0606476v3

Mathematics

Optimization and Control

This paper has 23 pages

Scientific paper

This paper discusses how to find the global minimum of functions that are summations of small polynomials (``small'' means involving a small number of variables). Some sparse sum of squares (SOS) techniques are proposed. We compare their computational complexity and lower bounds with prior SOS relaxations. Under certain conditions, we also discuss how to extract the global minimizers from these sparse relaxations. The proposed methods are especially useful in solving sparse polynomial system and nonlinear least squares problems. Numerical experiments are presented, which show that the proposed methods significantly improve the computational performance of prior methods for solving these problems. Lastly, we present applications of this sparsity technique in solving polynomial systems derived from nonlinear differential equations and sensor network localization.

Affiliated with

Also associated with

No associations

Rating

Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-40247