Refine
Year of publication
Language
- English (1103) (remove)
Keywords
- optimal control (27)
- stability (14)
- integer programming (11)
- Stochastic programming (9)
- finite elements (9)
- mixed integer programming (9)
- Hamiltonian matrix (8)
- finite element method (8)
- model reduction (8)
- state constraints (8)
We consider the design of a passive optical telecommunication access network, where clients have to be connected to an intermediate level of distribution points (DPs) and further on to some central offices (COs) in a tree-like fashion. Each client demands a given number of fiber connections to its CO. Passive optical splitters installed at the DPs allow k connections to share a single common fiber between the DP and the CO. We consider fixed charge costs for the use of an edge of the underlying street network, of a DP, and of a CO and variable costs for installing fibers along the street edges and for installing splitters at the DPs. We present two Lagrangian decomposition approaches that decompose the problem based on the network structure and on the cost structure, respectively. The subproblems are solved using MIP techniques. We report computational results for realistic instances and compare the efficiency of the Lagrangian approaches to the solutions of an integrated MIP model.
Motivation. Modelling, parameter identification, and simulation play an important role in systems biology. Usually, the goal is to determine parameter values that minimise the difference between experimental measurement values and model predictions in a least-squares sense. Large-scale biological networks, however, often suffer from missing data for parameter identification. Thus, the least-squares problems are rank-deficient and solutions are not unique. Many common optimisation methods ignore this detail because they do not take into account the structure of the underlying inverse problem. These algorithms simply return a “solution” without additional information on identifiability or uniqueness. This can yield misleading results, especially if parameters are co-regulated and data are noisy.
Results. The Gauss-Newton method presented in this paper monitors the numerical rank of the Jacobian and converges locally, for the class of adequate problems, to a solution that is unique within the subspace of identifiable parameters. This method has been implemented in BioPARKIN, a software package that combines state-of-the-art numerical algorithms with compliance to system biology standards, most importantly SBML, and an accessible interface.
Availability. The software package BioPARKIN is available for download at http://bioparkin.zib.de .
A basic task in signal analysis is to character-
ize data in a meaningful way for analysis and classification
purposes. Time-frequency transforms are powerful strategies
for signal decomposition, and important recent generalizations
have been achieved in the setting of frame theory. In parallel
recent developments, tools from algebraic topology, traditionally
developed in purely abstract settings, have provided new insights
in applications to data analysis. In this report, we investigate some
interactions of these tools, both theoretically and with numerical
experiments, in order to characterize signals and their frame
transforms. We explain basic concepts in persistent homology
as an important new subfield of computational topology, as well
as formulations of time-frequency analysis in frame theory. Our
objective is to use persistent homology for constructing topo-
logical signatures of signals in the context of frame theory. The
motivation is to design new classification and analysis methods by
combining the strength of frame theory as a fundamental signal
processing methodology, with persistent homology as a new tool
in data analysis.
We derive a formula for the backward error of a complex number $\lambda$ when considered as an approximate eigenvalue
of a Hermitian matrix pencil or polynomial with respect to Hermitian perturbations. The same are also obtained for approximate
eigenvalues of matrix pencils and polynomials with related structures like skew-Hermitian, $*$-even and $*$-odd.
Numerical experiments suggest that in many cases there is a significant difference between the backward
errors with respect to perturbations that preserve structure and those with respect to arbitrary perturbations.
An existence result is proved for a nonlinear diffusion problem of phase-field type, consisting of a parabolic system of two partial differential equations, complemented by Neumann homogeneous boundary conditions and initial
conditions. This system is meant to model two-species phase segregation on an atomic lattice under the presence of diffusion. A similar system has been recently
introduced and analyzed in [3]. Both systems conform to the general theory developed in [5]: two parabolic PDEs, interpreted as balances of microforces and microenergy,
are to be solved for the order parameter rho and the chemical potential mu. In the system studied in this note, a phase-field equation in rho fairly more general than in [3] is coupled with a highly nonlinear diffusion equation for mu, in which the conductivity coefficient is allowed to depend nonlinearly on both variables.
Global existence and uniqueness for a singular/degenerate Cahn-Hilliard system with viscosity
(2013)
Existence and uniqueness are investigated for a nonlinear diffusion problem of phase-field type, consisting of a parabolic system of two partial differential equations, complemented by Neumann homogeneous boundary conditions and initial conditions. This system aims to model two-species phase segregation on an atomic lattice [19]; in the balance equations of microforces and microenergy, the two
unknowns are the order parameter rho and the chemical potential mu. A simpler version of the same system has recently been discussed in [8]. In this paper, a fairly more general phase-field equation for rho is coupled with a genuinely nonlinear diffusion equation for mu. The existence of a global-in-time solution is proved with the help of suitable a priori estimates. In the case of constant atom mobility, a new and rather unusual uniqueness
proof is given, based on a suitable combination of variables.
We are concerned with a nonstandard phase field model of
Cahn-Hilliard type. The model, which was introduced by Podio-Guidugli (Ric. Mat. 2006), describes two-species phase segregation and consists of a system of two highly nonlinearly coupled PDEs. It has been recently investigated
by Colli, Gilardi, Podio-Guidugli, and Sprekels in a series of papers: see, in particular, SIAM J. Appl. Math. 2011,
and Boll. Unione Mat. Ital. 2012. In the latter contribution, the authors can treat the very general case in which the diffusivity coefficient of the parabolic PDE
is allowed to depend nonlinearly on both variables. In the same framework, this paper investigates the asymptotic limit of the solutions to the initial-boundary value problems as the diffusion coefficient sigma in the equation governing the evolution of the order parameter tends to zero. We prove that such a limit actually exists and solves the limit problem, which couples a nonlinear PDE of parabolic type with an ODE accounting for the phase dynamics. In the case of a constant diffusivity, we are able to show uniqueness and to improve the regularity of the solution.
The present note deals with a nonstandard systems of differential equations describing a two-species phase segregation. This system naturally arises in the asymptotic analysis carried out recently by the same authors,
as the diffusion coefficient in the equation governing
the evolution of the order parameter tends to zero. In particular, an existence result has been proved for the limit system in a very general framework. On the contrary, uniqueness was shown by assuming a constant mobility coefficient. Here, we generalize this result and prove
a continuous dependence property in the case that the mobility coefficient suitably depends on the chemical potential.
In this paper we propose a time discretization of a system of two parabolic equations describing diffusion-driven atom rearrangement in crystalline matter. The equations express the balances of microforces and microenergy; the two phase fields are the order parameter and the chemical potential. The initial and boundary-value problem for the evolutionary system is known to be well posed. Convergence of the discrete scheme to the solution of the continuous problem is proved by a careful development of uniform estimates, by weak compactness and a suitable treatment of
nonlinearities. Moreover, for the difference of discrete
and continuous solutions we prove an error estimate of
order one with respect to the time step.
We study the incremental facility location problem, wherein we are given an instance of the uncapacitated facility location problem. We seek an incremental sequence of opening facilities and an incremental sequence of serving customers along with their fixed assignments to facilities open in the partial sequence. Our aim is to have the solution obtained for serving the first l customers in the sequence be competitive with the optimal solution to serve any l customers. We provide an incremental framework that provides an overall competitive factor of 8 and a worst case instance that provides the lower bound of 3. The problem has applications in multi-stage network planning.
We consider a generalized version of the rooted connected facility location problem which occurs in planning of telecommunication networks with both survivability and hop-length constraints. Given a set of client nodes, a set of potential facility nodes including one predetermined root facility, a set of optional Steiner nodes, and the set of the potential connections among these nodes, that task is to decide which facilities to open, how to assign the clients to the open facilities, and how to interconnect the open facilities in such a way, that the resulting network contains at least edge-disjoint paths, each containing at most H edges, between the root and each open facility and that the total cost for opening facilities and installing connections is minimal. We study two IP models for this problem and present a branch-and-cut algorithm based on Benders decomposition for nding its solution. Finally, we report computational results.
In the connected facility location problem with buy-at-bulk edge costs we are given a set of clients with positive demands and a set of potential facilities with opening costs in an undirected graph with edge lengths obeying the triangle inequality. Moreover, we are given a set of access cable types, each with a cost per unit length and a capacity such that the cost per capacity decreases from small to large cables, and a core cable type of innite capacity. The task is to open some facilities and to connect them by a Steiner tree using core cables, and to build a forest network using access cables such that the edge capacities suce to simultaneously route all client demands unsplit to the open facilities. The objective is to minimize the total cost of opening facilities, building the core Steiner tree, and installing the access cables. In this paper, we devise a constant-factor approximation algorithm for this problem based on a random sampling technique.
We consider a generalization of the connected facility location problem where the clients must be connected to the open facilities via shared capacitated (tree) networks instead of independent shortest paths. This problem arises in the planning of ber optic telecommunication access networks, for example. Given a set of clients with positive demands, a set of potential facilities with opening costs, a set of capacitated access cable types, and a core cable type of innite capacity, one has to decide which facilities to open, how to interconnect them using a Steiner tree of innite capacity core cables, and which access cable types to install on which potential edges such that these edges form a forest and the installed capacities suce to simultaneously route the client demands to the open facilities via single paths. The objective is to minimize the total cost of opening facilities, building the core Steiner tree among them, and installing the access cables. In this paper, we devise a constant-factor approximation algorithm for problem instances where the access cable types obey economies of scale. In the special case where only multiples of a single cable type can be installed on the access edges, a variant of our algorithm achieves a performance guarantee of 6.72.
This paper presents efficient computational techniques for solving an optimization problem in cardiac defibrillation governed by the monodomain equations. Time-dependent electrical currents injected at different spatial positions act as the control. Inexact Newton-CG methods are used, with reduced gradient computation by adjoint solves. In order to reduce the computational complexity, adaptive mesh refinement for state and adjoint equations is performed. To reduce the high storage and bandwidth demand imposed by adjoint gradient and Hessian-vector evaluations, a lossy compression technique for storing trajectory data is applied. An adaptive choice of quantization tolerance based on error estimates is developed in order to ensure convergence. The efficiency of the proposed approach is demonstrated on numerical examples.
In this paper a condition number for linear-quadratic two-stage stochastic optimization problems is introduced as the Lipschitz modulus of the multifunction assigning to a (discrete) probability distribution the solution set of the problem. Being the outer norm of the Mordukhovich coderivative of this multifunction, the condition number can be estimated from above explicitly in terms of the problem data by applying appropriate calculus rules. Here, a chain rule for the extended partial second-order subdifferential recently proved by Mordukhovich and Rockafellar plays a crucial role. The obtained results are illustrated for the example of two-stage stochastic optimization problems with simple recourse.
The chemical master equation is a fundamental equation in chemical kinetics. It is an adequate substitute for the classical reaction-rate equations whenever stochastic effects become relevant. In the present paper we give a simple argument showing that the solutions of a large class of chemical master equations, including all those in which elementary reactions between two and more molecules do not generate a larger number of molecules than existed before,
are bounded in weighted $\ell_1$-spaces. As an illustration for the implications of this kind of regularity we analyze the effect of truncating the state space. This leads to an error analysis of the finite state projection of the chemical master equation, an approximation that underlies many numerical methods.
A mixed-integer stochastic nonlinear optimization problem with joint probabilistic constraints
(2013)
We illustrate the solution of a mixed-integer stochastic nonlinear optimization problem in an application of power management. In this application, a coupled system consisting of a hydro power station and a wind farm is considered. The objective is to satisfy the local energy demand and sell any surplus energy on a spot market for a short time horizon. Generation of wind energy is assumed to be random, so that demand satisfaction is modeled by a joint probabilistic constraint taking into account the multivariate distribution. The turbine is forced to either operate between given positive limits or to be shut down. This introduces additional binary decisions. The numerical solution procedure is presented and results are illustrated.
We present new residual estimates based on Kato's square root theorem for spectral approximations of diagonalizable non-self-adjoint differential operators of convection-diffusion-reaction type. These estimates are incorporated as part of an hp-adaptive finite element algorithm for practical spectral computations, where it is shown that the
resulting a posteriori error estimates are reliable. Provided experiments demonstrate the efficiency and reliability of our approach.
The huge number of elementary flux modes (EFM) in genome-scale metabolic networks makes analysis based on elementary flux modes intrinsically difficult. However, it has been shown that the elementary flux modes with optimal yield often contain highly redundant information. The set of optimal-yield elementary flux modes can be compressed using modules. Up to now, this compression was only possible by first enumerating the whole set of all optimal-yield elementary flux modes.
We present a direct method for computing modules of the thermodynamically constrained optimal flux space of a metabolic network. This method can be used to decompose the set of optimal-yield elementary flux modes in a modular way and to speed up their computation. In addition, it provides a new form of coupling information that is not obtained by classical flux coupling analysis. We illustrate our approach on a set of model organisms.
Constraint-based analysis of metabolic networks has become a widely used approach in computational systems biology.
In the simplest form, a metabolic network is represented by a stoichiometric matrix and thermodynamic information on the irreversibility of certain reactions.
Then one studies the set of all steady-state flux vectors satisfying these stoichiometric and thermodynamic constraints.
We introduce a new lattice-theoretic framework for the computational analysis of metabolic networks, which focuses on the support of the flux vectors,
i.e., we consider only the qualitative information whether or not a certain reaction is active, but not its specific flux rate.
Our lattice-theoretic view includes classical metabolic pathway analysis as a special case, but turns out to be much more flexible and general,
with a wide range of possible applications.
We show how important concepts from metabolic pathway analysis, such as blocked reactions, flux coupling, or elementary modes, can be generalized to arbitrary lattice-based models. We develop corresponding general algorithms and present a number of computational results.