Pasar al contenido principal

OPTIMIZATION AND VARIATIONAL ANALYSIS: THEORY, ALGORITHMS AND COMPUTATIONAL EXPERIMENTATION

RYC-2013-13327

•
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 Incorporación
Convocatoria Ramón y Cajal
Año convocatoria 2013
Plan Estatal 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Unidad de gestión Secretaría de Estado de Educación, Formación Profesional y Universidades
Centro beneficiario UNIVERSIDAD DE ALICANTE
Identificador persistente http://dx.doi.org/10.13039/501100004837

Resultados relacionados

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

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

Global behavior of the Douglas–Rachford method for a nonconvex feasibility problem

  • Aragón Artacho, Francisco Javier
  • Borwein, Jonathan M.
  • Tam, Matthew K.
  • Aragón Artacho, Francisco Javier|||/items/1606bcd1-4dcb-4543-98d2-cba4400516f6
In recent times the Douglas–Rachford algorithm has been observed empirically to solve a variety of nonconvex feasibility problems including those of a combinatorial nature. For many of these problems current theory is not sufficient to explain this observed success and is mainly concerned with questions of local convergence. In this paper we analyze global behavior of the method for finding a point in the intersection of a half-space and a potentially non-convex set which is assumed to satisfy a well-quasi-ordering property or a property weaker than compactness. In particular, the special case in which the second set is finite is covered by our framework and provides a prototypical setting for combinatorial optimization problems.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

The cyclic Douglas–Rachford algorithm with r-sets-Douglas–Rachford operators

  • Aragón Artacho, Francisco Javier
  • Censor, Yair
  • Gibali, Aviv
  • Aragón Artacho, Francisco Javier|||/items/1606bcd1-4dcb-4543-98d2-cba4400516f6
The Douglas–Rachford (DR) algorithm is an iterative procedure that uses sequential reflections onto convex sets and which has become popular for convex feasibility problems. In this paper we propose a structural generalization that allows to use r-sets-DR operators in a cyclic fashion. We prove convergence and present numerical illustrations of the potential advantage of such operators with r>2 over the classical 2-sets-DR operators in a cyclic algorithm.
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.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Local convergence of the Levenberg–Marquardt method under Hölder metric subregularity

  • Ahookhosh, Masoud
  • Aragón Artacho, Francisco Javier
  • Fleming, Ronan M.T.
  • Vuong, Phan T.
  • Aragón Artacho, Francisco Javier|||/items/1606bcd1-4dcb-4543-98d2-cba4400516f6
We describe and analyse Levenberg–Marquardt methods for solving systems of nonlinear equations. More specifically, we propose an adaptive formula for the Levenberg–Marquardt parameter and analyse the local convergence of the method under Hölder metric subregularity of the function defining the equation and Hölder continuity of its gradient mapping. Further, we analyse the local convergence of the method under the additional assumption that the Łojasiewicz gradient inequality holds. We finally report encouraging numerical results confirming the theoretical findings for the problem of computing moiety conserved steady states in biochemical reaction networks. This problem can be cast as finding a solution of a system of nonlinear equations, where the associated mapping satisfies the Łojasiewicz gradient inequality assumption.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

The Boosted Difference of Convex Functions Algorithm for Nonsmooth Functions

  • Aragón Artacho, Francisco Javier
  • Vuong, Phan T.
  • Aragón Artacho, Francisco Javier|||/items/1606bcd1-4dcb-4543-98d2-cba4400516f6
The boosted difference of convex functions algorithm (BDCA) was recently proposed for minimizing smooth difference of convex (DC) functions. BDCA accelerates the convergence of the classical difference of convex functions algorithm (DCA) thanks to an additional line search step. The purpose of this paper is twofold. First, we show that this scheme can be generalized and successfully applied to certain types of nonsmooth DC functions, namely, those that can be expressed as the difference of a smooth function and a possibly nonsmooth one. Second, we show that there is complete freedom in the choice of the trial step size for the line search, which is something that can further improve its performance. We prove that any limit point of the BDCA iterative sequence is a critical point of the problem under consideration and that the corresponding objective value is monotonically decreasing and convergent. The global convergence and convergence rate of the iterations are obtained under the Kurdyka--Łojasiewicz property. Applications and numerical experiments for two problems in data science are presented, demonstrating that BDCA outperforms DCA. Specifically, for the minimum sum-of-squares clustering problem, BDCA was on average 16 times faster than DCA, and for the multidimensional scaling problem, BDCA was 3 times faster than DCA.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Finding magic squares with Douglas—Rachford algorithm

  • Aragón Artacho, Francisco Javier
  • Segura Martínez, Paula
  • Aragón Artacho, Francisco Javier|||/items/1606bcd1-4dcb-4543-98d2-cba4400516f6
In this expository paper, we show how to use the Douglas—Rachford algorithm as a successful heuristic for finding magic squares. The Douglas—Rachford algorithm is an iterative projection method for solving feasibility problems. Although its convergence is only guaranteed in the convex setting, the algorithm has been successfully applied to a number of similar nonconvex problems, such as solving Sudoku puzzles. We present two formulations of the nonconvex feasibility problem of finding magic squares, which are inspired by those of Sudoku, and test the Douglas—Rachford algorithm on them.