24
$\begingroup$

I am looking to solve a constrained optimization problem where I know the bounds on some of the variables (specifically a boxed constraint).

$$ \arg \min_u f(u,x) $$

subject to

$$ c(u,x) = 0 $$ $$ a \le d(u,x) \le b $$

where $u$ is a vector of design variables, $x$ is a vector of state variables, and $c(u,x)$ is an equality constraint (usually a PDE). The lower and upper constraints $a$ and $b$ may be spatially variable.

Which packages can handle systems of this form?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ The edited version does not look like a box-constrained optimization problem. A box-constrained optimization problem would have $a \leq u \leq b$ as a constraint. Is $u$ supposed to be a function of $x$? Is $c$ linear in $u$? If it's not, is it twice-differentiable? Is $f$ convex in $u$? Is it twice-differentiable in $u$? Finally, $\arg \min_{u}$ denotes the set of points in $u$ at which the minimum value of $f$ is attained. Do you mean $\min_{u}$ instead? $\endgroup$
    – Geoff Oxberry
    Commented Dec 31, 2011 at 5:57
  • $\begingroup$ $d(u,x) = u$ is one special case, but this more general form is actually common in practice. You can always introduce extra variables if your method can only deal with constraints directly on $u$. We are usually more interested in the value $u$ at which a minimum is attained than in the minimum value of $f$. Sean added the [pde] tag, so you may get some regularity from that. He didn't state whether the system was hyperbolic or not, so let's not assume. Let's not assume that $f$ is convex, since it is often not. $\endgroup$
    – Jed Brown
    Commented Jan 2, 2012 at 0:15
  • $\begingroup$ It's quite common for $f$ to involve $L^1$ or $W^{1,1}$ regularization, so we should not assume two derivatives. $\endgroup$
    – Jed Brown
    Commented Jan 2, 2012 at 0:15
  • $\begingroup$ @JedBrown: That makes sense; it was confusing to see "box constraint" mentioned without, well, an explicit box constraint. For the types of problems you're talking about (design problems, control problems), $u$ is definitely more interesting, but optimization problems are typically stated using the $min$ notation, and their solution sets are described using the $\arg \min$ notation. $\endgroup$
    – Geoff Oxberry
    Commented Jan 2, 2012 at 6:16
  • $\begingroup$ It may be useful to specify in what language/environment you model the PDEs. It may restrict the choice of optimizers. $\endgroup$
    – Dominique
    Commented Jan 3, 2012 at 20:35

8 Answers 8

Reset to default
19
$\begingroup$

I decided to radically edit my answer based on some of the comments.

I haven't used TAO. From perusing the documentation, it seems like the only way that TAO can handle constrained optimization problems (excluding the special case of only box constraints) is to convert the problem into a variational inequality using the Karush-Kuhn-Tucker (KKT) conditions, which are necessary under constraint qualification (the type that I usually see is the Slater point condition), and sufficient under convexity of the objective and constraints (more generally, Type 1 invexity). If $f$ is nonconvex, the variational inequality formulation using the KKT conditions is NOT equivalent to the original optimization problem, so strictly speaking, if you want a global optimum for the optimization problem, you should not express it as a variational inequality. It would be difficult to find a global optimum anyway for PDE-constrained optimization (see below), so maybe ignoring this detail is fine. Given what Wolfgang has said, I'd be skeptical of using TAO; I'm already skeptical because it doesn't implement methods for solving nonlinear programs (NLPs) as NLPs, rather than variational inequalities.

I am not an expert on PDE-constrained optimization; co-workers and associates of mine work on ODE-constrained optimization problems. I know that for intrusive formulations, Larry Biegler (and others) will use collocation methods to discretize the PDE and make it a very large, sparse NLP, and then he will solve it using interior point methods. To really solve the problem to global optimality, you would also need to generate convex relaxations, but as far as I know, this approach is not taken because PDE-constrained optimization problems lead to such large NLPs that it would be difficult to solve them to global optimality. I mention these details only because problem formulation heavily influences choice of solver package. For nonintrusive formulations, repeated PDE solves yield gradient information for optimization algorithms.

Some people who study ODE-constrained optimization problems use a similar approach of discretizing the problem using collocation and a numerical method, and then relaxing the resulting NLP to yield a convex formulation used in a global optimization algorithm. An alternate approach to ODE-constrained optimization is to relax the problem, and then discretize the ODE, which is the approach taken in my lab. It could be possible to relax certain classes of PDE-constrained optimization problems, but I don't know of any extant work done on that problem. (It was a potential project in my lab at one point.)

Ultimately, what matters is not the differentiability of the original PDE, but the differentiability of the discretization with respect to the decision variables.

If the discretized problem is twice-differentiable with respect to the decision variables, the following packages will calculate a local solution:

  • IPOPT is an open source interior point solver developed by Andreas Wächter at IBM. It's a very high quality code. As an interior-point solver, it is better for objective functions with large, sparse Jacobian matrices, and would be useful for PDE-constrained optimization
  • SNOPT is a commercial sequential quadratic programming solver that is another high quality code. It is better for objective functions with small, dense Jacobian matrices, so I would not expect it to be useful for PDE-constrained optimization, but you could give it a try.
  • NLopt is a small, open source code written by Steven Johnson at MIT that contains basic implementations of a number of nonlinear optimization algorithms. All of the algorithms should be adequate for solving bound-constrained problems.
  • fmincon in Matlab implements a number of algorithms (including interior point and sequential quadratic programming) for nonlinear optimization
  • GAMS and AMPL are both commercial modeling languages used to formulate optimization problems, and contain interfaces to a large number of nonlinear programming solvers. I know that GAMS has a trial version that can be used for smaller problems, and problem instances can also be submitted to the NEOS server for solution as well.

However, it's possible that the discretization is only once differentiable with respect to the decision variables, in which case, you should use projected steepest descent or some other first-order optimization method when calculating a local solution. Since a lot of study focuses on problems where second-order methods can be used (and when you can use them, their superior convergence properties make them a better choice), I couldn't find many implementations of steepest descent that weren't solutions to homework problems. The GNU Scientific Library has an implementation, but it's only for demonstration purposes. You would probably need to code up your own implementation.

If the problem is only continuous with respect to the decision variables, then you could use direct methods to solve it locally. There is an excellent survey on direct methods by Kolda, Lewis, and Torczon. The most widely known of these methods is the Nelder-Mead simplex algorithm. It is not guaranteed to converge to a local minimum in multiple dimensions, but it has found considerable practical use anyway.

Choice of package really depends on the language you want to use to solve the problem, if solving the bound-constrained problem is only part of an algorithm you want to implement (or if it's the only step in your algorithm, in which case modeling languages become more viable for production code), the type and size of the problem, and if you need any parallelism.

Improve this answer
$\endgroup$
4
$\begingroup$

We've tried TAO but found it to be not very useful for inequality constrained problems. It's also essentially only in maintenance mode since at least 2003, with no real new features apart from updates to track changes in PETSc upon which it is built.

Improve this answer
$\endgroup$
3
$\begingroup$

Another alternative is OPT++. It supports linear and nonlinear constraints with an efficient nonlinear interior point solver, provides control for function accuracy (if numerical differentiation is required), control for step sizes, etc. I'm typically optimizing large implicit functions (e.g. FEM) where these types of controls can be useful.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Could you elaborate on why OPT++ is a good package to use? Do you (or your colleagues) have any experience with it? $\endgroup$
    – Geoff Oxberry
    Commented Jan 6, 2012 at 7:02
  • $\begingroup$ To be clear, I have no reason to say that OPT++ is superior to any of those that you listed previously because I don't have any experience with those (though I bookmarked a few of them to check out). But I do have experience with OPT++ and have found it suitable for my needs. It supports linear and nonlinear constraints with an efficient nonlinear interior point solver, provides control for function accuracy (if numerical differentiation is required), control for step sizes, etc. I'm typically optimizing large implicit functions (e.g. FEM) where these types of controls can be useful. $\endgroup$
    – Barron
    Commented Jan 6, 2012 at 14:52
  • 2
    $\begingroup$ @Barron: you should have put that in your answer to begin with. :) $\endgroup$
    – J. M.
    Commented Jan 7, 2012 at 1:25
2
$\begingroup$

If the problem is formulated as a complementarity problem, you can use TAO (Toolkit for Advanced Optimization). Some of the methods in TAO, such as the reduced space method (a variant of the active set method), is currently available as part of SNES in PETSc (SNESVI).

Improve this answer
$\endgroup$
2
$\begingroup$

The APM MATLAB and APM Python packages can solve large-scale (100,000+ variables) of Mixed-Integer Differential Algebraic equation systems. The software is available as a web service for commercial or academic use. If you are solving a PDE system, you could discretize once to get it into DAE or ODE form to put it into APMonitor modeling language. The modeling language uses APOPT, BPOPT, IPOPT, SNOPT, and MINOS solvers.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Please disclose your affiliation as an APMonitor developer in this and future answers that mention your software. See the FAQ for details on our disclosure policy. $\endgroup$
    – Geoff Oxberry
    Commented May 9, 2013 at 18:59
  • $\begingroup$ Geoff, thanks for the tip. I started work on the APMonitor platform in 2004 as a graduate student at the University of Texas at Austin. We now use it in our research group at Brigham Young University for process control and optimization (apm.byu.edu/prism) of biological, chemical, aerospace, and other applications. I make it freely available for commercial or academic users. $\endgroup$
    – John Hedengren
    Commented May 9, 2013 at 23:20
1
$\begingroup$

The MINUTE module of CERNLIB (long since ported to ROOT) uses a transformation on the input space to render box constrains into a space where they run $[-\infty,+\infty]$ and can thus be handled without special cases (at the cost of some speed, of course).

I don't think that MINUTE will work well for your needs, but the transform may if you are forced to write some or all of the code yourself.

Improve this answer
$\endgroup$
1
  • $\begingroup$ That transformation looks nasty; no wonder it's accompanied by a couple paragraphs. $\endgroup$
    – Geoff Oxberry
    Commented Jan 12, 2012 at 7:10
1
$\begingroup$

As @Geoff Oxberry pointed out, several packages allow you to find a local solution. If you want to be able to compare these different NLP solvers for a same problem, you can use RobOptim.

Even though RobOptim was initially developed with robotics optimization problems in mind, it is suitable for any nonlinear optimization problems. It provides a simple C++ interface with plugins for multiple NLP solvers (e.g. Ipopt, NAG). If you cannot provide gradients, finite-difference computation can be done automatically.

It's open source so you can check out the source code on GitHub: https://github.com/roboptim/

Note: I am one of the developers of this project.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Should point out that other answers describe solvers, not frameworks. It is easier to find an acceptable framework (driver) than a good solver, $\endgroup$
    – Deer Hunter
    Commented Dec 13, 2013 at 11:49
  • $\begingroup$ @DeerHunter When you are looking for a solver to solve a given problem, it is often hard to know a priori which solver will compute the best solution and/or be the fastest. You are talking about a "good solver", but this really depends on what you are solving: there is not one "best overall" solver. Moreover, solver APIs are usually quite different, so using a good framework that allows you to easily switch from one solver to another can be really helpful. The question was about "software packages for constrained optimization", and frameworks also fall into this category. $\endgroup$
    – BenC
    Commented Dec 13, 2013 at 12:10
1
$\begingroup$

Here is a partial list of PDE-constrained optimization packages.

Dolfin Adjoint is part of FEniCS FEM:

http://dolfin-adjoint.org/

ROL, MOOCHO, Sundance are parts of Trilinos:

https://github.com/trilinos/trilinos/tree/master/packages/rol/

https://github.com/trilinos/trilinos/tree/master/packages/Sundance/

http://trilinos.org/packages/moocho/

PYOMO example for PDE-constrained optimization:

https://software.sandia.gov/trac/pyomo/browser/pyomo/trunk/examples/dae

TAO manual gives examples of solving PDE-constrained optimization problems:

http://www.mcs.anl.gov/petsc/petsc-3.5/docs/tao_manual.pdf

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Welcome to SciComp.SE! Just providing a link (useful as it may be) is not really a good answer; see meta.stackexchange.com/questions/8231. Could you expand on this a bit (computing language, what kind of constraints can be treated, which methods are implemented, etc.)? $\endgroup$
    – Christian Clason
    Commented Mar 6, 2014 at 19:20
  • $\begingroup$ I agree with @ChristianClason. There's been substantial development in solvers for PDE-constrained optimization software; however, this answer provides essentially no background on what algorithms those packages actually implement. $\endgroup$
    – Geoff Oxberry
    Commented Mar 16, 2015 at 5:47

Your Answer

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

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