# Inverse problem with changing number of variables

I have an inverse problem in which the optimal positions for a variable number of injections needs to be determined.

If the number of injections was fixed, I could easily imagine implementing Simplex or Genetic Algorithm (or really any optimisation algorithm). With a changing number of variables, however, it seems that reflection in Simplex and crossover in GA become impossible.

I could use a meta-optimiser to find the optimal positions for a given number of injections and repeat this process for every number of injections, but this is computationally expensive.

Are there any thoughts on what I could do? Or any sources you can point me to (searching "optimising a variable number of variables" unsurprisingly isn't very fruitful)?

• I think a fruitful keyword to search for here would be "optimal experiment design". The feasibility of such problems very much depends on their structure. Could you add some details on the specific problem (what kind of physical model are you considering, how do the "injections" enter this model, how do you determine "optimal"), ideally as a mathematical statement? – Christian Clason Jun 10 '15 at 13:55
• @ChristianClason, injections contain radiation and I want to deliver an optimal amount of radiation to the tumour without delivering too much to the surrounding organs. So I will have cost functions for each of those aspects and will minimise those functions (for my research, I will try both SO and MO optimisers) – mbcx9rb9 Jun 10 '15 at 14:31
• I see. What's the mathematical model (Boltzmann, RTE, diffusive approximation)? (Also, this question might be related: scicomp.stackexchange.com/questions/18795/…) – Christian Clason Jun 10 '15 at 14:39

I have an inverse problem in which the optimal positions for a variable number of injections needs to be determined.

Are there any thoughts on what I could do? Or any sources you can point me to (searching "optimising a variable number of variables" unsurprisingly isn't very fruitful)?

One potential strategy is using a mixed-integer formulation, which is pretty common in applications such as heat exchange network synthesis, or chemical process design, where the number of pieces of equipment used in the design is unknown a priori, but usually bounded above by some number (e.g., due to cost constraints, or some application-specific intuition).

The basic idea is that you assume you have at most, say, $$N$$ injectors, and you introduce integer variables that model how many injectors you have; usually, formulations use binary variables, which can make it easier to "inactivate" constraints corresponding to injectors that don't exist, and "activate" constraints corresponding to the number of injectors currently under consideration.

If the number of injections was fixed, I could easily imagine implementing Simplex or Genetic Algorithm (or really any optimisation algorithm). With a changing number of variables, however, it seems that reflection in Simplex and crossover in GA become impossible.

I presume you mean a Nelder-Mead Simplex algorithm? In theory, it is possible to change the number of decision variables mid-iteration; this sort of strategy is done, for instance, when reduced order models are used within optimization problems (for instance, SQP solvers), although it requires some modifications to the underlying numerical methods to account for the changes in the number of variables; you need (pseudo)invertible mappings between the different dimensional spaces under consideration, and you need an implementation that enables you to change the number of variables mid-method. Most implementations assume the number of variables is fixed once initial problem data is specified, which poses an implementation problem from the outset.

I think the basic problem with this sort of approach for your application is that unlike something like model reduction or adaptive mesh refinement, it's less clear how to decide cheaply when to change the number of decision variables, and by how many.

The first strategy that comes to mind is one you suggest:

I could use a meta-optimiser to find the optimal positions for a given number of injections and repeat this process for every number of injections, but this is computationally expensive.

...and this sort of strategy is going to be expensive, as you point out. A mixed-integer formulation would also be expensive, but with a good solver and good choices of heuristics, you might get lucky.

There's a large literature on "trans-dimensional" Markov Chain Monte Carlo methods in geophysics where the geophysical model consists of a number of layers and the inversion process adjusts the number of layers in addition to the properties of the layers. This might be very relevant to your problem.

However, it's not clear that your problem is an inverse problem at all- if you're deciding where you should perform a series of injections, that's an optimization problem rather than a parameter estimation problem, even if the optimization has to be done in a stochastic sense relative to some random parameters in the system.