Refine
Language
- English (5)
Has Fulltext
- yes (5)
Keywords
- Bilevel Optimization (1)
- Gas Networks (1)
- Global Optimization (1)
- Lipschitz Optimization (1)
- Mixed-Integer Nonlinear Optimization (1)
- Mixed-Integer Nonlinear Optimization, Global Optimization, Lipschitz Optimization, Gas Networks (1)
- Mixed-Integer Nonlinear Optimization, Lipschitz Optimization, Inexact Function Evaluations, Decomposition Methods, Gas Networks (1)
- dual weighted residual, hyperbolic problems, discontinuous Galerkin, artificial viscosity (1)
Many mixed-integer optimization problems are constrained by nonlinear functions that do not possess desirable analytical properties like convexity or factorability or cannot even be evaluated exactly. This is, e.g., the case for problems constrained by differential equations or for models that rely on black-box simulation runs. For these problem classes, we present, analyze, and test algorithms that solve mixed-integer problems with only Lipschitz continuous nonlinearities. Our theoretical results depend on the assumptions made on the (in)exactness of function evaluations and on the knowledge of Lipschitz constants. If Lipschitz constants are known, we prove finite termination at approximate globally optimal points both for the case of exact and inexact function evaluations. If only approximate Lipschitz constants are known, we prove finite termination and derive additional conditions under which infeasibility can be detected. A computational study for gas transport problems and an academic case study show the applicability of our algorithms to real-world problems and how different assumptions on the constraint functions up- or downgrade the practical performance of the methods.
We consider the optimal control of a nonlinear hyperbolic system of balance
laws on a one-dimensional network which arises in the context of gas transport in pipeline
systems. State constraints, which are required for the safe operation of the system, are
incorporated by a barrier method. We discuss the well-posedness of the governing system
of partial differential-algebraic equations and investigate the existence of minimizers. For
the numerical solution, we then consider the approximation of the state equation by
mixed finite elements in space and a particular linear implicit time integration scheme
that can be interpreted as a discontinuous Galerkin approximation. We establish well-
posedness of this discretization scheme and prove the existence of minimizers for the
corresponding discretized optimal control problem and discuss its numerical solution
by a projected Gauß-Newton method. The efficient realization of the Jacobian and
Hessian of the quadratic approximations that have to be minimized in every iteration
of the Gauß-Newton method can be obtained via the solution of discretized sensitivity
and adjoint equations. These are obtained by formal differentiation and transposition
of the Galerkin methods employed for the discretization of the state equations. All
approximations obtained after discretization can thus be interpreted as functions on the
continuous level and, since the functional analytic setting is not changed by the Galerkin
discretization, we observe mesh independence of the resulting fully discrete methods. For
illustration of our theoretical results and to demonstrate the efficiency of the proposed
method, we present numerical results for two test problems that model typical situations
that may arise in the daily operation of gas networks.
The Cost of Not Knowing Enough: Mixed-Integer Optimization with Implicit Lipschitz Nonlinearities
(2018)
It is folklore knowledge that nonconvex mixed-integer nonlinear optimization problems can be notoriously hard to solve in practice. In this paper we go one step further and drop analytical properties that are usually taken for granted in mixed-integer nonlinear optimization. First, we only assume Lipschitz continuity of the nonlinear functions and additionally consider multivariate implicit constraint functions that cannot be solved for any parameter analytically. For this class of mixed-integer problems we propose a novel algorithm based on an approximation of the feasible set in the domain of the nonlinear function---in contrast to an approximation of the graph of the function considered in prior work. This method is shown to compute approximate global optimal solutions in finite time and we also provide a worst-case iteration bound. In some first numerical experiments we show that the ``cost of not knowing enough'' is rather high by comparing our approach with the open-source global solver SCIP. This reveals that a lot of work is still to be done for this highly challenging class of problems and we thus finally propose some possible directions of future research.
Goal-oriented mesh adaptation, in particular using the dual-weighted residual (DWR) method, is known in many cases to produce very efficient meshes. For obtaining such meshes the (numerical) solution of an adjoint problem is needed to weight the residuals appropriately with respect to their relevance for the overall error. For hyperbolic problems already the weak primal problem requires in general an additional entropy condition to assert uniqueness of solutions; this difficulty is also reflected when considering adjoints to hyperbolic problems involving discontinuities where again an additional requirement (reversibility) is needed to select appropriate solutions. Within this article, an approach to the DWR method for hyperbolic problems based on an artificial viscosity approximation is proposed. It is discussed why the proposed method provides a well-posed dual problem, while a direct, formal, application of the dual problem does not. Moreover, we will discuss a further, novel, approach in which the forward problem need not be modified, thus allowing for an unchanged forward solution. The latter procedure introduces an additional residual term in the error estimation, accounting for the inconsistency between primal and dual problem. Finally, the effectivity of the extended error estimator, assessing the global error by a suitable functional of interest, is tested numerically; and the advantage over a formal estimator approach is demonstrated.
We present a novel method for mixed-integer optimization problems with multivariate and Lipschitz continuous nonlinearities. In particular, we do not assume that the nonlinear constraints are explicitly given but that we can only evaluate them and that we know their global Lipschitz constants. The algorithm is a successive linear relaxation method in which we alternate between solving a master problem, which is a mixed-integer linear relaxation of the original problem, and a subproblem, which is designed to tighten the linear relaxation of the next master problem by using the Lipschitz information about the respective functions. By doing so, we follow the ideas of Schmidt et al. (2018, 2021) and improve the tackling of multivariate constraints. Although multivariate nonlinearities obviously increase modeling capabilities, their incorporation also significantly increases the computational burden of the proposed algorithm. We prove the correctness of our method and also derive a worst-case iteration bound. Finally, we show the generality of the addressed problem class and the proposed method by illustrating that both bilevel optimization problems with nonconvex and quadratic lower levels as well as nonlinear and mixed-integer models of gas transport can be tackled by our method. We provide the necessary theory for both applications and briefly illustrate the outcomes of the new method when applied to these two problems.