3
$\begingroup$

Can anyone recommend a straightforward quadratic programming (QP) algorithm suitable for an undergraduate engineering class? I'm interested in finding an algorithm that they can easily grasp and implement, say in Python, through a hands-on learning approach.

Best, Walton.

$\endgroup$

2 Answers 2

5
$\begingroup$

You can optimize convex equality-constrained QP by solving a linear equation system (the KKT conditions). This is good knowledge to disseminate and easy for undergrads to grasp in a lecture. Moreover, there are many tools out there for solving equation systems so the only challenge for your undergrads is setting up the equation system and calling a function.

Once that is cleared, you can challenge them to write an active set method to solve convex inequality-constrained QP. This is a natural generalization of the simplex method which many undergrads will most likely encounter in their studies anyway, and combinatorial in nature meaning that (at the cost of performance) your undergrads can focus on the logic of decisions derived from mathematical expressions, rather than the numerical challenges of floating-point precision.

Whether this approach is suitable all depends on your learning goals.

$\endgroup$
1
  • $\begingroup$ Thank you very much, Henrik! $\endgroup$ Jun 27, 2023 at 1:54
4
$\begingroup$

Some really simple but higher-level approaches (no low-level pivoting required) could be:

  1. A simple Sequential Linear Programming algorithm (useful approach for other nonlinear problems and a nice application of a Taylor series)
  2. Form LCP from KKT conditions, and solve as a MIP (makes you understand complementarity)

These methods can help students look at QP problems in a different way (as NLP or as complementarity problem). Not a real programming challenge however (I have taught these things using remarkably few lines of GAMS code).

$\endgroup$
5
  • $\begingroup$ Better yet, solve by SQP. Converges in one iteration. $\endgroup$ Jun 7, 2023 at 15:35
  • 1
    $\begingroup$ Depends on the definition of iteration. $\endgroup$ Jun 7, 2023 at 15:57
  • $\begingroup$ In this case, "outer" iteration of SQP. $\endgroup$ Jun 7, 2023 at 16:29
  • 1
    $\begingroup$ Actually, I know a lot of QP models (matrix balancing models) that are solved with an sqp solver like conopt, because that is a popular NLP solver under economists. Such models are solved as part of data prep steps. $\endgroup$ Jun 7, 2023 at 19:18
  • $\begingroup$ Many thanks you all! $\endgroup$ Jun 27, 2023 at 1:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.