Global Optimization Using Interval Analysis - The Multi-Dimensional Case.
Greedy algorithms for optimal computing of matrix chain products involving square dense and triangular matrices
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
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...
How much do approximate derivatives hurt filter methods?
In this paper, we examine the influence of approximate first and/or second derivatives on the filter-trust-region algorithm designed for solving unconstrained nonlinear optimization problems and proposed by Gould, Sainvitu and Toint in [12]. Numerical experiments carried out on small-scaled unconstrained problems from the CUTEr collection describe the effect of the use of approximate derivatives on the robustness and the efficiency of the filter-trust-region method.
Imperfect Conjugate Gradient Algorithms for Extended Quadratic Functions.
Implementació d'un algorisme primal-dual de un punt interior amb fites superiors a les variables.
Implémentation des méthodes d'optimisation : test d'arrêt optimal, contrôle et précision de la solution
Implémentation des méthodes d'optimisation : test d'arrêt optimal, contrôle et précision de la solution (II)
Inequality-sum : a global constraint capturing the objective function
This paper introduces a new method to prune the domains of the variables in constrained optimization problems where the objective function is defined by a sum , and where the integer variables are subject to difference constraints of the form . An important application area where such problems occur is deterministic scheduling with the mean flow time as optimality criteria. This new constraint is also more general than a sum constraint defined on a set of ordered variables. Classical approaches...
Inequality-sum: a global constraint capturing the objective function
This paper introduces a new method to prune the domains of the variables in constrained optimization problems where the objective function is defined by a sum y = ∑xi, and where the integer variables xi are subject to difference constraints of the form xj - xi ≤ c. An important application area where such problems occur is deterministic scheduling with the mean flow time as optimality criteria. This new constraint is also more general than a sum constraint defined on a set of ordered variables....
Inexact solution of auxiliary problems in Polyak type algorithms
Inexact trust region method for large sparse nonlinear least squares
Integer Programming Formulation of the Bilevel Knapsack Problem
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...
Interval linear regression analysis based on Minkowski difference – a bridge between traditional and interval linear regression models
In this paper, we extend the traditional linear regression methods to the (numerical input)-(interval output) data case assuming both the observation/measurement error and the indeterminacy of the input-output relationship. We propose three different models based on three different assumptions of interval output data. In each model, the errors are defined as intervals by solving the interval equation representing the relationship among the interval output, the interval function and the interval...
Inverse problem in engineering plasticity: a quadratic programming approach
Si considera un modello discreto (per elementi finiti) di un solido o un sistema strutturale perfettamente elastoplastico, con condizioni di snervamento «linearizzate a tratti», nell’ipotesi di olonomia assunta per processi di caricamento proporzionali. Supponendo noti su base sperimentale certi spostamenti sotto assegnate azioni esterne, si formula il problema di identificare i limiti di snervamento, ossia le resistenze locali. Si dimostra che questo problema inverso di meccanica strutturale non...
Investment/financial planning with endogenous lifetimes : a heuristic approach to mixed-integer programming
Iterative Optimierungsverfahren, die unter schwachen Voraussetzungen konvergieren.
Kernel-function Based Primal-Dual Algorithms for P*(κ) Linear Complementarity Problems
Recently, [Y.Q. Bai, M. El Ghami and C. Roos, SIAM J. Opt. 15 (2004) 101–128] investigated a new class of kernel functions which differs from the class of self-regular kernel functions. The class is defined by some simple conditions on the growth and the barrier behavior of the kernel function. In this paper we generalize the analysis presented in the above paper for P*(κ) Linear Complementarity Problems (LCPs). The analysis for LCPs deviates significantly from the analysis for linear optimization....
La différentiation automatique et son utilisation en optimisation
In this work, we present an introduction to automatic differentiation, its use in optimization software, and some new potential usages. We focus on the potential of this technique in optimization. We do not dive deeply in the intricacies of automatic differentiation, but put forward its key ideas. We sketch a survey, as of today, of automatic differentiation software, but warn the reader that the situation with respect to software evolves rapidly. In the last part of the paper, we present some...
La programmation mathématique multicritère et la gestion des ressources en eau