Autonomous rendezvous and proximity operations of spacecraft require the capability of onboard planning and executing highly constrained trajectories without ground support. This paper presents a general and rigorous methodology and algorithmic procedure toward this goal with a target vehicle that can be in an arbitrary orbit. The rendezvous and proximity operations problem is formulated as a nonlinear optimal control problem, subject to various state and control inequality constraints and equality constraints on interior points and terminal conditions. By a lossless relaxation technique, a relaxed problem is formed, the solution of which is proven to be equivalent to that of the original rendezvous and proximity operations problem. The relaxed problem is then solved by a novel successive solution process, in which the solutions of a sequence of constrained subproblems with linear, time-varying dynamics are sought. After discretization, each of these problems becomes a second-order cone programming problem. Their solutions, if they exist, are guaranteed to be found by a primal-dual interior-point algorithm. The efficacy of the proposed methodology is strongly supported by numerical experiments.