3
$\begingroup$

Suppose we have an optimization problem $$ \mathbf{x} = (x_1, x_2, \ldots, x_m) = \arg\!\min_{\mathbf{x}\in \mathbb{R}^m}f(\mathbf{x})$$ and a second related problem: $$ \mathbf{y} = (y_1, y_2, \ldots, y_n) = \arg\!\min_{\mathbf{y}\in \mathbb{R}^n}g(\mathbf{y})$$ because we have the relations $$ \mathbf{x} = \mathbf{t}(\mathbf{y}) $$ and $$ f(\mathbf{t}(\mathbf{y})) = g(\mathbf{y}) $$ and $n>m$.

My question is: what is the disadvantage of solving the second problem instead of the first problem if you use a numerical optimizer?

An example: take for example a function $g(\mathbf{y})$ that only depends on $$x_1 = y_1 + y_2$$ $$x_2 = y_1+y_3$$ $$x_3 = y_1 + y_4$$ and $$x_4 =y_1+y_5$$. So minimizing $g(\mathbf{y})$ is equivalent with minimizing $$ f(\mathbf{x}) = g(0,x_1,x_2,x_3,x_4) $$

Is it harmful to solve the optimization problem the larger problem? Is it possible that a numerical optimizer has more troubles solving the larger problem, even though it doesn't matter which of all the extra solutions it gives?

edit: I use the Nelder-Mead algorithm.

update: in some cases the optimizer indicates the problem of a degenerate Nelder mead simplex . Is the root of the problem to be found in the extra variable?

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ More often than not, you want to solve the lower dimensional problem unless the larger dimensional problem is somehow simpler to solve (going from low dimensional non convex problem to high dimensional convex problem, perhaps). But the difficulty of solving depends partly on the method you use to solve it. If you use solution schemes that get hurt by the curse of dimensionality, like genetic algorithms, Particle Swarm, etc, you may want to try and solve the lower dimensional problem. $\endgroup$ – spektr Jan 23 '16 at 16:33
  • $\begingroup$ I am using the Nelder-Mead algorithm. The problem is that it would be annoying for me to adapt my current software and adapt all my optimization problems, so they have one variable less. Is it possible that an optimizer can solve the small problem, but not the larger one? $\endgroup$ – Ruben Jan 23 '16 at 16:38
  • 2
    $\begingroup$ Well I think if you have the constraint you are mentioning, you should try it with the larger problem. Given it's only one more dimension, it shouldn't be that much more difficult for the solver to solve it vs the lower dimensional variation. Also, I am not sure if one can show some optimizer can't solve a larger problem but can solve a smaller problem. I do think many approaches have a harder time solving the larger one largely because of the curse of dimensionality. It's just hard to gather enough information based on the large input space so one can solve the problem. $\endgroup$ – spektr Jan 23 '16 at 16:42
  • $\begingroup$ Ok, thank you. I can't seem to upvote your comment btw. $\endgroup$ – Ruben Jan 23 '16 at 16:58
3
$\begingroup$

Generally speaking, adding a single variable to a continuous optimization problem does not drastically decrease algorithm performance. These sorts of manipulations happen routinely to transform apparently "difficult" problems into "easy ones"; examples are things like smooth reformulations of max functions or absolute values by adding variables and constraints. Other sorts of manipulations increase sparsity, or enable more efficient algorithms to be used, and in these cases, the reformulations decrease execution time compared to solving the original formulation of the problem.

The exceptions are categories of NP-hard problems, e.g., mixed-integer (linear or nonlinear) programs, when using a global optimization algorithm. The worst-case scaling for those algorithms is exponential, so you could see, for instance, in mixed-integer problems with binary variables, a doubling of execution time when adding a binary variable. However, in working with reformulations of binary mixed-integer linear programs, I haven't seen drastic increases in solve times due to adding variables.

In the case of black-box algorithms, it would not surprise me if adding a variable or two greatly increased execution times. The problem of a degenerate Nelder-Mead simplex iteration could be a result of your reformulation by adding a variable.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Depending of your problem, adding more variables can make the problem extremely easy to solve. All will depend of the structure of your problem.

For instance, LP problems are solved using a LU decomposition of the constraint matrix. If the decomposition is easy, the problem will be fast to solve.

Example for a sum. You can have a problem where you directly have the sum with only 1s under the diagonal. If you double the size of the problem where you have the value and the sum, then you only have 2 identity matrix one next to the other assuming you compute the sum recursively.

This problem can be solve in a o(N) where the first problem will be in o(N³).

Then, in that case, having a sparse matrix, although twicce the size, will considerably reduce the overall time to solve.

| cite | improve this answer | |
$\endgroup$

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.