Multi-weight graph partitioning problem

Abstract: In this work a multi-weight graph partitioning problem is introduced. This problem consists in partitioning an undirected graph in a fixed number of subgraphs such that multiple node weight constraints over each partition are satisfied and the total distance between nodes in the same subgraph induced by the partition is minimized. This problem generalizes several graph partitioning problems like $k$-way equipartition, and bisection. It arises as a subproblem of an integrated vehicle and pollster problem from a real world application. Two Integer Programming formulations are provided and several families of valid inequalities associated to the respective polyhedra are proved. An exact algorithm based on branch and bound and cutting planes is proposed and it is tested on real-world instances.

Leer

Integrated Vehicle and Pollster Routing

Abstract: The National Statistics Bureau of Ecuador carries out monthly polls to monitor the evolution of an economic indicator called “Consumer Price Index”, which measures the consumer prices of basic commodities. A set of stores is selected to apply these polls. A set of vehicles transport pollsters from the headquarters of the bureau to the stores to perform this activity. Moreover, pollsters move between stores using pedestrian paths or using a vehicle to shorten the travel time between far away stores. This paper introduces an integer programming model for the integrated task of scheduling visits of pollsters to selected stores, as well as routing the vehicle fleet used to transport them. Results on the computational complexity of the aforementioned problem, a three-phase algorithm, and computational experience based on real-world instances are provided.

Leer

Primal-dual proximal splitting and generalized conjugation in non-smooth non-convex optimization

Abstract: We demonstrate that difficult non-convex non-smooth optimization problems, such as Nash equilibrium problems and anisotropic as well as isotropic Potts segmentation model, can be written in terms of generalized conjugates of convex functionals. These, in turn, can be formulated as saddle-point problems involving convex non-smooth functionals and a general smooth but non-bilinear coupling term. We then show through detailed convergence analysis that a conceptually straightforward extension of the primal--dual proximal splitting method of Chambolle and Pock is applicable to the solution of such problems. Under sufficient local strong convexity assumptions of the functionals -- but still with a non-bilinear coupling term -- we even demonstrate local linear convergence of the method. We illustrate these theoretical results numerically on the aforementioned example problems.

Leer

Block-proximal methods with spatially adapted acceleration

Abstract: We study and develop (stochastic) primal--dual block-coordinate descent methods for convex problems based on the method due to Chambolle and Pock. Our methods have known convergence rates for the iterates and the ergodic gap: O(1/N2) if each block is strongly convex, O(1/N) if no convexity is present, and more generally a mixed rate O(1/N2)+O(1/N) for strongly convex blocks, if only some blocks are strongly convex. Additional novelties of our methods include blockwise-adapted step lengths and acceleration, as well as the ability to update both the primal and dual variables randomly in blocks under a very light compatibility condition. In other words, these variants of our methods are doubly-stochastic. We test the proposed methods on various image processing problems, where we employ pixelwise-adapted acceleration.

Leer

Inertial, corrected, primal--dual proximal splitting

Abstract: We study inertial versions of primal--dual proximal splitting, also known as the Chambolle--Pock method. Our starting point is the preconditioned proximal point formulation of this method. By adding correctors corresponding to the anti-symmetric part of the relevant monotone operator, using a FISTA-style gap unrolling argument, we are able to derive gap estimates instead of merely ergodic gap estimates. Moreover, based on adding a diagonal component to this corrector, we are able to combine strong convexity based acceleration with inertial acceleration. We test our proposed method on image processing and inverse problems problems, obtaining convergence improvements for sparse Fourier inversion and Positron Emission Tomography.

Leer

A bilevel learning approach for optimal observation placement in variational data assimilation

Abstract: In this paper we propose a bilevel optimization approach for the placement of observations in variational data assimilation problems. Within the framework of supervised learning, we consider a bilevel problem where the lower level task is the variational reconstruction of the initial condition of the system, and the upper level problem solves the optimal placement with help of a sparsity inducing norm. Due to the pointwise nature of the observations, an optimality system with regular Borel measures on the right-hand side is obtained as necessary and sufficient optimality condition for the lower level problem. The latter is then considered as constraint for the upper level instance, yielding an optimization problem constrained by time-dependent PDE's with measures. After proving some extra regularity results, we demonstrate the existence of Lagrange multipliers and derive a necessary optimality system characterizing the optimal solution of the bilevel problem. The numerical solution is carried out also on two levels. The lower level problem is solved using a standard BFGS method, while the upper level one is solved by means of a projected BFGS algorithm based on the estimation of e-active sets. A penalty function is also considered for enhancing sparsity of the location weights. Finally, some numerical experiments are presented to illustrate the main features of our approach.

Leer

Testing and non-linear preconditioning of the proximal point method

Abstract: Employing the ideas of non-linear preconditioning and testing of the classical proximal point method, we formalise common arguments in convergence rate and convergence proofs of optimisation methods to the verification of a simple iteration-wise inequality. When applied to fixed point operators, the latter can be seen as a generalisation of firm non-expansivity or the $\alpha$-averaged property. The main purpose of this work is to provide the abstract background theory for our companion paper "Block-proximal methods with spatially adapted acceleration". In the present account we demonstrate the effectiveness of the general approach on several classical algorithms, as well as their stochastic variants. Besides, of course, the proximal point method, these method include the gradient descent, forward--backward splitting, Douglas--Rachford splitting, Newton's method, as well as several methods for saddle-point problems, such as the Alternating Directions Method of Multipliers, and the Chambolle--Pock method.

Leer

Interior-proximal primal-dual methods

Abstract: We study preconditioned proximal point methods for a class of saddle point problems, where the preconditioner decouples the overall proximal point method into an alternating primal--dual method. This is akin to the Chambolle--Pock method or the ADMM. In our work, we replace the squared distance in the dual step by a barrier function on a symmetric cone, while using a standard (Euclidean) proximal step for the primal variable. We show that under non-degeneracy and simple linear constraints, such a hybrid primal--dual algorithm can achieve linear convergence on originally strongly convex problems involving the second-order cone in their saddle point form. On general symmetric cones, we are only able to show an O(1/N) rate. These results are based on estimates of strong convexity of the barrier function, extended with a penalty to the boundary of the symmetric cone.

Leer

ERROR ESTIMATES FOR THE FEM APPROXIMATION OF STATE–CONSTRAINED ELLIPTIC OPTIMAL CONTROL PROBLEMS WITH SPARSITY IN A FINITE–DIMENSIONAL CONTROL SPACE

Abstract: In this work, we derive an a–priori error estimate of order $h^2|log(h)|$ for the finite element approximation of an sparse optimal control problem governed by an elliptic equation, which is controlled in a finite dimensional space. Furthermore, box–constrains on the control are considered and finitely many pointwise state–constrains are imposed in specific points in the domain. With this choice for the control space, the achieved order of approximation for the optimal control is optimal, in the sense that the order of the error for the optimal control is of the same order of the approximation fro the state equation.

Leer

Acceleration and global convergence of a first-order primal--dual method for nonconvex problems

Abstract: The primal--dual hybrid gradient method (PDHGM, also known as the Chambolle--Pock method) has proved very successful for convex optimization problems involving linear operators arising in image processing and inverse problems. In this paper, we analyze an extension to nonconvex problems that arise if the operator is nonlinear. Based on the idea of testing, we derive new step length parameter conditions for the convergence in infinite-dimensional Hilbert spaces and provide acceleration rules for suitably (locally and/or partially) monotone problems. Importantly, we prove linear convergence rates as well as global convergence in certain cases. We demonstrate the efficacy of these step length rules for PDE-constrained optimization problems.

Leer

Preconditioned proximal point methods and notions of partial subregularity

Abstract: Based on the needs of convergence proofs of preconditioned proximal point methods, we introduce notions of partial strong submonotonicity and partial (metric) subregularity of set-valued maps. We study relationships between these two concepts, neither of which is generally weaker or stronger than the other one. For our algorithmic purposes, the novel submonotonicity turns out to be easier to employ than more conventional error bounds obtained from subregularity. Using strong submonotonicity, we demonstrate the a posteriori linear convergence of the Primal--Dual Hybrid Gradient Method (Modified) to some strictly complementary solutions of example problems from image processing and data science. This is without the conventional assumption that all the objective functions of the involved saddle point problem are strongly convex.

Leer

Total Generalized Variation Regularization in Variational Data Assimilation for Burgers' Equation

Abstract: We propose a second-order total generalized variation (TGV) regularization for the reconstruction of the initial condition in variational data assimilation problems. After showing the equivalence between TGV regularization and the Bayesian method for the MAP estimator, we focus on the detailed study of the inviscid Burgers' data assimilation problem. Due to the difficult structure of the governing hyperbolic conservation law, we consider a discretize-then-optimize approach and derive first-order optimality conditions for the problem. For the numerical solution, we propose a globalized reduced Newton-type method and prove convergence of the algorithm to stationary points. The paper finishes with some numerical experiments where among others, the performance of TGV-regularization compared to the TV-regularization is tested.

Leer

The set covering polyhedron of circular matrices: Minor vs. row family inequalities

Abstract: In the context of the study of the set covering polyhedron of circular matrices, we study the relationship between row family inequalities and a previously proposed class termed minor inequalities. Recently, a complete linear description of this polyhedron has been provided in terms of row family inequalities. In this work we prove that for the particular subclass of circulant matrices, the corresponding row family inequalities are related to circulant minors. Moreover, we extend previous results on circulant matrices $C_{sk}^k$, $s\in\{2,3\}$ and $k\ge 2$, by providing a polynomial time separation algorithm for the inequalities describing the set covering polyhedron of matrices $C_{4k}^k$, $k\ge 2$.

Leer

On the Chvátal-rank of facets for the set covering polyhedron of circular matrices

Abstract: We study the family of minor related row family inequalities for the set covering polyhedron related to circular matrices introduced in [8]. We provide a construction to obtain facets with arbitrarily large coefficients. Moreover, we address the issue of generating these inequalities via the Chvátal-Gomory rounding procedure and provide examples of inequalities having Chvátal-rank strictly larger than one.

Leer

On dominating set polyhedra of circular interval graphs

Abstract: Clique-node and closed neighborhood matrices of circular interval graphs are circular matrices. The stable set polytope and the dominating set polytope on these graphs are therefore closely related to the set packing polytope and the set covering polyhedron on circular matrices. Eisenbrand et al. take advantage of this relationship to propose a complete linear description of the stable set polytope on (fuzzy) circular interval graphs. In this paper we follow si milar ideas to obtain a complete description of the dominating set polytope on circular interval graphs. As in the packing case, our results are established for a larger class of covering polyhedra of the form $Q^*(A,b):= conv\{x\in \mathbb{Z}_+^n: Ax\ge b\}$, with $A$ a $\{0,1\}$-matrix and $b$ an integer vector.

Leer

On the optimal control of some nonsmooth distributed parameter systems arising in mechanics

Abstract: Variational inequalities are an important mathematical tool for modelling free boundary problems that arise in different application areas. Due to the intricate nonsmooth structure of the resulting models, their analysis and optimization is a difficult task that has drawn the attention of researchers for several decades. In this paper we focus on a class of variational inequalities, called of the second kind, with a twofold purpose. First, we aim at giving a glance at some of the most prominent applications of these types of variational inequalities in mechanics, and the related analytical and numerical difficulties. Second, we consider optimal control problems constrained by these variational inequalities and provide a thorough discussion on the existence of Lagrange multipliers and the different types of optimality systems that can be derived for the characterization of local minima. The article ends with a discussion of the main challenges and future perspectives of this important problem class.

Leer

A non-smooth trust-region method for B-differentiable functions with application to optimization problems constrained by variational inequalities

Abstract: We propose a non-smooth trust-region method for solving optimization problems with B-differentiable functions, with application to problems constrained by variational inequalities of the second kind. Under suitable assumptions on the model functions, convergence of the general algorithm to a C-stationary point is verified. For variational inequality constrained problems, we are able to properly characterize the Bouligand subdifferential of the reduced cost function and, based on that, we propose a computable trust-region model which fulfills the convergence hypotheses of the general algorithm. The article concludes with the experimental study of the main properties of the proposed method based on two different numerical instances.

Leer

A DC–PROGRAMMING APPROACH FOR SPARSE PDE OPTIMAL CONTROL PROBLEMS WITH NONCONVEX FRACTIONAL COSTS

Abstract: We propose a local regularization of elliptic optimal control problems which involves the nonconvex $L^q$ fractional penalizations in the cost function. The proposed Huber type regularization allows us to formulate the PDE constrained optimization formulation as a DC programming problem (difference of convex functions) that is useful to obtain necessary optimality conditions and tackle its numerical solution by applying the well known DC algorithm used in nonconvex optimization problems. By this procedure we approximate the original problem in terms of a consistent family of parameterized problems for which there are efficient numerical methods available. Finally, we present numerical experiments to illustrate our theory with different configurations associated to the parameters of the problem.

Leer

An Exact Approach for the Balanced k-Way Partitioning Problem with Weight Constraints and its Application to Sports Team Realignment

Abstract: In this work a balanced k-way partitioning problem with weight constraints is defined to model the sports team realignment. Sports teams must be partitioned into a fixed number of groups according to some regulations, where the total distance of the road trips that all teams must travel to play a Double Round Robin Tournament in each group is minimized. Two integer programming formulations for this problem are introduced, and the validity of three families of inequalities associated to the polytope of these formulations is proved. The performance of a tabu search procedure and a Branch & Cut algorithm, which uses the valid inequalities as cuts, is evaluated over simulated and real-world instances. In particular, an optimal solution for the realignment of the Ecuadorian Football league is reported and the methodology can be suitable adapted for the realignment of other sports leagues.

Leer

A locking-free optimal control problem with $L^1$ cost for optimal placement of control devices in Timoshenko beam

Abstract: The numerical approximation of an optimal control problem with $L^1$-control of a Timoshenko beam is considered and analyzed by using the finite element method. From the practical point of view, inclusion of the $L^1$-norm in the cost functional is interesting in the case of beam vibration model, since the sparsity enforced by the $L^1$-norm is very useful for localizing actuators or control devices. The discretization of the control variables is performed by using piecewise constant functions. The states and the adjoint states are approximated by a locking free scheme of linear finite elements. Analogously to the purely $L^2$-norm penalized optimal control, it is proved that this approximation have optimal convergence order, which do not depend on the thickness of the beam.

Leer

A MULTIGRID OPTIMIZATION APPROACH FOR THE NUMERICAL SOLUTION OF A CLASS OF VARIATIONAL INEQUALITIES OF THE SECOND KIND

Abstract: In this work we introduce a Multigrid Optimization Algorithm (MG/OPT) for the numerical solution of a class of quasilinear variational inequalities of the second kind, which involve the p-Laplacian operator and the $L^1$-norm of the gradient. The solution of the variational inequality is given by the solution of an optimization algorithm.We proposed a Huber regularization of the functional for the $L^1$-norm of the gradient and a finite element discretization for the problem. Finally, we analyze the performance of the MG/OPT algorithm when used to simulate the visco-plastic flows in a pipe. Several numerical experiments are carried out to show the main features of the proposed method.

Leer

A MULTIGRID OPTIMIZATION APPROACH FOR THE NUMERICAL SOLUTION OF A CLASS OF VARIATIONAL INEQUALITIES OF THE SECOND KIND

Abstract: In this work we introduce a Multigrid Optimization Algorithm (MG/OPT) for the numerical solution of a class of quasilinear variational inequalities of the second kind, which involve the p-Laplacian operator and the $L^1$-norm of the gradient. The solution of the variational inequality is given by the solution of an optimization algorithm.We proposed a Huber regularization of the functional for the $L^1$-norm of the gradient and a finite element discretization for the problem. Finally, we analyze the performance of the MG/OPT algorithm when used to simulate the visco-plastic flows in a pipe. Several numerical experiments are carried out to show the main features of the proposed method.

Leer

OPTIMIZACIÓN BINIVEL DEL PARÁMETRO DE REGULARIZACIÓN CON DEPENDENCIA ESPACIAL DEL MODELO DE VARIACIÓN TOTAL GENERALIZADA PARA EL FILTRADO DE RUIDO EN IMÁGENES

Abstract: In this thesis, we study and solve a nonlinear bilevel optimization problem in function spaces. The goal is to determine the optimal spatially dependent regularization parameters in total variation (TV) and generalized total variation (TGV) image denoising models. Considering the spatial dependence of the parameters allows us to filter non-uniform noise in an image, which brings us closer to real situations where the type and distribution of noise are not known. We present some analytical results like the existence of solutions of the problem of parameter optimization, the Fréchet differentiability of the solution operator, which allows to prove the existence of Lagrange multipliers. The multipliers associated with the positivity constraints are regular Borel measured which are very difficult to compute. In order to overcome this issue, we proposed a Moreau-Yosida regularization, where the optimality system associated with the regularized problem was established and we prove that the solutions of regularized problems converge to the solution of the original one.

Leer

SOLUCIÓN DE UN PROBLEMA DE ASIMILACIÓN DE DATOS Y UN PROBLEMA DE LOCALIZACIÓN ÓPTIMA MEDIANTE MÉTODOS DE OPTIMIZACIÓN BINIVEL

Abstract: Data assimilation problems have been widely studied in numerical weather prediction as a technique for the reconstruction of the atmosphere’s initial condition. Taking this problem as motivation, our goal in this project is finding the optimal placements of the locations of a data assimilation problem, represented by a parabolic equation. We worked in a bilevel optimization problem where the inner level solves the data assimilation problem, and the upper level solves the optimal placement problem. To solve the data assimilation problem, we used a variational approach 4D-VAR. The existence and uniqueness of the data assimilation problem were demonstrated using usual techniques in optimization. By using the Lagrangian approach, we derive the optimality system of the inner problem. As result, we got an adjoint equation with measures on the right-hand side. This was due to the structure of the objective functional. We proved the existence of a unique very weak solution of the adjoint equation by using the transposition method. The numerical solution was also worked in two levels. The inner problem was solved by using the BFGS method while the upper level used the BFGS projected method through an estimation of $\epsilon$-active sets jointly with a modified Armijo line search and a stop criterio which takes full steps.

Leer

PHOTOGRAPHIC DATASET: PLAYING CARDS

Abstract: A photographic dataset is collected for testing image processing algorithms.

Leer

Balanced Partition of a Graph for Football Team Realignment in Ecuador

Abstract: In the second category of the Ecuadorian football league, a set of football teams must be grouped in k geographical zones according to some regulations, where the total distance of the road trips that all teams must travel to play a Double Round Robin Tournament in each zone is minimized. This problem can be modeled as a k clique partitioing problem with constraints on the sizes and weights of the cliques. An integer programming formulation and a heuristic approach were developed to provide a solution to the problem which has been implemented in the 2015 edition of this football championship.

Leer

VEHICLE AND DUTY SCHEDULING FOR A PUBLICTRANSPORTATION SYSTEM IN QUITO

Abstract: We address the vehicle and duty scheduling problems in the context of the Trolebus public transportation system of Quito. An integer programming model for the vehicle scheduling problem based on a multi-commodity flow formulation is presented. The model aims at minimizing both the size of the fleet and the total idle time of the vehicles at the terminals. A primal heuristic for solving this model is proposed. This heuristic is later extended to an algorithm for solving the integrated vehicle and duty scheduling problem under the particular circumstances of the studied system. The method is based on the idea of aggregating sequences of trips that minimize the idle time and at the same time conform to legal and administrative constraints which are inherent to the duty scheduling problem. Computational results for real-world data with up to 1,400 timetabled trips are reported.

Leer

LEARNING OPTIMAL SPATIALLY-DEPENDENT REGULARIZATION PARAMETERS IN TOTAL VARIATION IMAGE RESTORATION

Abstract: We consider a bilevel optimization approach in function space for the choice of spatially dependent regularization parameters in TV image restoration models. First- and second-order optimality conditions for the bilevel problem are studied, when the spatially-dependent parameter belongs to the Sobolev space $H1( )$. A combined Schwarz domain decomposition semismooth Newton method is proposed for the solution of the full optimality system and local superlinear convergence of the semismooth Newton method is analyzed. Exhaustive numerical computations are finally carried out to show the suitability of the approach.

Leer

Métodos de optimización para la segmentación numérica de imágenes usando el modelo de Chan-Vese

Abstract: La segmentación de imágenes consiste en dividir una imagen en subconjuntos donde cada uno de ellos corresponda a un objeto que la constituye. Durante los últimos años se ha propuesto una gran variedad de modelos de segmentación vinculados a diferentes áreas de la Matemática. En nuestro caso, nos enfocamos en la formulación variacional del problema propuesta por Chan y Vese. El modelo se plantea utilizando conjuntos de nivel con el objetivo de minimizar el funcional de energía asociado al problema de segmentación. El método consiste en la evolución de una curva de nivel que, bajo ciertos criterios, se detiene en el contorno de los objetos que forman la imagen. Resolver numéricamente este problema es, en general, muy costoso. La utilización de métodos de optimización numérica permite dar una solución eficiente a este inconveniente y garantiza la convergencia de la solución hacia un mínimo. Se analizan métodos tales como: el método de descenso explícito, un método de tipo proximal y LBFGS, que combinados con el método del momento, permiten hacer uso de la información de primer y segundo orden del funcional para acelerar los métodos utilizados tradicionalmente.

Leer

Bilevel parameter learning for Higher-order Total Variation Regularisation Models

Abstract: We consider a bilevel optimisation approach for parameter learning in higher-order total variation image reconstruction models. Apart from the least squares cost functional, naturally used in bilevel learning, we propose and analyse an alternative cost, based on a Huber regularised TV-seminorm. Differentiability properties of the solution operator are verified and a first-order optimality system is derived. Based on the adjoint information, a quasi-Newton algorithm is proposed for the numerical solution of the bilevel problems. Numerical experiments are carried out to show the suitability of our approach and the improved performance of the new cost functional. Thanks to the bilevel optimisation framework, also a detailed comparison between TGV2 and ICTV is carried out, showing the advantages and shortcomings of both regularisers, depending on the structure of the processed images and their noise level.

Leer

Métodos variacionales para la restauración de dominios perdidos de imágenes y su resolución numérica mediante métodos de segundo orden

Abstract: Entre los problemas más interesantes a tratar dentro del procesamiento de imágenes se encuentra el problema de inpainting, que consiste en reconstruir o restaurar partes deterioradas o perdidas de la imagen observada, a partir de la información disponible alrededor del área a ser recuperada, además de remover objetos que no sean de interés pues ocultan información. En la última década, varios modelos de inpainting basados en distintos conceptos matemáticos han sido planteados para resolver este problema. En este trabajo, nos enfocaremos en la formulación variacional de Chan y Shen [9] basado en la regularización de variación total y el modelo basado en la ecuación del movimiento de la curvatura media [3]. No sólo el planteamiento y la ejecución de la restauración de imágenes son un proceso complejo, sino también su implementación computacional, por la gran cantidad de datos que se deben procesar. Es así que, en este trabajo se proponen algoritmos numéricos de segundo orden basados en el método Newton semi-suave, pues existen términos no definidos que regularizados presentan términos no diferenciables.

Leer

The structure of optimal parameters for image restoration problems

Abstract: We study the qualitative properties of optimal regularisation parameters in variational models for image restoration. The parameters are solutions of bilevel optimisation problems with the image restoration problem as constraint. A general type of regulariser is considered, which encompasses total variation (TV), total generalized variation (TGV) and infimal-convolution total variation (ICTV). We prove that under certain conditions on the given data optimal parameters derived by bilevel optimisation problems exist. A crucial point in the existence proof turns out to be the boundedness of the optimal parameters away from 0 which we prove in this paper. The analysis is done on the original – in image restoration typically non-smooth variational problem – as well as on a smoothed approximation set in Hilbert space which is the one considered in numerical computations. For the smoothed bilevel problem we also prove that it $\Gamma$ converges to the original problem as the smoothing vanishes. All analysis is done in function spaces rather than on the discretised learning problem.

Leer

Bilevel approaches for learning of variational imaging models

Abstract: We review some recent learning approaches in variational imaging, based on bilevel optimisation, and emphasize the importance of their treatment in function space. The paper covers both analytical and numerical techniques. Analytically, we include results on the existence and structure of minimisers, as well as optimality conditions for their characterisation. Based on this information, Newton type methods are studied for the solution of the problems at hand, combining them with sampling techniques in case of large databases. The computational verification of the developed techniques is extensively documented, covering instances with different type of regularisers, several noise models, spatially dependent weights and large image databases.

Leer

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