Adjoint Sensitivity Analysis of Index-One Multistage Differential Equations

Many practical chemical engineering processes involve a sequence of distinct transient operations, forming multistage systems in which each stage is described by mixed sets of differential and algebraic equations (DAEs). These models usually involve decision variables that must be chosen so as to optimize some performance subject to operational constraints, thus leading to dynamic optimization problems, as well as parameters whose values are not known accurately. The sensitivity analysis of the solutions to these models is typically conducted via forward sensitivity analysis. However, when sensitivities with respect to a large number of variables or parameters are required, the forward sensitivity approach may become intractable, especially if the number of state variables is also large. These problems can often be handled more efficiently via adjoint sensitivity analysis. In the first part of the presentation, we propose an extension of the adjoint sensitivity approach to address index-1, multistage DAEs. We allow discontinuous junction conditions between the various stages of the system, as well as different number of equations in each stage. Moreover, we consider functionals depending not only on the differential states at stage end times, but also on the algebraic states and the differential state time derivatives. In particular, both end-point conditions and junction conditions at stage times will be discussed. Next, we consider optimization problems embedding index-1 mutistage DAEs and show how the adjoint sensitivity results can be used for the post-optimal sensitivity analysis of an optimal solution with respect to parameter variations. An important application of post-sensitivity analysis, in the field of real-time optimization, is for the development of neighboring-extremal controllers for multistage DAE systems. The proposed framework is illustrated via the numerical simulation and optimization of micro-scale chemical processes for portable power generation.

A Dual Modifier-Adaptation Approach for Real-Time Optimization

Dominique Bonvin, Benoît Chachuat, Alejandro Gabriel Marchetti

For good performance in practice, real-time optimization schemes need to be able to deal with the inevitable plant-model mismatch problem. Unlike the two-step schemes combining parameter estimation and optimization, the modifier-adaptation approach does not require the model parameters to be estimated on-line. Instead, it uses information regarding the constraints and selected gradients to improve the plant operation. The dual modifier-adaptation approach presented in this paper drives the process towards optimality, while paying attention to the accuracy of the estimated gradients. The gradients are estimated from successive operating points generated by the optimization algorithm. The novelty lies in the development of an upper bound on the norm of the gradient errors, which is used as a constraint when determining the next operating point. The proposed approach is demonstrated via numerical simulation for both an unconstrained and a constrained problem.

Elsevier2010

Approximations in Distributed Optimization

Boi Faltings, Adrian Petcu

We present in this paper an approximative method for distributed combinatorial optimization problems based on dynamic programming. The algorithm is a utility propagation method and requires a linear number of messages. The largest message is in the worst case exponential in the width of the constraint graph, in case of exact computation. However, it can be tuned with 2 parameters that allow the user to specify the desired tradeoff between solution quality and computational complexity. The second part of this paper presents an anytime version of the first algorithm, which provides increasingly accurate solutions while the propagation is still in progress, thus being suitable for very large distributed problems. Although the algorithms presented here are distributed, their reduction to the centralized case is rather straightforward.

2005

A Propagation/Local Search Hybrid for Distributed Optimization

Boi Faltings, Adrian Petcu

We present a new hybrid algorithm for local search in distributed combinatorial optimization. This method is a mix between classical local search methods in which nodes take decisions based only on local information, and full inference methods that guarantee completeness. In general, classical inference methods are time and space exponential in a parameter of the graph called the induced width, thus they may be infeasible for dense problems. On the other hand, local search methods suffer from the fact that the nodes take myopic decisions based only on local information available to them, and thus can easily get stuck in local optima. Their advantage is that they require linear memory, and in many cases provide good solutions with a small amount of effort. We propose a hybrid method that combines the advantages of both these approaches. This method is a utility propagation algorithm controlled by a parameter maxDim which specifies the maximal allowable amount of inference. The maximal space requirements are exponential in this parameter. In the dense parts of the problem, where the required amount of inference exceeds this limit, the algorithm executes a local search procedure guided by as much inference as allowed by maxDim. This hybrid can be seen as a large neighborhood search, where exponential neighborhoods are rigorously determined according to problem structure, and polynomial efforts are spent for their complete exploration at each local search step. The algorithm explores independent parts of the problem simultaneously and asynchronously, and then combines the results, all in a distributed fashion. We show the efficiency of this approach with experimental results from the distributed meeting scheduling domain.

2005