# How can I check for the accuracy of numerical result to optimization problem?

How can I check for the accuracy of numerical result to optimization problem?

Or when is this possible?

Intuitively it could be possible at least to some extent, when one knows how to find analytic solutions or analytic approximations.

However, what if one just starts with some numerical solution, but the problem is e.g. non-linear. Then is there anyway to know, whether one can trust the optimization routine to have found the correct answer and not some other?

• What do you mean by accuracy? Suppose you want to solve $\min_{x > 0} 1/x$ and you find $x=10^8$, how inaccurate is that? – LinAlg Feb 12 at 16:01
• @LinAlg Well that's the question! And not just such simple problem, but consider e.g. $\min \log(x^2+1)+y^4+xz, x,z \geq 0$. If the numerical algo spits out something, then how would you guess whether it's even near something correct or whether the result is entirely false? Especially if you cannot be entirely sure that your algo is correct or that you're relying on a correct type of algo. – mavavilj Feb 12 at 18:06
• Well, you asked how you can check for 'accuracy', so you need to specify what that means. In my example, is it $\infty$ (in solution space), $10^{-8}$ (in objective value space), or something else? – LinAlg Feb 12 at 18:22
• For a convex problem, if you can obtain a dual feasible point, you can use it to bound the optimality gap. Thus, some convex optimization algorithms are able to provide a certificate that the optimality gap is less than a specified tolerance. – littleO Feb 13 at 5:58
• The problem of @LinAlg does not have an optimum. But assume that a problem has an optimum at $x_0$ with value $y_0=f(x_0)$ and you calculate $\tilde {x_0}$ with a value $\tilde {y_0}=\tilde f (\tilde{x_0})$ then you can ask for the size of $\left\| x_0-\tilde{x_0}\right\|$ or $\left\|y_0-\tilde {y_0}\right\|$. But you do not know $x_0$ and $y_0$. So given only $\tilde {x_0}$ and $\tilde {y_0}$ the you dont know nothing about the quality of your solution. But of course you need additional information to estimate these differences. – miracle173 Feb 13 at 14:04