Solving nonlinear optimization problem with combinational constraints

I have to minimize a nonlinear objective function $f(x_0, x_1, x_2, x_3, x_4, x_5)$ with 6 variables.

The constraints governing these these variables are a mix of nonlinear inequality constraints, and some combinatorial constraints.

For the nonlinear inequality constraints and the objective function, I can evaluate the functional and Jacobian values as long as all the variables ($x_0$ to $x_5$) are specified. I can also obtain the Hessian values if I want, but I afraid that the values might be inaccurate.

Also, the objective function and the nonlinear inequality constraints are always continuous, but only piecewise differentiable over the region of interest.

By combinatorial constraints, I mean that ${x_3, x_4, x_5}$ can only take a list of discrete values together, such as {3,4,5}, {8,7,18} and so on.

Is there any existing scientific package ( or mathematical algorithm, I can program the solver myself) that does what I need?

Note: the inequality constraints are highly nonlinear and can only be evaluated via numerical means.

1 Answer

At best, your problem is a mixed-integer nonlinear program (MINLP).

Assuming you can decompose your problem into subregions, so that in each region, your objective function and all constraints are twice continuously differentiable, you could probably use BARON, Couenne, or Bonmin. I've assume that a decent locally optimal solution is satisfactory; if a globally optimal solution is required, BARON is probably your best option, but will require analytical expressions for your objective function and constraints.

If you cannot do that, then you'll probably have to find a nonsmooth mixed-integer nonlinear programming solver. I could not find one with a cursory Google search, but perhaps one exists. I suppose you could wrap a non-smooth solver in a branch-and-bound algorithm, if you wanted to.

Unless you plan on pursuing the implementation of such solvers as the primary thrust of your research, I strongly recommend that you avoid trying to program the solver yourself. Many of the best optimization solvers are the product of man-decades of work, and simple implementations often achieve only a small fraction of the performance of a state-of-the-art implementation. (I am currently in the process of implementing a mixed-integer programming solver as part of my research, and expect that programming a respectable implementation will be a multi-year effort.)