In this paper, a convex optimization based approach is proposed for solving the relative spacecraft guidance problem with non-convex obstacle avoidance constraints akin to sequential convex programming approaches proposed in literature, which require solving a sequence of simpler convex programs. However, contrary to existing approaches, the method proposed in this paper ensures that the iterates remain feasible as long as the first iterate is feasible and achieves monotonic convergence of the objective function. Significantly, the proposed methodology leads to anytime solutions, i.e., the computation can be aborted whenever needed and still return a quality solution, which is highly desirable for real-time operations due to potential unexpected situations and limited computation resources. However, most existing methods only guarantee the correctness of the solution when they converge, whereas pre-convergence solution obtained can be useless or even dangerous when applied. The underlying methodology assumes linear dynamics with polynomial path constraints and relies on the convex-concave procedure and sum-of-squares programming to obtain tractable inner convex approximations. To validate the efficacy of the proposed method, a relative spacecraft fuel optimal guidance problem under Clohessy-Hill-Wiltshire (CHW) dynamics is studied under plume impingement, keep-out zones, and obstacle avoidance constraints.