Intrinsic complexity estimates in polynomial optimization

It is known that point searching in basic semialgebraic sets and the search for globally minimal points in polynomial optimization tasks can be carried out using (sd) O(n) arithmetic operations, where n and s are the numbers of variables and constraints and d is the maximal degree of the polynomials...

Descripción completa

Guardado en:
Detalles Bibliográficos
Publicado: 2014
Materias:
Degree of varieties
Intrinsic complexity
Polynomial optimization
Computational complexity
Numerical analysis
Arithmetic operations
Complexity estimates
Probabilistic algorithm
Quasi-poly-nomial
Semi-algebraic sets
Polynomials
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v30_n4_p430_Bank
http://hdl.handle.net/20.500.12110/paper_0885064X_v30_n4_p430_Bank
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_0885064X_v30_n4_p430_Bank
record_format dspace
spelling paper:paper_0885064X_v30_n4_p430_Bank2023-06-08T15:46:38Z Intrinsic complexity estimates in polynomial optimization Degree of varieties Intrinsic complexity Polynomial optimization Computational complexity Numerical analysis Arithmetic operations Complexity estimates Degree of varieties Intrinsic complexity Polynomial optimization Probabilistic algorithm Quasi-poly-nomial Semi-algebraic sets Polynomials It is known that point searching in basic semialgebraic sets and the search for globally minimal points in polynomial optimization tasks can be carried out using (sd) O(n) arithmetic operations, where n and s are the numbers of variables and constraints and d is the maximal degree of the polynomials involved. Subject to certain conditions, we associate to each of these problems an intrinsic system degree which becomes in worst case of order (nd) O(n) and which measures the intrinsic complexity of the task under consideration. We design non-uniform deterministic or uniform probabilistic algorithms of intrinsic, quasi-polynomial complexity which solve these problems. © 2014 Elsevier Inc. All rights reserved. 2014 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v30_n4_p430_Bank http://hdl.handle.net/20.500.12110/paper_0885064X_v30_n4_p430_Bank
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Degree of varieties
Intrinsic complexity
Polynomial optimization
Computational complexity
Numerical analysis
Arithmetic operations
Complexity estimates
Degree of varieties
Intrinsic complexity
Polynomial optimization
Probabilistic algorithm
Quasi-poly-nomial
Semi-algebraic sets
Polynomials
spellingShingle Degree of varieties
Intrinsic complexity
Polynomial optimization
Computational complexity
Numerical analysis
Arithmetic operations
Complexity estimates
Degree of varieties
Intrinsic complexity
Polynomial optimization
Probabilistic algorithm
Quasi-poly-nomial
Semi-algebraic sets
Polynomials
Intrinsic complexity estimates in polynomial optimization
topic_facet Degree of varieties
Intrinsic complexity
Polynomial optimization
Computational complexity
Numerical analysis
Arithmetic operations
Complexity estimates
Degree of varieties
Intrinsic complexity
Polynomial optimization
Probabilistic algorithm
Quasi-poly-nomial
Semi-algebraic sets
Polynomials
description It is known that point searching in basic semialgebraic sets and the search for globally minimal points in polynomial optimization tasks can be carried out using (sd) O(n) arithmetic operations, where n and s are the numbers of variables and constraints and d is the maximal degree of the polynomials involved. Subject to certain conditions, we associate to each of these problems an intrinsic system degree which becomes in worst case of order (nd) O(n) and which measures the intrinsic complexity of the task under consideration. We design non-uniform deterministic or uniform probabilistic algorithms of intrinsic, quasi-polynomial complexity which solve these problems. © 2014 Elsevier Inc. All rights reserved.
title Intrinsic complexity estimates in polynomial optimization
title_short Intrinsic complexity estimates in polynomial optimization
title_full Intrinsic complexity estimates in polynomial optimization
title_fullStr Intrinsic complexity estimates in polynomial optimization
title_full_unstemmed Intrinsic complexity estimates in polynomial optimization
title_sort intrinsic complexity estimates in polynomial optimization
publishDate 2014
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v30_n4_p430_Bank
http://hdl.handle.net/20.500.12110/paper_0885064X_v30_n4_p430_Bank
_version_ 1768541617236475904

Ejemplares similares