7
$\begingroup$

I solve a nonlinear optimization problem of the form

\begin{align} &\max x_0 \text{ such that } \\ &\left[ \sum_{j=0}^N \left(\alpha_j x_0^{j} \prod_{k=3}^j x_k \right)\right]^2 + \left[ \sum_{j=1}^N \left(\beta_j x_0^{j} \prod_{k=3}^j x_k \right)\right]^2 \overset{!}{\leq} 1 \end{align}

where I know relatively tight bounds of the optimization variables $\boldsymbol x$, something between $0.1\% - 30 \%$ depending on the component. These stem from solutions for a different value of $N$. I can observe that for increasing the dimensionality $N \to N+1$, the values change only merely (this is where the bounds come from). However, the optimizer I am currently using (IpOpt) takes quite some time even for relatively small allowed deviations.

Thus my question: Is there a well-known way how to treat those long products of optimization variables, or are these just notoriously difficult problems?

I tested setting some variables as constant, but the constraint is very sensitive and even small deviations matter (this is also probably why this problem is hard). In that case, the optimization was often found infeasible.

$\endgroup$
6
  • 1
    $\begingroup$ You can try a solver implementing an active set algorithm, it should require less evaluations to converge. Thus, if it's the bottleneck, it might be faster $\endgroup$
    – fontanf
    Jun 28, 2022 at 15:52
  • $\begingroup$ Are the variables supposed to be nonnegative? $\endgroup$ Jun 29, 2022 at 10:24
  • $\begingroup$ @ErlingMOSEK This is a priori not guaranteed but in practice observed. $\endgroup$
    – Dan Doe
    Jun 29, 2022 at 10:37
  • 1
    $\begingroup$ If the variables had to be nonnegative the problem could be reformulated as a geometric programming (GP) problem I think. Such a problem is fairly easy. $\endgroup$ Jun 29, 2022 at 10:47
  • $\begingroup$ Unfortunately, the $\alpha_k, \beta_k$ are also negative and thus I am, unfortunately, not within the framework of geometric pograms - but good suggestion! $\endgroup$
    – Dan Doe
    Jun 29, 2022 at 13:54

1 Answer 1

6
$\begingroup$

You are repeating the same expressions over and over again. It may be worthwhile to see if it is better to define: $$y_j = \begin{cases}y_{j-1}\cdot x_j & \text{for $j\gt 3$}\\ x_j & \text{for $j=3$}\end{cases} $$

and then use $y_j$ in this constraint. No guarantee it is better; could well be much worse as we add variables and equations.

$\endgroup$
1
  • 1
    $\begingroup$ Good point, this is actually where I come from. In that case, however, the latter $y$ become extremely small and one runs essentially out of precision. For the presented form, all optimization variables are more or less of same precision and the problem is numerically stable, while more expensive. $\endgroup$
    – Dan Doe
    Jun 29, 2022 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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