Scalable Dynamic Optimization back

Motivation:

This project develops scalable algorithms and supporting convergence theory for large-scale nonlnear optimization problems motivated by real-time dynamic optimization.
Real-time dynamic optimization involves the solution of parametric optimization problems in which the problem data is driven by a dynamic system that we seek to control or drive towards an optimal manifold. Applications include predictive control and state estimation (data assimilation). A key issue arising in this framework and that limits the use of off-the-shelf solvers is computational latency: if the optimization problem cannot be solved at a frequency comparable to the system dynamics, the system will destabilize. We investigate approaches that have the potential of achieving manifold tracking stability in O(n) operations and thus support model updates in the minimum possible time. For such approaches, given enough computational resources to reduce the compute time below the update time, tracking stability will be achieved. A particular emphasis is on DO problems arising from NMPC and data assimilation of real-time operations of energy systems, such as the power grid, power plants, and environmental applications, which poses stringent constraints on the time to solution.

To give an order of magnitude estimate of the complexity of instances of problems of interest, the power grid of the Midwest region includes 10,000 transmission nodes, 1,000 generation nodes, and 5,000 demand nodes. Such complexity can easily generate dynamic optimization problems with more than one million state and control variables. Another large-scale application is the one of large-scale coordinated HVAC (heating, ventilation, and air conditioning) building control in urban systems, currently contemplated in many major US cities.

Research:

Sponsored by the Department of Energy (DOE) Office of Science, we have been using generalized equation theory, we have derived conditions under which a single sequential-quadratic-programming (SQP) can achieve stable tracking of the optimal manifold (see Figure 1). We demonstrated that the manifold tracking error can be made of second order with respect to the time step even if the active-set changes in time and even if the SQP iteration is performed inexactly. This result was later generalized by Dontchev and Rockafellar in which again, using generalized equation theory,  they show that a corrector SQP step can further reduce the tracking error to fourth order with respect to the time step.

We have also developed an augmented lagrangian (AL) scheme coupled to a projected Gauss-Seidel strategy (see Figure 2) to enable inexact SQP iterates and fast detection of activity. The strategy works well in practice but the AL regularization degrades the tracking error to first order. These results motivated further work in NLP algorithms.  We have developed an exact differentiable penalty framework, which has many interesting properties of interest in large-scale parametric optimization. We believe that this work has huge implications to the NLP field as it enables fast detection of activity, warm-starts, inertia detection, and the use of iterative linear algebra. In addition, we have shown that the exact penalty can detect minima of the optimization problem without introducing of spurious points.  We are currently investigation approaches to deal with ill-conditionning induced by the penalty function.

Collaborators
  • Mihai Anitescu [link]

Publications

  1. Zavala, V. M. and Anitescu, M. Scalable Nonlinear Programming Via Exact Differentiable Penalty Functions and Trust-Region Newton Methods.  Under Review, 2013. [pdf]
  2. Zavala, V. M.; and Anitescu, M. Real-Time Nonlinear Optimization as a Generalized Equation.  SIAM J. Control and Optimization, 48, pp. 5444-5454, 2010. [pdf]
  3. Robbins, B.; and Zavala, V.M. Convergence Analysis of a Parallel Newton Scheme for Dynamic Power Grid Simulations. International Workshop on High Performance Computing, Networking and Analytics for the Power Grid, 2011. [pdf]
  4. Zavala, V. M.;  and Anitescu, M.  Achieving Higher Frequencies in Large-Scale Nonlinear Model Predictive Control. IEEE CDC, 2010. [pdf]





Figure 1. Stable Manifold Solution Tracking Using Exact Penalty Function



Figure 2. Fast Active-Set Detection Using Projected Gauss-Seidel for Different Problems