constrained minimization in N dimensions

Question

I am looking to create an algorithm to minimize an N dimensional problem. I am unsure how to write it in its generic form, so I will show it in 1, 2 and 3 dimensions Minimize $ \sum_{i} x_i\left [ f\left ( w_i\right )-H \right ], $

Constrained by$ \sum_{I} x_i \left (w_i - R \right) \le 0.01,$

Where $f\left (w\right)\left\{\begin{matrix} 0& w=0\\ 1& w>0 \end{matrix}\right.$

$0 <R\le1,$

$0 <H\le 1,$

$x \in \mathbb{R}^{+},$

$w \in \mathbb{R}^{+},$

In 2D Minimize $ \sum_{i}\sum_{j} x_{1i}x_{2j}\left [ f\left ( w_{ij}\right )-H \right ], $

Constrained by$ \sum_{i}\sum_{j} x_{1i }x_{2j}\left (w_{ij} - R \right) \le 0.01,$

And 3D Minimize $ \sum_{i}\sum_{j}\sum_{k}x_{1i}x_{2j}x_{3k}\left [ f\left ( w_{ijk}\right )-H \right ], $

Constrained by$ \sum_{i}\sum_{j}\sum_{k} x_{1i }x_{2j}x_{3k}\left (w_{ijk} - R \right) \le 0.01,$

The values of R, H and w are all known, so we are solving for x. The first problem I am looking to solve with this is actually in 5D, with each sum over 19. In 1D this looks to me like a basic branch and bounds problem akin to the regularly used example of the knapsack problem, however the unknowns here are all real rather than integer and I'm unsure of how this would generalise to multiple dimensions. Any pointers for literature to read or algorithms to try would be massively appreciated.

To clarify the problem, in case my notation is iffy, I am a physicist and a bit rusty on standard maths notation, expanding the 2D example with

$ w= \begin{bmatrix} 5 & 2\\ 0& 0 \end{bmatrix} $

$R=0.95$

Gives for the constraint

$4.05x_{11}x_{21}+1.05x_{11}x_{22}-0.95x_{12}x_{21}-0.95x_{12}x_{22}\le0.01$

Answer 1

The isolated bilinear and trilinear terms make your problem nonconvex. (Occasionally, these terms can be gathered into sums or differences of squares, but that does not appear to be the case here.) If $f$ is a twice continuously differentiable function, and you're interested in deterministic global optimization, you probably want to use a branch-and-bound method in concert with a method for generating convex relaxations and a deterministic local optimization method (any standard method like sequential quadratic programming, interior-point methods, active-set methods, etc. will work). This combination of methods is pretty hard to come by. BARON is a GAMS solver that has all of these features. It's possible to roll your own with some combination of interval arithmetic, convex analysis, and automatic differentiation. libMC (or its successor MC++) is one tool that I'm aware of that will compute the convex relaxations you need; it works with the automatic differentiation software FADBAD++. Rolling your own solver is likely to be a lot of work.

If you don't care about obtaining a certified globally $\varepsilon$-optimal solution, you could use a local optimization method with multistart, or nondeterministic methods (simulated annealing). My preference is to use multistart in combination with IPOPT, which is an interior-point method that has a limited capability for coping with nonconvexity (better than nothing).