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...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_0885064X_v30_n4_p430_Bank |
| Aporte de: |
| id |
todo:paper_0885064X_v30_n4_p430_Bank |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_0885064X_v30_n4_p430_Bank2023-10-03T15:40:41Z Intrinsic complexity estimates in polynomial optimization Bank, B. Giusti, M. Heintz, J. Safey El Din, M. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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 Bank, B. Giusti, M. Heintz, J. Safey El Din, M. 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. |
| format |
JOUR |
| author |
Bank, B. Giusti, M. Heintz, J. Safey El Din, M. |
| author_facet |
Bank, B. Giusti, M. Heintz, J. Safey El Din, M. |
| author_sort |
Bank, B. |
| 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 |
| url |
http://hdl.handle.net/20.500.12110/paper_0885064X_v30_n4_p430_Bank |
| work_keys_str_mv |
AT bankb intrinsiccomplexityestimatesinpolynomialoptimization AT giustim intrinsiccomplexityestimatesinpolynomialoptimization AT heintzj intrinsiccomplexityestimatesinpolynomialoptimization AT safeyeldinm intrinsiccomplexityestimatesinpolynomialoptimization |
| _version_ |
1807316284630630400 |