5
$\begingroup$

In an exam, I studied Theoretical approaches to converting constrained minimum problems into unconstrained minimum problems. Specifically:

KKT conditions

Projection Gradient Descent

Penalty and Barrier Methods

But how are nonlinear constrained problems solved numerically with KKT conditions? I can't find any library in Python that uses them.

Same for Projection Gradient Descent and Penalization and Barrier methods, I can't find any library in Python.

Are these just theoretical methods, or are they also used in practice? What are the algorithms and library in Python to solve nonlinear programming problems in practice and also in business?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Questions solely about how software works are off-topic here, but you may have a real statistical question buried here. You may want to edit your question to clarify the underlying statistical issue. You may find that when you understand the statistical concepts involved, the software-specific elements are self-evident or at least easy to get from the documentation. $\endgroup$
    – kjetil b halvorsen
    Jan 15, 2021 at 23:58
  • $\begingroup$ Gradient descent indeed has a constrained version, although not well known. For example, it is not implemented in Mathematica, and I have requested that it be done for some future version. Penalization methods are widely implemented for constrained regression. KKT I do not know about off-hand. For some routines, sneaking in a absolute value works, and that would be a barrier method. A complete answer would be book length, you are as a first approximation asking for a very long answer, under the "numerical methods" heading. You need to read up on it to develop a decent understanding. $\endgroup$
    – Carl
    Jan 17, 2021 at 1:44

2 Answers 2

Reset to default
4
$\begingroup$

A common and free NLP solver is IPOPT. IPOPT implements an interior-point line-search filter method, a variation of the interior-point method, these interior point method uses the barrier functions you are aware of. Interior point methods are also useful for large linear systems, as the number of interior steps doesn't depend on the number of constraints. IPOPT is callable from Python.

As for penalty methods there is a solver called WORHP which includes one. It also has a quiet ugly Python API and could use a wrapper in a modeling language. I have started to make it accessible from JuMP but I haven't completed that.

KKT conditions are often employed to verify the goodness of a solution. There are also solvers that work using this augmented Lagrangian algorithm such as Lancelot. I've never used Lancelot so I can't comment on it's use but it is an old solver.

I am not aware what Projection Gradient Descent is so I can't comment on that.

Improve this answer
$\endgroup$
3
$\begingroup$

A commonly used alternative to Interior Point methods is Sequential Quadratic Programming (SQP) https://www.math.uh.edu/~rohop/fall_06/Chapter4.pdf.

SQP essentially amounts to iteratively numerically solving the KKT conditions, while "rolling downhill" (for minimization).

There are several commercial, as well as free, nonlinear programming solvers of varying quality available under Python which either are exclusively based on SQP, or have SQP as an algorithm option.

Improve this answer
$\endgroup$

Your Answer

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