Unsolvability of some optimization problems

DOI10.1016/J.AMC.2005.05.025MaRDI QIDQ2489339zbMATH OpenOpenAlexFDO

Authors Wenxing Zhu

Publication date 16 May 2006

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2005.05.025

zbMATH Keywords

Constraint satisfactionGlobal optimizationInteger programmingNonlinear equationsUnsolvability

Mathematics Subject Classification ID

Numerical computation of solutions to systems of equations (65H10) Numerical mathematical programming methods (65K05) Integer programming (90C10) Nonlinear programming (90C30)

Review text

Using Hilbert's 10th problem the author shows that over an unbounded domain the integer programming, nonlinear equations, and continuous global minimization problems are undecidable, i.e., that it is impossible to construct an algorithm to find a solution for these problems or decide that the problem has no solution. Moreover, although the continuous global minimization problem can only be solved under the assumption that the solution space is bounded, the author proves that it may also be unsolvable if there are no assumptions on the objective function. In particular, if there are no assumptions on the objective function of the box-constrained global minimization problem then the problem is undecidable.

Recommendations

• Undecidability in number theory
• Global Optimization over Unbounded Domains
• Questions of decidability and undecidability in Number Theory
• scientific article; zbMATH DE number 42574
• scientific article; zbMATH DE number 1261118

Cited in

(12)

• Dynamic globally concavized filled function method for continuous global optimization
• Symmetry in mathematical programming
• Optimisation impossible
• scientific article; zbMATH DE number 610245 (Why is no real title available?)
• Unsolvability Cores in Classification Problems
• A new parameter free filled function for solving unconstrained global optimization problems
• A new filled function for global minimization and system of nonlinear equations
• A new parameter-free continuously differentiable filled function algorithm for solving nonlinear equations and data fitting problems
• Reformulations in mathematical programming: automatic symmetry detection and exploitation
• A novel single-parameter continuously differentiable filled function for global optimization
• Detecting and handling reflection symmetries in mixed-integer (nonlinear) programming and beyond
• Filled function method that avoids minimizing the objective function again

This page was built for publication: Unsolvability of some optimization problems

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