Complexity results for some global optimization problems

DOI10.1007/S10957-008-9448-5zbMATH Open1173.90545OpenAlexW2036807485MaRDI QIDQ1024247FDOQ1024247

Authors: Marco Locatelli 

Publication date: 16 June 2009

Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10957-008-9448-5

Recommendations

• scientific article; zbMATH DE number 3878714
• scientific article; zbMATH DE number 757674
• Algorithms and Computation
• Complexity and algorithms for nonlinear optimization problems
• On complexity of a global optimization problem

zbMATH Keywords

global optimizationcomplexityseparable functionsapproximation problems

Mathematics Subject Classification ID

Nonlinear programming (90C30) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• Approximation algorithms for indefinite quadratic programming
• Quadratic programming with one negative eigenvalue is NP-hard
• \(NP\)-hardness of linear multiplicative programming and related problems
• Title not available (Why is that?)
• Approximating quadratic programming with bound and quadratic constraints
• Geometric optimization problems likely not contained in \(\mathbb A\mathbb P\mathbb X\)
• The complexity of approximating a nonlinear program
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• Computational complexity of norm-maximization
• Title not available (Why is that?)

Cited In (10)

• The complexity results of the sparse optimization problems and reverse convex optimization problems
• The complexity of optimization problems
• The complexity of optimizing over a simplex, hypercube or sphere: a short survey
• Studying the complexity of global verification for NP-hard discrete optimization problems
• Title not available (Why is that?)
• On complexity of unconstrained hyperbolic 0--1 programming problems
• A class of increasing positively homogeneous functions for which global optimization problem is NP-hard
• On complexity of a global optimization problem
• On the complexity of optimization over the standard simplex
• Title not available (Why is that?)

This page was built for publication: Complexity results for some global optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1024247)