4
$\begingroup$

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

\begin{equation} min( \sum_i d^{x_i}c_{i})\\ 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$ – Rahul 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
2
$\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
2
$\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

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.