The reason I am wondering this is that all of the reductions from 3-SAT => quadratic programming (or similar NP-hard reductions) involve encoding the underlying NP-hard problem into feasibility testing. If you take out that trick, can you still find another way to encode it?
EDIT: Killed the duality stuff, don't know what I was thinking.
No; I think what you're observing is a side effect of reducing from deicision problems; if you tried to encode an NP optimization problem, you'd end up using more than just the feasibility machinery.
Take MAX-CUT, with variables $x_i\in\{-1,+1\}$ indicating taking a vertex or not, and $W\in\mathbb{R}^{n\times n}$ a matrix of edge weights. Since cut capacity can be written as $\frac 1 2\sum_{i<j} W_{ij}(1-x_ix_j)$, the optimization problem has form $$ \min\ x^TWx \quad\quad \textrm{subject to} \quad \forall i\centerdot x_i^2 = 1. $$ Even the real-valued relaxation $x_i\in [-1,+1]$ is problematic since $W$ is in general indefinite. Like I said above, since we're trying to solve an NP optimization problem, we are definitely relying on the optimization machinery.
As a final point, I'm not sure why you brought duality into the picture, since the usual guarantees of strong duality are murky once nonconvexity enters the picture ....
