Is it possible to get the exact solution of a large-scale convex quadratic programming problem (quadratic objective, linear inequality constraints)?

Ongoing

ximeng fan

• March 27, 2023 21:31

For 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 large-scale 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.

Related to

• Tolerances

0

• 

  Mario Ruthmair

  Gurobi Staff

  • March 28, 2023 10:30

  Hi Ximeng Fan,

  As often, the answer is: It depends!

  The first question is what "large-scale" 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,
  Mario

  0
• 

  ximeng fan

  • March 28, 2023 13:47

  

  

  

  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 small-scale 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 large-scale (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 near-optimal 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.