Search

Different notions on regularity of sets and of collection of sets play an important role in the analysis of the convergence of projection algorithms in nonconvex scenarios. While some projection algorithms can be applied to feasibility problems defined by finitely many sets, some other require the use of a product space reformulation to construct equivalent problems with two sets. In this work we analyze how some regularity properties are preserved under a reformulation in a product space of reduced dimension. This allows us to establish local linear convergence of parallel projection methods which are constructed through this reformulation.

The Boosted Difference of Convex functions Algorithm (BDCA) has been recently introduced to accelerate the performance of the classical Difference of Convex functions Algorithm (DCA). This acceleration is achieved thanks to an extrapolation step from the point computed by DCA via a line search procedure. In this work, we propose an extension of BDCA that can be applied to difference of convex functions programs with linear constraints, and prove that every cluster point of the sequence generated by this algorithm is a Karush–Kuhn–Tucker point of the problem if the feasible set has a Slater point. When the objective function is quadratic, we prove that any sequence generated by the algorithm is bounded and R-linearly (geometrically) convergent. Finally, we present some numerical experiments where we compare the performance of DCA and BDCA on some challenging problems: to test the copositivity of a given matrix, to solve one-norm and infinity-norm trust-region subproblems, and to solve piecewise quadratic problems with box constraints. Our numerical results demonstrate that this new extension of BDCA outperforms DCA.

In this work, we develop a systematic framework for computing the resolvent of the sum of two or more monotone operators which only activates each operator in the sum individually. The key tool in the development of this framework is the notion of the “strengthening” of a set-valued operator, which can be viewed as a type of regularisation that preserves computational tractability. After deriving a number of iterative schemes through this framework, we demonstrate their application to best approximation problems, image denoising and elliptic PDEs.

El problema de encontrar representaciones adecuadas de objetos abstractos es tan antiguo como las propias Matemáticas. En el ámbito de la docencia de las mismas, y especialmente de la Geometría y la Topología, nos enfrentamos muy frecuentemente con el problema de imaginar y visualizar de manera adecuada ciertas funciones, curvas, superficies y otros elementos. Representar objetos en dimensión dos es sencillo pues podemos plasmarlos simplemente en una hoja de papel o en una pizarra. En cambio, algunos entes tridimensionales, que también son susceptibles de admitir un dibujo bidimensional usando proyecciones, son mucho más difíciles de manejar y dibujar sin las herramientas adecuadas. En este trabajo de investigación, nuestro objetivo principal ha sido explorar el potencial de la versión 3D del software GeoGebra para visualizar y manipular cierto tipo de objetos tridimensionales: las superficies cuádricas. Al mismo tiempo, hemos intentado indagar sobre las ventajas educativas de la representación de dichas superficies utilizando herramientas de representación en 3D. Desgranaremos las fases que hemos seguido poniendo algún ejemplo de las actividades implementadas y finalizaremos con el análisis de los resultados obtenidos concluyendo que esta experiencia nos ha llevado a apreciar positivamente la utilización de herramientas de representación en 3D para mejorar las capacidades de visualización de conceptos geométricos de nuestros alumnos.

El problema de encontrar representaciones adecuadas de objetos abstractos es tan antiguo como las propias Matemáticas. En el ámbito de la docencia de las mismas, y especialmente de la Geometría y la Topología, nos enfrentamos muy frecuentemente con el problema de imaginar y visualizar de manera adecuada ciertas funciones, curvas, superficies y otros elementos. Representar objetos en dimensión dos es sencillo pues podemos plasmarlos simplemente en una hoja de papel o en una pizarra. En cambio, algunos entes tridimensionales, que también son susceptibles de admitir un dibujo bidimensional usando proyecciones, son mucho más difíciles de manejar y dibujar sin las herramientas adecuadas. En este trabajo de investigación, nuestro objetivo principal ha sido explorar el potencial de la versión 3D del software GeoGebra para visualizar y manipular cierto tipo de objetos tridimensionales: las superficies cuádricas. Para ello, hemos diseñado una serie de actividades usando las herramientas que ofrece GeoGebra 3D con las que los alumnos han podido acercarse a estos objetos. Una vez realizadas dichas actividades, hemos realizado un estudio de la satisfacción e impresiones de los participantes a través de una encuesta online. El análisis de los resultados recogidos arroja principalmente la siguiente conclusión: la introducción de herramientas de representación de objetos en tres dimensiones (GeoGebra 3D, en nuestro caso) resulta altamente positiva. Las capacidades de visualización de objetos geométricos tridimensionales de nuestros alumnos mejoran; especialmente su destreza en el manejo de las superficies cuádricas.

The Difference of Convex functions Algorithm (DCA) is widely used for minimizing the difference of two convex functions. A recently proposed accelerated version, termed BDCA for Boosted DC Algorithm, incorporates a line search step to achieve a larger decrease of the objective value at each iteration. Thanks to this step, BDCA usually converges much faster than DCA in practice. The solutions found by DCA are guaranteed to be critical points of the problem, but these may not be local minima. Although BDCA tends to improve the objective value of the solutions it finds, these are frequently just critical points as well. In this paper we combine BDCA with a simple Derivative-Free Optimization (DFO) algorithm to force the d-stationarity (lack of descent direction) at the point obtained. The potential of this approach is illustrated through some computational experiments on a Minimum-Sum-of-Squares clustering problem. Our numerical results demonstrate that the new method provides better solutions while still remains faster than DCA in the majority of test cases.

We study the behavior of the Douglas–Rachford algorithm on the graph vertex-coloring problem. Given a graph and a number of colors, the goal is to find a coloring of the vertices so that all adjacent vertex pairs have different colors. In spite of the combinatorial nature of this problem, the Douglas–Rachford algorithm was recently shown to be a successful heuristic for solving a wide variety of graph coloring instances, when the problem was cast as a feasibility problem on binary indicator variables. In this work we consider a different formulation, based on semidefinite programming. The much improved performance of the Douglas–Rachford algorithm, with this new approach, is demonstrated through various numerical experiments.

The Douglas–Rachford algorithm is an optimization method that can be used for solving feasibility problems. To apply the method, it is necessary that the problem at hand is prescribed in terms of constraint sets having efficiently computable nearest points. Although the convergence of the algorithm is guaranteed in the convex setting, the scheme has demonstrated to be a successful heuristic for solving combinatorial problems of different type. In this self-contained tutorial, we develop the convergence theory of projection algorithms within the framework of fixed point iterations, explain how to devise useful feasibility problem formulations, and demonstrate the application of the Douglas–Rachford method to said formulations. The paradigm is then illustrated on two concrete problems: a generalization of the “eight queens puzzle” known as the “(m, n)-queens problem”, and the problem of constructing a probability distribution with prescribed moments.

La Geometría Lineal es una asignatura obligatoria que se imparte en el tercer semestre del Grado en Matemáticas de la Universidad de Alicante. Dentro de los contenidos de esta asignatura se incluye una parte muy importante encaminada al estudio de las curvas cónicas (parábola, elipse e hipérbola), a su clasificación y al análisis de sus propiedades. La docencia de las cónicas se ha abordado usualmente desde los métodos tradicionales: desarrollo teórico-algebraico con exposición en la pizarra y posterior resolución de ejercicios relacionados. Por la propia naturaleza de las curvas cónicas, existen multitud de herramientas de tipo gráfico y computacional que pueden ayudar en el manejo, visualización y comprensión de las mismas. De entre todas las posibilidades disponibles, hemos optado por el software matemático (libre y multiplataforma) GeoGebra debido a su dinamismo, versatilidad y sencillez. En este trabajo de investigación presentamos nuestro principal objetivo, que es indagar sobre las posibles ventajas de la enseñanza de las cónicas utilizando dicho software, describiremos el procedimiento que hemos seguido exhibiendo algunas de las actividades que hemos desarrollado y, finalmente, analizaremos los resultados obtenidos concluyendo que la utilización de este software tan intuitivo se traduce en un aprendizaje más ágil y atractivo para el alumno.

La Geometría Lineal es una asignatura obligatoria que se imparte en el tercer semestre del Grado en Matemáticas de la Universidad de Alicante. Dentro de los contenidos de esta asignatura se incluye una parte muy importante encaminada al estudio de las curvas cónicas (parábola, elipse e hipérbola), a su clasificación y al análisis de sus propiedades. La docencia de las cónicas se ha abordado usualmente desde los métodos tradicionales: desarrollo teórico-algebraico con exposición en la pizarra y posterior resolución de ejercicios relacionados. Por la propia naturaleza de las curvas cónicas, existen multitud de herramientas de tipo gráfico y computacional que pueden ayudar en el manejo, visualización y comprensión de las mismas. De entre todas las posibilidades disponibles, hemos optado por el software matemático (libre y multiplataforma) GeoGebra debido a su dinamismo, versatilidad y sencillez. En este trabajo de investigación presentamos nuestro principal objetivo, que es indagar sobre las posibles ventajas de la enseñanza de las cónicas utilizando dicho software, describiremos el procedimiento que hemos seguido exhibiendo algunas de las actividades que hemos desarrollado y, finalmente, analizaremos los resultados obtenidos concluyendo que la utilización de este software tan intuitivo se traduce en un aprendizaje más ágil y atractivo para el alumno.

The averaged alternating modified reflections (AAMR) method is a projection algorithm for finding the closest point in the intersection of convex sets to any arbitrary point in a Hilbert space. This method can be seen as an adequate modification of the Douglas–Rachford method that yields a solution to the best approximation problem. In this paper, we consider the particular case of two subspaces in a Euclidean space. We obtain the rate of linear convergence of the AAMR method in terms of the Friedrichs angle between the subspaces and the parameters defining the scheme, by studying the linear convergence rates of the powers of matrices. We further optimize the value of these parameters in order to get the minimal convergence rate, which turns out to be better than the one of other projection methods. Finally, we provide some numerical experiments that demonstrate the theoretical results.

The averaged alternating modified reflections algorithm is a projection method for finding the closest point in the intersection of closed and convex sets to a given point in a Hilbert space. In this work, we generalize the scheme so that it can be used to compute the resolvent of the sum of two maximally monotone operators. This gives rise to a new splitting method, which is proved to be strongly convergent. A standard product space reformulation permits to apply the method for computing the resolvent of a finite sum of maximally monotone operators. Based on this, we propose two variants of such parallel splitting method.

We present the Douglas-Rachford algorithm as a successful heuristic for solving graph coloring problems. Given a set of colors, these types of problems consist in assigning a color to each node of a graph, in such a way that every pair of adjacent nodes are assigned with different colors. We formulate the graph coloring problem as an appropriate feasibility problem that can be effectively solved by the Douglas-Rachford algorithm, despite the nonconvexity arising from the combinatorial nature of the problem. Different modifications of the graph coloring problem and applications are also presented. The good performance of the method is shown in various computational experiments.

In this paper we present a new iterative projection method for finding the closest point in the intersection of convex sets to any arbitrary point in a Hilbert space. This method, termed AAMR for averaged alternating modified reflections, can be viewed as an adequate modification of the Douglas–Rachford method that yields a solution to the best approximation problem. Under a constraint qualification at the point of interest, we show strong convergence of the method. In fact, the so-called strong CHIP fully characterizes the convergence of the AAMR method for every point in the space. We report some promising numerical experiments where we compare the performance of AAMR against other projection methods for finding the closest point in the intersection of pairs of finite dimensional subspaces.

In this work, we propose an optimization approach for constructing various classes of circulant combinatorial designs that can be defined in terms of autocorrelation. The problem is formulated as a so-called feasibility problem having three sets, to which the Douglas–Rachford projection algorithm is applied. The approach is illustrated on three different classes of circulant combinatorial designs: circulant weighing matrices, D-optimal matrices of circulant type, and Hadamard matrices with two circulant cores. Furthermore, we explicitly construct two new circulant weighing matrices, a CW(126, 64) and a CW(198, 100), whose existence was previously marked as unresolved in the most recent version of Strassler’s table.