Abstract:
Making major changes in enterprise information systems, such as large IT-investments, often have a significant impact on business operations. Moreover, when deliberating which IT-changes to make, the consequences of choosing a certain scenario may be difficult to grasp. One way to ascertain the quality of IT investment decisions is through the use of methods from decision theory. This paper proposes the use of one such method to facilitate IT-investment decision making, viz. extended influence diagrams. An extended influence diagram is a tool able to completely describe and analyse a decision situation. The applicability of extended influence diagrams is demonstrated at the end of the paper by using an extended influence diagram in combination with the ISO/IEC 9126 software quality characteristics and metrics as means to assist a decision maker in a decision regarding an IT-investment.

Abstract:
Recently an analytical model was presented that treats the nonlinear signal distortion from the Kerr nonlinearity in optical transmission systems as additive white Gaussian noise. This important model predicts the impact of the Kerr nonlinearity in systems operating at a high symbol rate and where the accumulated dispersion at the receiver is large. Starting from the suggested model for the propagating signal, we here give an independent and different calculation of the main result. The analysis is based on the Manakov equation with attenuation included and a complete and detailed derivation is given using a perturbation analysis. As in the case with the published model, in addition to assuming that the input signal can be written on a specific form, two further assumptions are necessary; the nonlinearity is weak and the signal-noise interaction is neglected. The result is then found without any further approximations.

Abstract:
Using T=0 Monte Carlo and simulated annealing simulation, we study the energy relaxation of ferromagnetic Ising and Potts models on random graphs. In addition to the expected exponential decay to a zero energy ground state, a range of connectivities for which there is power law relaxation and freezing to a metastable state is found. For some connectivities this freezing persists even using simulated annealing to find the ground state. The freezing is caused by dynamic frustration in the graphs, and is a feature of the local search-nature of the Monte Carlo dynamics used. The implications of the freezing on agent-based complex systems models are briefly considered.

Abstract:
In dual decomposition, the dual to an optimization problem with a specific structure is solved in distributed fashion using (sub)gradient and recently also fast gradient methods. The traditional dual decomposition suffers from two main short-comings. The first is that the convergence is often slow, although fast gradient methods have significantly improved the situation. The second is that computation of the optimal step-size requires centralized computations, which hinders a fully distributed implementation of the algorithm. In this paper, the first issue is addressed by providing a tighter characterization of the dual function than what has previously been reported in the literature. Then a distributed and a parallel algorithm are presented in which the provided dual function approximation is minimized in each step. Since the approximation is more accurate than the approximation used in standard and fast dual decomposition, the convergence properties are improved. For the second issue, we extend a recent result to allow for a fully distributed parameter selection in the algorithm. Further, we show how to apply the proposed algorithms to optimization problems arising in distributed model predictive control (DMPC) and show that the proposed distributed algorithm enjoys distributed reconfiguration, i.e. plug-and-play, in the DMPC context.

Abstract:
Recently, several authors have suggested the use of first order methods, such as fast dual ascent and the alternating direction method of multipliers, for embedded model predictive control. The main reason is that they can be implemented using simple arithmetic operations only. However, a known limitation of gradient-based methods is that they are sensitive to ill-conditioning of the problem data. In this paper, we present a fast dual gradient method for which the sensitivity to ill-conditioning is greatly reduced. This is achieved by approximating the negative dual function with a quadratic upper bound with different curvature in different directions in the algorithm, as opposed to having the same curvature in all directions as in standard fast gradient methods. The main contribution of this paper is a characterization of the set of matrices that can be used to form such a quadratic upper bound to the negative dual function. We also describe how to choose a matrix from this set to get an improved approximation of the dual function, especially if it is ill-conditioned, compared to the approximation used in standard fast dual gradient methods. This can give a significantly improved performance as illustrated by a numerical evaluation on an ill-conditioned AFTI-16 aircraft model.

Abstract:
Douglas-Rachford splitting and the alternating direction method of multipliers (ADMM) can be used to solve convex optimization problems that consist of a sum of two functions. Convergence rate estimates for these algorithms have received much attention lately. In particular, linear convergence rates have been shown by several authors under various assumptions. One such set of assumptions is strong convexity and smoothness of one of the functions in the minimization problem. The authors recently provided a linear convergence rate bound for such problems. In this paper, we show that this rate bound is tight for many algorithm parameter choices.

Abstract:
Douglas-Rachford splitting is an algorithm that solves composite monotone inclusion problems, in which composite convex optimization problems is a subclass. Recently, several authors have shown local and global convergence rate bounds for Douglas-Rachford splitting and the alternating direction method of multipliers (ADMM) (which is Douglas-Rachford splitting applied to the dual problem). In this paper, we show global convergence rate bounds under various assumptions on the problem data. The presented bounds improve and/or generalize previous results from the literature. We also provide examples that show that the provided bounds are indeed tight for the different classes of problems under consideration for many algorithm parameters.

Abstract:
In this note, we present results for the colouring problem on small world graphs created by rewiring square, triangular, and two kinds of cubic (with coordination numbers 5 and 6) lattices. As the rewiring parameter p tends to 1, we find the expected crossover to the behaviour of random graphs with corresponding connectivity. However, for the cubic lattices there is a region near p=0 for which the graphs are colourable. This could in principle be used as an additional heuristic for solving real world colouring or scheduling problems. Small worlds with connectivity 5 and p ~ 0.1 provide an interesting ensemble of graphs whose colourability is hard to determine. For square lattices, we get good data collapse plotting the fraction of colourable graphs against the rescaled parameter parameter $p N^{-\nu}$ with $\nu = 1.35$. No such collapse can be obtained for the data from lattices with coordination number 5 or 6.

Abstract:
We describe the recently introduced extremal optimization algorithm and apply it to target detection and association problems arising in pre-processing for multi-target tracking. Here we consider the problem of pre-processing for multiple target tracking when the number of sensor reports received is very large and arrives in large bursts. In this case, it is sometimes necessary to pre-process reports before sending them to tracking modules in the fusion system. The pre-processing step associates reports to known tracks (or initializes new tracks for reports on objects that have not been seen before). It could also be used as a pre-process step before clustering, e.g., in order to test how many clusters to use. The pre-processing is done by solving an approximate version of the original problem. In this approximation, not all pair-wise conflicts are calculated. The approximation relies on knowing how many such pair-wise conflicts that are necessary to compute. To determine this, results on phase-transitions occurring when coloring (or clustering) large random instances of a particular graph ensemble are used.