How to verify whether a solution to an optimization problem is correct.

Question

Consider a general optimization problem

min f(x)

subject to g(x) <=0

       h(x)=0,

where x denotes a vector and the functions are $R^n$ -> $R^n$.

suppose somebody gave me a solution x*, how can I verify whether this solution is correct?

One straight forward idea is to check whether x* satisfies the constrains. But how can I determine whether x* will minimize f(x)?

Answer 1

You could try and plot it (using some mathematics software) and see if the solution is actually a minimum within the constrains.

Answer 2

The difficulty to determine wheather some point $x^\ast$ is optimal depends on the structure of the optimization problem.

Non-convex optimization problems: Generally, for non-convex problems, proving global optimality is not an easy task and can be NP-hard. Worse, it can be even NP-hard proving local optimiality.

Convex optimization: To be optimal, the point $x^\ast$ must satisfy the KKT-conditions, see http://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions. The necessary KKT-conditions are also sufficient for optimality in some cases.