Pasar al contenido principal

FUNDAMENTOS, METODOS Y APLICACIONES DE LA OPTIMIZACION CONTINUA

BES-2015-073360

•
Nombre agencia financiadora Ministerio de Ciencia e Innovación
Acrónimo agencia financiadora MICINN
Programa Programa Estatal de Promoción del Talento y su Empleabilidad en I+D+i
Subprograma Subprograma Estatal de Formación
Convocatoria Contratos Predoctorales
Año convocatoria 2015
Plan Estatal 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Unidad de gestión Dirección General de Investigación Científica y Técnica
Centro beneficiario UNIVERSIDAD DE ALICANTE
Identificador persistente http://dx.doi.org/10.13039/501100004837

Resultados relacionados

Resultados totales (Incluyendo duplicados): 3
Encontrada(s) 1 página(s)

RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

The Douglas–Rachford algorithm for convex and nonconvex feasibility problems

  • Aragón Artacho, Francisco Javier
  • Campoy, Rubén
  • Tam, Matthew K.
  • Aragón Artacho, Francisco Javier|||/items/1606bcd1-4dcb-4543-98d2-cba4400516f6
  • Campoy, Rubén|||/items/21264c6a-ecd6-4c42-bdfb-61ec73f47d5c
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.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

An enhanced formulation for solving graph coloring problems with the Douglas–Rachford algorithm

  • Aragón Artacho, Francisco Javier
  • Campoy, Rubén
  • Elser, Veit
  • Aragón Artacho, Francisco Javier|||/items/1606bcd1-4dcb-4543-98d2-cba4400516f6
  • Campoy, Rubén|||/items/21264c6a-ecd6-4c42-bdfb-61ec73f47d5c
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.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Using Positive Spanning Sets to Achieve d-Stationarity with the Boosted DC Algorithm

  • Aragón Artacho, Francisco Javier
  • Campoy, Rubén
  • Vuong, Phan T.
  • Aragón Artacho, Francisco Javier|||/items/1606bcd1-4dcb-4543-98d2-cba4400516f6
  • Campoy, Rubén|||/items/21264c6a-ecd6-4c42-bdfb-61ec73f47d5c
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.