Skip to main content

How was upper bound generated for non-linear, non-convex maximization optimization model?

Answered

Comments

3 comments

  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Gurobi uses an interior point solver to search for feasible solutions of nonlinear nonconvex problems. One book about primal-dual interior methods can be found here. Interior point methods have are of big interest in the nonlinear nonconvex optimization community. One of the most popular nonlinear interior point solvers is the open-source solver IPOPT (not used by Gurobi).

    Once a solution is available, neighborhood search methods such as RINS are applied to try to improve the given solution point.

    Another way of finding feasible solutions for nonlinear nonconvex problems is through branching on continuous variables and checking the branching point or the LP relaxation solution point. This can sometimes be the best way of finding feasible solutions.

     

    0
  • Yifei Sun
    First Comment
    Gurobi-versary
    First Question

    Hi Jaromil, 

    Thanks for your quick answer. This is very helpful! I also wonder how Gurobi calculates the provable upper bound (not the feasible solution) for the non-linear maximization problem. 

    Thanks,
    Yifei

    0
  • Jaromił Najman
    Gurobi Staff Gurobi Staff

    Hi Yifei,

    Gurobi uses a spatial branch-and-bound algorithm with an outer approximation approach. You can find more details in our webinar on non-convex features and tech talk through non-convex optimization.

    A good starting literature for nonlinear global optimization is Global Optimization by Horst & Tuy.

    Best regards, 
    Jaromił

    0

Please sign in to leave a comment.