Nonlinear optimization / fmincon algorithm mathematics-level question

1 view (last 30 days)
D zepp
D zepp on 13 Feb 2021
Commented: D zepp on 17 Feb 2021
I am building an fmincon-style solver. It needs to be able to solve symbolic expressions with nonlinear equality and inequality constraints.
My solver uses a fairly basic Newton-Raphson gradient-descent active set algorithm to solve a set of KKT conditions.
In fmincon, nonlcon is used as a parameter for the nonlinear constraints. Me myself, I have only made a solution for linear and quadratic constraints. If I want to move onto nonlinear constraints, is it okay for me to assume that a gradient-descent algorithm can handle nonlinear expressions? In other words, can I just add nonlinear equality constraints to the equality constraints vector that I have for linear/quadratic constraints; and can i also add nonlinear inequality constraints to the inequality constraints vector that I already have?
I hope to get some insights here. I have tried it with some examples and so far it seems to work but I am not sure if it holds up for all nonlinear expressions.
If anyone needs more information to help me, feel free to ask and I will try to answer as precise as possible. Thank you.

Accepted Answer

Walter Roberson
Walter Roberson on 13 Feb 2021
You need different handling for nonlinear constraints.
For linear equality or inequality constraints, you can use the information from the numerically-encoded constraints to decide whether a proposed position would be within range, and if not to use the linear information to "back off" to a point that would be in range or on the boundary. You do not need to evaluate the objective function at the new position or evaluate any function at the new position: you can calculate the boundaries fairly directly.
For nonlinear constraints, the constraint function is a "black box": you pass it a proposed position and it replies "yes" or "no", but it does not give you enough information to be able to predict where the boundary is. Provided that the nonlinear constraints were well-coded, you might be able to use a gradient estimation from them to figure out and approximate direction to the boundary, but finding the boundary can be hard. That is especially difficult for nonlinear equality constraints: it can be difficult to find any points in the valid region.
  3 Comments
D zepp
D zepp on 17 Feb 2021
Thank you. This majorly improved my insight. I adjusted my algorithm and it seems to work more or less. Mostly just some runtime issues.

Sign in to comment.

More Answers (0)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!