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