6
$\begingroup$

I want to solve a nonlinear optimization problem of the following form

\begin{equation} \min\left(\sum_i d^{x_i}c_{i}\right)\\ 0 \leq x_{i} \leq a\\ \sum_{i} x_{i} \leq b \end{equation}

$a$, $b$, $0.95 < d < 1$ and $c_i > 1$ are constant. The problem has a very specific structure, and my question is whether using a very general nonlinear optimization software (e.g. NLopt, Ipopt) is the best way to solve it numerically. The second issue is that the number of variables ($x_i$) is very large (around one million). Does the standard algorithms for nonlinear optimization can handle this large number of variables?

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ That's a bad nonlinearity. Do you have an estimate of the value of $a$? $\endgroup$ – Wolfgang Bangerth Dec 15 '14 at 14:39
  • $\begingroup$ Why is this kind of nonlinearity bad? $a$ is somewhere between 100 and 200. $\endgroup$ – Thomas W. Dec 15 '14 at 17:17
  • $\begingroup$ What are the signs of the $c_i$? Are they all positive, all negative, or mixed? $\endgroup$ – user3883 Dec 15 '14 at 19:16
  • $\begingroup$ @ThomasW.:The nonlinearity you have looks like a sum of exponentials. For the sake of argument, $e^{200}$ is roughly something like $10^{86}$; such a large range of scales could cause conditioning issues. The constraints you have are linear, which is good. It's really just the objective function that's problematic, and the large number of variables. $\endgroup$ – Geoff Oxberry Dec 15 '14 at 19:36
  • $\begingroup$ @Rahul: $c_i > 0$ $\endgroup$ – Thomas W. Dec 16 '14 at 5:35
3
$\begingroup$

At 1 million variables, you're sort of on the cusp of what a code like (the publicly released version of) IPOPT can do. IPOPT will solve the KKT system derived from an interior point method using direct methods (usually, it's an $LDL^{T}$ factorization using something like Bunch-Parlett). Memory is typically the limiting resource in these algorithms for large-scale problems. I doubt NLopt would be better; interior-point methods are supposed to be good for large-scale problems, and SQP algorithms (such as SLSQP in NLopt) are not supposed to perform as well. Method-of-moving-asymptote methods have been used in topology optimization and are supposed to be geared towards solving large-scale problems, but I don't have much experience with those methods.

Of greater concern might be scaling; even $(1.05)^{200} \approx 10^{10}$. It's something to look out for, and not necessarily a show-stopper.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I've implemented the equation with Ipopt. It solved the system with 763,435 unknowns in around 25 minutes on an quite old notebook. $\endgroup$ – Thomas W. Dec 18 '14 at 19:50
1
$\begingroup$

An important issue here is whether this is a convex optimization problem or not.

Your objective function is a weighted sum-exp function (since $d$ and the $c_{i}$ are fixed, you can use the change of base formula for logs to write this as $\sum \hat{c}_{i} \exp(x_{i})$. Assuming that the $\hat{c}_{i}$ are nonnegative, you've got a convex $f(x)$. Unfortunately, you're trying to maximize, which is the wrong direction. If by some chance all of your $c_{i}$ coefficients were negative, then you'd be maximizing a concave function which is a good case. If the $c_{i}$ coefficients have mixed signs you're generally going to have a nonconvex objective function.

Research has been done on the related problem of minimizing convex log-sum-exp functions (note that $\log$ is a monotone transformation of your objective function) which might prove helpful if your optimization problem is indeed convex. Even simpler would be to use a projected gradient method.

On the other hand, if your problem is non-convex, then you're in a world of hurt.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ups, I made an failure in the equation, it should be a minimization of the sum. I already corrected it in the question above. You mentioned some research about minimization of convex log-sum-exp functions. Do you know some details? $\endgroup$ – Thomas W. Dec 16 '14 at 5:34
0
$\begingroup$

[ I hope you solved the problem since you posted it. Or that you graduated since then. :) ]

This looks a lot like one of the these problems to reason about rather than to explicitly solve.

For $d \simeq 1$ (which is what one of the constraints seem to imply), $d^x \simeq 1 + x(d-1)$

Therefore the minimization problem is roughly equivalent to

\begin{equation} \min\left( \sum_i x_i (d-1) c_{i}\right) \\ 0 \leq x_{i} \leq a\\ \sum_{i} x_{i} \leq b \end{equation}

since $d - 1 < 0$ this is equivalent to maximize

\begin{equation} \max\left( \sum_i x_i c_{i}\right)\\ 0 \leq x_{i} \leq a\\ \sum_{i} x_{i} \leq b \end{equation}

I am not an expert in the subject but this looks like one of these linear programming problems which I believe have efficient computational solutions.

As a matter of fact the extrema of this function cannot exist in an interior point of the domain, so one can only check at the "boundaries" of the constraints. Maybe this is a property of the original problem as well.

It is also likely that the series expansion that I described above not only is an approximation but also a bound to the minimizing function, in which case it can allow obtain upper bound to the minimum value.

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

This looks like smoothing/unsmoothing techniques can be used to say something theoretically before throwing it into a computer: what happens if you replace two unknowns $(x_i, x_j)$ with $(x_i+\varepsilon, x_j - \varepsilon)$?

Can you prove that some of these variables must be $0$ or $a$, or that they must be equal one to another or have a specific ratio? In other words: can you get conditions by solving the subproblem restricted to two variables?

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