All of this assumes that you're not in one of the weird cases where strong duality doesn't hold, but you've already said that this is OK.

Another issue is that various authors disagree on which of the primal-dual pair of problems is the "primal" and which is the "dual" problem. Is your primal problem the one with constraints of the form $A(X)=b$, $X$ positive semidefinite?

Your wording is a little bit unclear because of your use of "the" rather than "a." Are you asking, "I have a dual feasible (but not necessarily optimal) solution to an SDP. Can I use it to obtain a primal feasible solution?" Or, are you asking about whether you can get a primal optimal solution from a dual optimal solution?

I'm confused- the original poster referred to the gradient as if this was a smooth problem. How did we jump to considering nonsmooth problems?

There are certainly convergence theorems that work as long as the step direction is a descent direction for the function being minimized and the step length is selected so as to satisfy some special conditions (e.g. the Armijo conditions.) I don't think it's possible to say much more without knowing exactly what's being done to the gradient.

It's worth mentioning that first order methods that make recursive use of gradients from previous iterations can do better than $O(1/\epsilon)$ iterations. For example, Nesterov's fast method takes $O(\sqrt{L/\epsilon})$ iterations to get an $\epsilon$ optimal solution. The practical performance of these methods is a different issue.

You should step back and look at the literature on conservative numerical methods for PDE's. By asking your question in this narrow fashion, you're likely to miss out on broader answers.

With respect to option 1, I've witnessed a talk where the speaker managed to list results from a couple of dozen papers that he'd written. He was way too proud of his publications. The talk was not well received because of his attitude and also because most of the audience wasn't impressed with a bunch of results in a narrow field. Furthermore, most of the audience was in no position to understand the results- they weren't familiar with the terminology or notation used in his field.

No, it's not gradient ascent- it's "projected gradient ascent." Look for information on "projected gradient descent" methods for minimization problems- the convergence of the projected gradient descent method is standard textbook material.

You haven't described any projection onto the nonnegative orthant- I assume that you're doing that. Although Q is nonnegative, it's conceivable that negative elements in d could cause the iteration to to move outside of the nonnegative orthant. If you used $y_{n+1}=2Qx_{n}+d$, then you'd have a projected gradient ascent algorithm for which there are plenty of convergence results.

You can use the symmetry of your matrix to cut the memory traffic in half, but it takes careful coding to get that efficiency in practice.

The material on algorithms for solving convex optimization problems is actually later in the book. However, I have to say that the coverage of algorithms for solving convex optimzation problems in Boyd and Vandenberghe is much less useful than the material on formulating convex optimization problems and the basic theory (optimality conditions, etc.) that is in this book. Frankly, you should try to implement your own solver. Rather, use a well supported package such as CVX to do the work.