I cannot imagine which linear obejctive you have in mind to substitute as an objective the QP. As I understand the term you got quadratic objective and linear constraints you would end up with an LP, which of course is easier to solve. The solution of the LP (if you leave the constraints as they were) is feasible. The only drawback would be: the solution will normally not be optimal for the original problem,

No matter what linear objective you use (if it is not constant), if you substitute the quadratic objective by a linear one using the same constraint set, solutions of the LP are always boundary points of the constraint polyhedron, while the solution of the original QP can well be an inner point.

You could for instance approximate the QP by a sequence of problems, adding supporting hyperplanes to the obejctive in the current iterate. If the objective is convex, this leads to a series of LPs with an increasing number of constraints. Did you refer such kind of idea with your question?

Modern commercial solvers like Gurobi and CPLEX include solution techniques for convex QPs, Using these you would not have to resort to selfmade approximation schemes.

Hi! Thanks for the answer. My problem was mainly regarding modeling, but I think I have all the ingredients now, Though, the idea of approximating a QP problem with a sequence of LP problems as you suggest is interesting as well! :-)

Solving a convex QP by sequence LPs which usually be much slower than sloving the problem directly by a commercial code such MOSEK or the codes mentioned by Ralf.

At present, no reduction of QP to LP is known. Wiki, http://en.wikipedia.org/wiki/Quadratic_programming contains:

For positive definite Q, the ellipsoid method solves the problem in polynomial time.[6] If, on the other hand, Q is indefinite, then the problem is NP-hard.[7] In fact, even if Q has only one negative eigenvalue, the problem is NP-hard.[8]

I agree with Erling and Ralf. Particularly if your QP is convex, try using the barrier method. While it has more work to do at each iterations for a QP as compared to the LP, the number of iterations doesn't grow very fast. And if your quadratic objective is separable (i.e., the Q matrix is diagonal), the extra work is even less.

If your QP is nonconvex, the computations become more challenging. While you may want to consider solving some sort of sequence of LPs or convex QPs, the recently released CPLEX 12.6 offers support for finding a global optimum to a nonconvex QP as well.

I think Frank-Wolfe method (also called method of convex combinations) is worth a try. It solves a sequence of linear programming approximations to your problem, by using a first order model of the objective function. The advantage of it is that you can benefit from all kind of specialized methods for solving huge linear programs, such as specilized simplex-like methods, column generation, Benders decomposition, and so on...

http://en.wikipedia.org/wiki/Frank%E2%80%93Wolfe_algorithm

Since the Frank-Wolfe method requires a feasible solution to the linear constraints and bounds of your QP, you might get better convergence if you jump start the procedure by solving the LP associated with your QP. Or, if Q is convex and you can easily derive or compute the Cholesky factor Q = L'L, you could obtain your starting point by solving the following augmented LP, where you first replace the original quadratic objective term x'Qx with x 'L'Lx, then substitute y = Lx and linearize the resulting quadratic objective y'y:

min e'y // e = (1,1,...,1)

Ax = b

y - Lx = 0

l