(1) For each x_k, you will need to find a minorizing surrogate function Q(x;x_k), i.e., it satisfies Q(y;x_k)<=f(y) for all y with equality at y=x_k. You must find such a function that is easy to minimize analytically over the feasible set. Then,
f(x_k) - f(x_opt)<=f(x_k)- min_y Q(y;x_k)
For a good choice of Q(), the right hand side will --->0 as x_k-->x_opt and you can monitor when it falls below your desired epsilon.
For example, in unconstrained problems in which a global lower bound on the Hessian eigenvalues L is known, you could construct the quadratic surrogate
Q(y;x_k)= f(x_k)+ dot(grad(x_k),y-x_k)+ L/2*norm(y-x_k)^2
whose minimum is f(x_k)-grad(x_k)/(2*L). This leads to the upper bound
f(x_k) - f(x_opt) <= grad(x_k)/(2*L)
so you would stop when grad(x_k)<= 2*L*epsilon.