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?

  • $\begingroup$ 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? $\endgroup$ – LinAlg Feb 12 at 16:01
  • $\begingroup$ @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. $\endgroup$ – mavavilj Feb 12 at 18:06
  • $\begingroup$ 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? $\endgroup$ – LinAlg Feb 12 at 18:22
  • $\begingroup$ 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. $\endgroup$ – littleO Feb 13 at 5:58
  • $\begingroup$ 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. $\endgroup$ – miracle173 Feb 13 at 14:04

If you have an objective function in low dimensions (e.g., one or two scalar variables) then the simplest way of checking your optimising value is to plot the function and look at the optimising value. You should be able to see if the optimising value you have calculated is actually at a minimising/maximising point. If your objective function is in higher dimensions then this gets trickier, but you can always hold some argument values constant (at the optimising point) and check the others with plots.

  • $\begingroup$ No, that is not a possible way. There is not guarantee the plot shows you what you need to see. $\endgroup$ – miracle173 Feb 13 at 15:13
  • $\begingroup$ There is no guarantee, but it is still incredibly useful. $\endgroup$ – Ben Feb 13 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.