Is it possible to get the exact solution of a largescale convex quadratic programming problem (quadratic objective, linear inequality constraints)?
OngoingFor a convex quadratic programming problem with the quadratic objective and linear inequality constraints. I had an example with 3 variables and 3 constraints. In the sample answer, we can solve them using the KKT condition to get the exact solutions.
Analytically, I think I can get the exact solution (global optimum) of the aforementioned optimization problems regardless of the question size using the KKT condition (or some other method, like the simplex method). But in tutorials, it said that it is very "expensive" to do so when we have largescale convex quadratic programming problems. Instead, we use some numerical methods to solve them, usually, we set some tolerance for the objective function (for example, 10^−6).
My question is, how expensive it is if we want to get the exact solution (global optimum) of the quadratic programming problem I mentioned before? And how it relates to the number of inequality of constraints? Is it impossible to calculate it even with computers? I will really appreciate it if you can offer some references for this problem.

Hi Ximeng Fan,
As often, the answer is: It depends!
The first question is what "largescale" actually means for you (in terms of numbers of variables and constraints)?
We have seen models with millions of variables and constraints that can be solved quite easily, and we have seen small models that are still open. It highly depends on the internal structure of the model which is not easy to identify and to describe.If your model is a convex QP, then current barrier implementations are quite good at solving huge models to global optimality.
If you have the model at hand, it is usually not much effort to just throw it to a solver (preferably Gurobi ;)) and see what happens. You might be surprised what current solvers are able to do, provided that you have enough memory in your machine in case of large models.Best regards,
Mario0 
Hi Mr. Mario,
Yes, I have been using Gurobi for a long time. What I am confused about is that in our courses, we were asked to manually solve smallscale quadratic programming problems (with the quadratic objective and linear inequality constraints), a similar example can be found here http://www.universalteacherpublications.com/univ/ebooks/or/Ch15/examp1.htm , we can get the exact solution of the problem (meaning that it is exact the optimal solution with zero errors).
I suspect that for largescale (maybe 2000 variables and 10000 constraints) problems, we should also be able to get an 'exact solution' if it follows the reqirements:1, strictly convex; 2, having the format of quadratic objective and linear inequality constraints.
But as far as I know, the interior point method is an iterative method to get a nearoptimal solution. The iterations will terminate when the difference between two iterations is smaller than the setting tolerance (usually $10^{7}$). So I wonder if is it possible to have the exact solution to the aforementioned problems,and how expensive to get the exact solution (in terms of the computation).
0
Please sign in to leave a comment.
Comments
2 comments