George B. Dantzig and systems optimization

We pay homage to George B. Dantzig by describing a less well-known part of his legacy–his early and dedicated championship of the importance of systems optimization in solving complex real-world problems.     

The application of automated reasoning to formal models of combinatorial optimization

Many formalisms have been proposed over the years to capture combinatorial optimization algorithms such as dynamic programming, branch and bound, and greedy. In 1989 Helman [9] presented a common formalism that captures dynamic programming and branch and bound type algorithms. The formalism was later extended to include greedy algorithms. In this paper, we describe the application of automated reasoning techniques to the domain of our model, in particular considering some representational issues and demonstrating that proofs about the model can be obtained by an automated reasoning program. The long-term objective of this research is to develop a methodology for using automated reasoning to establish new results within the theory, including the derivation of new lower bounds and the discovery (and verification) of new combinatorial search strategies.     

Conjugate Gradient Methods with Armijo-type Line Searches

Abstract Two Armijo-type line searches are proposed in this paper for nonlinear conjugate gradient methods.Under these line searches, global convergence results are established for several famous conjugate gradientmethods, including the Fletcher-Reeves method, the Polak-Ribiere-Polyak method, and the conjugate descentmethod.     

Market Power Issues in Bid-Based Hydrothermal Dispatch

The objective of this work is to investigate market power issues in bid-based hydrothermal scheduling. Initially, market power was simulated with a single stage Cournot–Nash equilibrium model. In this static model the equilibrium was calculated analytically. It was shown that the total production of N strategic agents is smaller than the least-cost solution by a factor of (N/(N+1)). Market power analysis for multiple stages was then carried through a stochastic dynamic programming scheme, where the decision in each stage and state is the Cournot–Nash equilibrium of a multi-agent game. Case studies with data taken from the Brazilian system are presented.     

On the Finite-Time Dynamics of Ant Colony Optimization

An analytical framework for investigating the finite-time dynamics of ant colony optimization (ACO) under a fitness-proportional pheromone update rule on arbitrary construction graphs is developed. A limit theorem on the approximation of the stochastic ACO process by a deterministic process is demonstrated, and a system of ordinary differential equations governing the process dynamics is identified. As an example for the application of the presented theory, the behavior of ACO on three different construction graphs for subset selection problems is analyzed and compared for some basic test functions. The theory enables first rough theoretical predictions of the convergence speed of ACO. AMS 2000 Subject classification 68W20, 68W40     

Development and Evaluation of Decision-Making Model for Stock Markets

The paper introduces an intelligent decision-making model which is based on the application of artificial neural networks (ANN) and swarm intelligence technologies. The proposed model is used to generate one-step forward investment decisions for stock markets. The ANN are used to make the analysis of daily stock returns and to calculate one day forward decision for purchase of the stocks. Subsequently the Particle Swarm Optimization (PSO) algorithm is applied in order to select the “the best” ANN for the future investment decisions and to adapt the weights of other networks towards the weights of the best network. The experimental investigations were made considering different forms of decision-making model: different number of ANN, ANN inputs, sliding windows, and commission fees. The paper introduces the decision-making model, its evaluation results and discusses its application possibilities.     

Liberating the Subgradient Optimality Conditions from Constraint Qualifications

In convex optimization the significance of constraint qualifications is evidenced by the simple duality theory, and the elegant subgradient optimality conditions which completely characterize a minimizer. However, the constraint qualifications do not always hold even for finite dimensional optimization problems and frequently fail for infinite dimensional problems. In the present work we take a broader view of the subgradient optimality conditions by allowing them to depend on a sequence of ε-subgradients at a minimizer and then by letting them to hold in the limit. Liberating the optimality conditions in this way permits us to obtain a complete characterization of optimality without a constraint qualification. As an easy consequence of these results we obtain optimality conditions for conic convex optimization problems without a constraint qualification. We derive these conditions by applying a powerful combination of conjugate analysis and ε-subdifferential calculus. Numerical examples are discussed to illustrate the significance of the sequential conditions.     

Global Optimization using a Dynamical Systems Approach

We develop new algorithms for global optimization by combining well known branch and bound methods with multilevel subdivision techniques for the computation of invariant sets of dynamical systems. The basic idea is to view iteration schemes for local optimization problems – e.g. Newton’s method or conjugate gradient methods – as dynamical systems and to compute set coverings of their fixed points. The combination with bounding techniques allow for the computation of coverings of the global optima only. We show convergence of the new algorithms and present a particular implementation. Michael Dellnitz - Research of the authors is partially supported by the Deutsche Forschungsgemeinschaft within the Sonderforschungsbereich 376     

On Finite Element Approximations to a Shape Gradient Flow in Shape Optimization of Elliptic Problems

Shape gradient flows are widely used in numerical shape optimization algorithms. We investigate the accuracy and effectiveness of approximate shape gradients flows for shape optimization of elliptic problems. We present convergence analysis with a priori error estimates for finite element approximations of shape gradient flows associated with a distributed or boundary expression of Eulerian derivative. Numerical examples are presented to verify theory and show that using the volume expression is effective for shape optimization with Dirichlet and Neumann boundary conditions.     

On mixed finite element approximations of shape gradients in shape optimization with the Navier–Stokes equation

For shape optimization of fluid flows governed by the Navier–Stokes equation, we investigate effectiveness of shape gradient algorithms by analyzing convergence and accuracy of mixed finite element approximations to both the distributed and boundary types of shape gradients. We present convergence analysis with a priori error estimates for the two approximate shape gradients. The theoretical analysis shows that the distributed formulation has superconvergence property. Numerical results with comparisons are presented to verify theory and show that the shape gradient algorithm based on the distributed formulation is highly effective and robust for shape optimization.