A Preconditioned Descent Algorithm for Variational Inequalities of the Second Kind Involving the p-Laplacian Operator

Abstract: This paper is concerned with the numerical solution of a class of variational inequalities of the second kind, involving the p-Laplacian operator. This kind of problems arise, for instance, in the mathematical modelling of non-Newtonian fluids. We study these problems by using a regularization approach, based on a Huber smoothing process. Well posedness of the regularized problems is proved, and convergence of the regularized solutions to the solution of the original problem is verified. We propose a preconditioned descent method for the numerical solution of these problems and analyze the convergence of this method in function spaces. The existence of admissible descent directions is established by variational methods and admissible steps are obtained by a line search algorithm, which combines the classical Armijo’s rule with an interpolation technique. Finally, several numerical experiments are carried out to show the efficiency of the methodology here introduced.

Leer

A bus scheduling model for a public transportation system in Quito

Abstract: We propose an integer programming model for the bus scheduling problem in the METROBUS-Q public transportation system of Quito. The model is based on a multi-commodity flow formulation of the problem, and aims at minimizing both the size of the fleet and the total idle time of the vehicles in the terminals. Two primal solution heuristics and an algorithm for obtaining lower bounds from a mincost relaxation of the problem are presented. Finally, computational results for real-world data with up to 1,400 timetabled trips are reported.

Leer

An Integer Programming Model for Scheduling Classes at the Escuela Politécnica Nacional in Quito

Abstract: We present an integer programming model for scheduling lectures at a university, taking into account restrictions imposed by the availability of lecturers and classrooms, as well as by the students’ curricula. We propose a constructive heuristic and an local improvement heuristic to obtain feasible solutions for this model, and report computational results for real instances concerning the timetable planning at the Escuela Politécnica Nacional in Quito.

Leer

Generalized minor inequalities for the set covering polyhedron related to circulant matrices

Abstract: We study the set covering polyhedron related to circulant matrices. In particular, our goal is to characterize the first Chv´atal closure of the usual fractional relaxation. We present a family of valid inequalities that generalizes the family of minor inequalities previously reported in the literature and includes new facet-defining inequalities. Furthermore, we propose a polynomial time separation algorithm for a particular subfamily of these inequalities.

Leer

Finite element error estimates for an optimal control problem governed by the burgers equation.

Abstract: We derive a-priori error estimates for the finite-element approximation of a distributed optimal control problem governed by the steady onedimensional Burgers equation with pointwise box constraints on the control. Here the approximation of the state and the control is done by using piecewise linear functions. With this choice, an L2 superlinear order of convergence for the control is obtained; moreover, under a further assumption on the regularity structure of the optimal control this error estimate can be improved to h3/2. The theoretical findings are tested experimentally by means of numerical examples.

Leer

Imaging with Kantorovich-Rubinstein discrepancy

Abstract: We propose the use of the Kantorovich-Rubinstein norm from optimal transport in imaging problems. In particular, we discuss a variational regularisation model endowed with a Kantorovich-Rubinstein discrepancy term and total variation regularization in the context of image denoising and cartoon-texture decomposition. We point out connections of this ap-proach to several other recently proposed methods such as total general-ized variation and norms capturing oscillating patterns. We also show thatthe respective optimization problem can be turned into a convex-concave saddle point problem with simple constraints and hence, can be solved by standard tools. Numerical examples exhibit interesting features and favourable performance for denoising and cartoon-texture decomposition.

Leer

The jump set under geometric regularisation. Part 1: Higher order approaches

Abstract:

Leer

The jump set under geometric regularisation. Part 1: Basic technique and first-order denoising

Abstract:

Leer

Optimizando la asignación de flota en sistemas de transportación pública.

Abstract: El presente reporte comprende una revisión del estado del arte respecto a la mod- elización matemática del problema de asignación de flota en un sistema de trans- portación pública. El problema consiste en el cubrimiento de un conjunto de viajes conocidos a-priori, empleando una flota de vehículos ubicados en algunas terminales. Cada viaje es caracterizado por una estación de origen, una estación de destino, una hora de inicio y una hora de llegada. Se busca un plan de viajes que indique la secuencia de viajes a ser cubiertos por cada vehículo de la flota, tomando en cuenta algunos criterios de optimización, por ejemplo, minimizar la cantidad de vehículos empleados, o minimizar la divergencia entre las distancias recorridas por los dis- tintos vehículos. Este artículo discute varios tipos de formulaciones y proporciona una actualizada y detallada revisión de los conceptos y definiciones del problema de asignación de flota, como un primer paso para el desarrollo de nuevos modelos, estrategias y extensiones orientados la planificación operativa del corredor central del Sistema Integrado de Transporte Metrobús-Q.

Leer

Second-order orthant-based methods with enriched Hessian information for sparse l1-optimization

Abstract: We present a second order algorithm for solving optimization problems involving the sparsity enhancing `1-norm. An orthantwise-direction strategy is used in the spirit of [1]. The main idea of our method consists in computing the descent directions by incorporating second order information both of the regular term and (in weak sense) of the `1-norm. The weak second order information behind the `1-term is incorporated via a partial Huber regularization. One of the main features of our algorithm consists in a faster identi_cation of the active set. We also prove that our method is equivalent to a semismooth Newton algorithm applied to the optimality condition, under a speci_c choice of the (SSN) de_ning constants. We present several computational experiments to show the e_ciency of our approach compared to other up-to-date algorithms.

Leer

An adaptive numerical method for semi-infinite elliptic control problems based on error estimates

Abstract: We discuss numerical reduction methods for an optimal control prob- lem of semi-infinite type with finitely many control parameters but in- finitely many constraints. We invoke known a-priori error estimates to reduce the number of constraints. In a first strategy, we apply uniformly refined meshes, whereas in a second more heuristic strategy we use adap- tive mesh-refinement and provide an a-posteriori error estimate for the control based on perturbation arguments.

Leer

Optimal control of electrorheological fluids through the action of electric fields.

Abstract: An optimal control problem of steady-state electrorheological fluids based on an extended Bingham model. Our control parameters are given by finite real numbers representing applied direct voltages which enter into the viscosity of the electrorheological fluid via an electrostatic potential. The corresponding optimization problem belongs to a class of nonlinear optimal control problems of variational inequalities with control in the coefficients. We analyze the associated variational inequality model and the optimal control problem. Thereafter, we introduce a family of Huber-regularized optimal control problems for the approximation of the original one and verify the convergence of the regularized solutions. Differentiability of the solution operator is proved and an optimality system for each regularized problem is established. In the last part of the paper, an algorithm for the numerical solution of the regularized problem is constructed and numerical experiments are carried out.

Leer

Error estimates for optimal control problems of a class of quasilinear equations arising in variable viscosity fluid flow

Abstract: We consider optimal control problems of quasilinear elliptic equations with gradient coefficients, arising in variable viscosity fluid flow. The state equation is monotone and the controls are of distributed type. We prove that the control-to-state operator is twice Fréchet differentiable for this class of equations. A finite element approximation is studied and an estimate of order \(h^{min(2s,1)}\), \(s \in (0, 1)\), is obtained for the control. The result makes use of the distributed structure of the controls, together with a regularity estimate for elliptic equations with Hölder coefficients and a second order sufficient optimality condition. The paper ends with a numerical experiment, where the approximation order is computationally tested.

Leer

B-stationarity conditions for a class of optimization problems governed by variational inequalities of the 2nd kind

Abstract: We investigate optimality conditions for optimization problems constrained by a class of variational inequalities of the second kind. Based on a nonsmooth primal-dual reformulation of the governing inequality, the differentiability of the solution map is studied. Directional differentiability is proved both for finite-dimensional and function space problems, under suitable assumptions on the active set. A characterization of B-stationary optimal solutions is obtained thereafter. Finally, based on the obtained first-order information, an inexact trust-region algorithm is proposed for the solution of the optimization problems.

Leer

On the first Chvátal closure of the set covering polyhedron related to circulant matrices

Abstract: We study the set covering polyhedron related to circulant matrices. In particular, our goal is to characterize the first Chvátal closure of the usual fractional relaxation. We present a family of valid inequalities that generalizes the family of minor inequal- ities previously reported in the literature. This family includes new facet-defining inequalities for the set covering polyhedron.

Leer

Acerca de una versión dinámica del problema de la mochila

Abstract: El problema de la mochila (Knapsack Problem, KP) es un problema clásico de optimización combinatoria que ha sido ampliamente estudiado por más de un siglo. Es uno de los problemas de programación lineal entera más simples; aparece como subproblema en otros problemas más complejos; y tiene muchas aplicaciones prácticas, en áreas tan diversas como el corte de material [6], la selección de inversiones de capital y portafolios financieros [10], la correcta administración de recursos de cómputo, del ancho de banda de una conexión, del espacio de almacenamiento en discos duros [14], etc. Variantes dinámicas de este problema han sido estudiadas por sus aplicaciones prácticas, aunque no en gran extensión y con pocos resultados obtenidos hasta el presente. La variante considerada en este artículo consiste en agregar una dimensión temporal (discreta) al problema clásico: a cada objeto se le asigna una duración, que indica el intervalo de tiempo que éste debe permanecer dentro de la mochila cada vez que es seleccionado. Se busca maximizar el valor total almacenado en la mochila dentro de un horizonte temporal T. Formulamos un modelo de programación lineal entero para este problema y presentamos un algoritmo de solución exacto basado en el esquema branch-and-bound. Adicionalmente, estudiamos su comportamiento y su desempeño computacional.

Leer

Reduction of population dispersion model using the POD method.

Abstract: We consider population growth model equations described by Fisher, consisting of a parabolic reaction-difussion equation in two dimensions. In this paper, we propose the application of the method POD (Proper Orthogonal Decomposition) for the purpose of establishing a reduced numerical model for Fisher's equation using the Implicit Euler schemes and Crank-Nicholson. The resulting reduced schemes use a much smaller number of variables, compared with their counterparts approximation with basis functions give the finite element method. We present several numerical experiments to test the efficiency of the reduction.

Leer

Un modelo de programación entera para la asignación de flota en el Sistema de Transporte Metrobús-Q

Abstract: El presente trabajo considera el problema de asignación de flota en el contexto del Sistema Integrado de Transportación Pública Metrobús-Q. El problema consiste en el cubrimiento de un conjunto de viajes conocidos a-priori con una flota de vehículos heterogénea y almacenada en múltiples depósitos, mientras se minimizan los costos operacionales. Para ello, un modelo de programación lineal entera basado en flujos multi-producto es presentado. Inicialmente proponemos la implementación del mo- delo en el solver de programación entera GUROBI y la obtención de cotas inferiores basados en algoritmos de flujos de costo de mínimo.

Leer

Optimal Control of Static Elastoplasticity in Primal Formulation.

Abstract: An optimal control problem of static plasticity with linear kinematic hardening and von Mises yield condition is studied. The problem is treated in its primal formulation, where the state system is a variational inequality of the second kind. First-order necessary optimality conditions are obtained by means of an approximation by a family of control problems with state system regularized by Huber-type smoothing, and a subsequent limit analysis. The equivalence of the optimality conditions with the C-stationarity system Herzog et al. [2012] for the equivalent dual formulation of the problem is proved. Numerical experiments are presented, which demonstrate the viability of the Huber-type smoothing approach.

Leer