4
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ $f(w)$ is effectively the Heaviside function (although $f(0)=0$ whereas $H(0)=1$, as such I am wondering if I should use an approximation to this which is twice continuously differentiable, or even something like a Legendre polynomial expansion (phys.ufl.edu/~fry/6346/legendrestep.pdf) $\endgroup$ – MikeW Jan 10 '14 at 8:39
4
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ That certainly gives me plenty to look at. I am not interested in a global minimum, I would be happy with a local minimum with a given tolerance. f () is not twice differentiable, however. $\endgroup$ – MikeW Jan 1 '14 at 21:00
  • $\begingroup$ @GeoffOxberry Could you insert a link to libMC++, please? $\endgroup$ – Ali Jan 1 '14 at 22:27
  • $\begingroup$ @Ali Sure. I've edited the post to include links to software pages. $\endgroup$ – Geoff Oxberry Jan 2 '14 at 0:45
  • $\begingroup$ @GeoffOxberry Thanks. (I upvoted your answer 2 hours ago.) Anyway, I failed to find libMC++ with a quick Google search that's why I asked. I didn't know about this software package. Thanks for the info! $\endgroup$ – Ali Jan 2 '14 at 0:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.