Displaying 61 – 80 of 124

Showing per page

Greedy algorithms for optimal computing of matrix chain products involving square dense and triangular matrices

Faouzi Ben Charrada, Sana Ezouaoui, Zaher Mahjoub (2011)

RAIRO - Operations Research - Recherche Opérationnelle

This paper addresses a combinatorial optimization problem (COP), namely a variant of the (standard) matrix chain product (MCP) problem where the matrices are square and either dense (i.e. full) or lower/upper triangular. Given a matrix chain of length n, we first present a dynamic programming algorithm (DPA) adapted from the well known standard algorithm and having the same O(n3) complexity. We then design and analyse two optimal O(n) greedy algorithms leading in general to different optimal solutions...

Greedy algorithms for optimal computing of matrix chain products involving square dense and triangular matrices

Faouzi Ben Charrada, Sana Ezouaoui, Zaher Mahjoub (2011)

RAIRO - Operations Research

This paper addresses a combinatorial optimization problem (COP), namely a variant of the (standard) matrix chain product (MCP) problem where the matrices are square and either dense (i.e. full) or lower/upper triangular. Given a matrix chain of length n, we first present a dynamic programming algorithm (DPA) adapted from the well known standard algorithm and having the same O(n3) complexity. We then design and analyse two optimal O(n) greedy algorithms leading in general to different optimal solutions...

Growth rates and average optimality in risk-sensitive Markov decision chains

Karel Sladký (2008)

Kybernetika

In this note we focus attention on characterizations of policies maximizing growth rate of expected utility, along with average of the associated certainty equivalent, in risk-sensitive Markov decision chains with finite state and action spaces. In contrast to the existing literature the problem is handled by methods of stochastic dynamic programming on condition that the transition probabilities are replaced by general nonnegative matrices. Using the block-triangular decomposition of a collection...

High-performance simulation-based algorithms for an alpine ski racer's trajectory optimization in heterogeneous computer systems

Roman Dębski (2014)

International Journal of Applied Mathematics and Computer Science

Effective, simulation-based trajectory optimization algorithms adapted to heterogeneous computers are studied with reference to the problem taken from alpine ski racing (the presented solution is probably the most general one published so far). The key idea behind these algorithms is to use a grid-based discretization scheme to transform the continuous optimization problem into a search problem over a specially constructed finite graph, and then to apply dynamic programming to find an approximation...

Integer Programming Formulation of the Bilevel Knapsack Problem

R. Mansi, S. Hanafi, L. Brotcorne (2010)

Mathematical Modelling of Natural Phenomena

The Bilevel Knapsack Problem (BKP) is a hierarchical optimization problem in which the feasible set is determined by the set of optimal solutions of parametric Knapsack Problem. In this paper, we propose two stages exact method for solving the BKP. In the first stage, a dynamic programming algorithm is used to compute the set of reactions of the follower. The second stage consists in solving an integer program reformulation of BKP. We show that the...

Locally bounded k-colorings of trees

C. Bentz, C. Picouleau (2009)

RAIRO - Operations Research

Given a tree T with n vertices, we show, by using a dynamic programming approach, that the problem of finding a 3-coloring of T respecting local (i.e., associated with p prespecified subsets of vertices) color bounds can be solved in O(n6p-1logn) time. We also show that our algorithm can be adapted to the case of k-colorings for fixed k.

Markov decision processes with time-varying discount factors and random horizon

Rocio Ilhuicatzi-Roldán, Hugo Cruz-Suárez, Selene Chávez-Rodríguez (2017)

Kybernetika

This paper is related to Markov Decision Processes. The optimal control problem is to minimize the expected total discounted cost, with a non-constant discount factor. The discount factor is time-varying and it could depend on the state and the action. Furthermore, it is considered that the horizon of the optimization problem is given by a discrete random variable, that is, a random horizon is assumed. Under general conditions on Markov control model, using the dynamic programming approach, an optimality...

Nash equilibrium payoffs for stochastic differential games with reflection

Qian Lin (2013)

ESAIM: Control, Optimisation and Calculus of Variations

In this paper, we investigate Nash equilibrium payoffs for nonzero-sum stochastic differential games with reflection. We obtain an existence theorem and a characterization theorem of Nash equilibrium payoffs for nonzero-sum stochastic differential games with nonlinear cost functionals defined by doubly controlled reflected backward stochastic differential equations.

Object library of algorithms for dynamic optimization problems: benchmarking SQP and nonlinear interior point methods

Jacek Błaszczyk, Andrzej Karbowski, Krzysztof Malinowski (2007)

International Journal of Applied Mathematics and Computer Science

The main purpose of this paper is to describe the design, implementation and possibilities of our object-oriented library of algorithms for dynamic optimization problems. We briefly present library classes for the formulation and manipulation of dynamic optimization problems, and give a general survey of solver classes for unconstrained and constrained optimization. We also demonstrate methods of derivative evaluation that we used, in particular automatic differentiation. Further, we briefly formulate...

Currently displaying 61 – 80 of 124