Pasar al contenido principal

FUNDAMENTOS, METODOS Y APLICACIONES DE LA OPTIMIZACION CONTINUA

MTM2014-59179-C2-1-P

•
Nombre agencia financiadora Ministerio de Economía y Competitividad
Acrónimo agencia financiadora MINECO
Programa Programa Estatal de Fomento de la Investigación Científica y Técnica de Excelencia
Subprograma Subprograma Estatal de Generación de Conocimiento
Convocatoria Proyectos de I+D (Excelencia / Generación de Conocimiento)
Año convocatoria 2014
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/501100003329

Resultados relacionados

Resultados totales (Incluyendo duplicados): 37
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 LFM data qualification in convex multiobjetive semi-infinite programming

  • Goberna, Miguel A.
  • Rodríguez Álvarez, Margarita
  • Vera de Serio, Virginia N.
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
  • Rodríguez Álvarez, Margarita|||/items/81d9e7c1-c8aa-48b0-b6c7-5a4bd3e26327
Given a semi-infinite multiobjective convex problem we introduce a data qualification that enables to characterize optimality in terms of Lagrange multipliers. We show that this condition characterizes the weak efficient solutions through the weak Karush-Kuhn-Tucker (KKT) condition, and identifies the proper efficient solutions through the strong KKT condition. We also address the question in relation to a gap function.
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)

A Uniform Approach to Hölder Calmness of Subdifferentials

  • Beer, Gerald
  • Cánovas Cánovas, María Josefa
  • López Cerdá, Marco A.
  • Parra López, Juan
For finite-valued convex functions f defined on the n-dimensional Euclidean space, we are interested in the set-valued mapping assigning to each pair (f, x) the subdifferential of f at x. Our approach is uniform with respect to f in the sense that it involves pairs of functions close enough to each other, but not necessarily around a nominal function. More precisely, we provide lower and upper estimates, in terms of Hausdorff excesses, of the subdifferential of one of such functions at a nominal point in terms of the subdifferential of nearby functions in a ball centered in such a point. In particular, we obtain the (1/2) - Hölder calmness of our mapping at a nominal pair (f, x) under the assumption that the subdifferential mapping viewed as a set-valued mapping from Rn to Rn with f fixed is calm at each point of {x} X ∂f(x).
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)

Valadier-like Formulas for the Supremum Function. II: The Compactly Indexed Case

  • Correa, Rafael
  • Hantoute, Abderrahim
  • López Cerdá, Marco A.
  • Hantoute, Abderrahim|||/items/257fa651-9a93-4e26-b88e-d90594995ecc
Continuing part I of this article of the same authors [Valadier-like formulas for the supremum function I, J. Convex Analysis 25(4) (2018) 1253--1278], we focus now on the compactly indexed case. We assume that the index set is compact and that the data functions are upper semicontinuous with respect to the index variable (actually, this assumption will only affect the set of ε-active indices at the reference point). As in the previous work, we do not require any continuity assumption with respect to the decision variable. The current compact setting gives rise to more explicit formulas, which only involve subdifferentials at the reference point of active data functions. Other formulas are derived under weak continuity assumptions. These formulas reduce to the characterization given by M. Valadier [Sous-différentiels d'une borne supérieure et d'une somme continue de fonctions convexes, C. R. Acad. Sci. Paris, Sér. A-B Math. 268 (1969) 39--42; Theorem 2] when the supremum function is continuous.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Optimality Conditions in DC-Constrained Mathematical Programming Problems

  • Correa, Rafael
  • López Cerdá, Marco A.
  • Pérez-Aros, Pedro
This paper provides necessary and sufficient optimality conditions for abstract-constrained mathematical programming problems in locally convex spaces under new qualification conditions. Our approach exploits the geometrical properties of certain mappings, in particular their structure as difference of convex functions, and uses techniques of generalized differentiation (subdifferential and coderivative). It turns out that these tools can be used fruitfully out of the scope of Asplund spaces. Applications to infinite, stochastic and semi-definite programming are developed in separate sections.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

New Farkas-Type Results for Vector-Valued Functions: A Non-abstract Approach

  • Dinh, Nguyen
  • Goberna, Miguel A.
  • Long, Dang H.
  • López Cerdá, Marco A.
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
This paper provides new Farkas-type results characterizing the inclusion of a given set, called contained set, into a second given set, called container set, both of them are subsets of some locally convex space, called decision space. The contained and the container sets are described here by means of vector functions from the decision space to other two locally convex spaces which are equipped with the partial ordering associated with given convex cones. These new Farkas lemmas are obtained via the complete characterization of the conic epigraphs of certain conjugate mappings which constitute the core of our approach. In contrast with a previous paper of three of the authors (Dinh et al. in J Optim Theory Appl 173:357–390, 2017), the aimed characterizations of the containment are expressed here in terms of the data.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Best Approximate Solutions of Inconsistent Linear Inequality Systems

  • Goberna, Miguel A.
  • Hiriart-Urruty, Jean-Baptiste
  • López Cerdá, Marco A.
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
This paper is intended to characterize three types of best approximate solutions for inconsistent linear inequality systems with an arbitrary number of constraints. It also gives conditions guaranteeing the existence of best uniform solutions and discusses potential applications.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Valadier-like Formulas for the Supremum Function I

  • Correa, Rafael
  • Hantoute, Abderrahim
  • López Cerdá, Marco A.
  • Hantoute, Abderrahim|||/items/257fa651-9a93-4e26-b88e-d90594995ecc
We generalize and improve the original characterization given by M. Valadier [Sous-différentiels d'une borne supérieure et d'une somme continue de fonctions convexes, C. R. Acad. Sci. Paris, Sér. A-B Math. 268 (1969) 39--42; Theorem 1] of the subdifferential of the pointwise supremum of convex functions, involving the subdifferentials of the data functions at nearby points. We remove the continuity assumption made in that work and obtain a general formula for such a subdifferential. In particular, when the supremum is continuous at some point of its domain, but not necessarily at the reference point, we get a simpler version which gives rise to the Valadier formula. Our starting result is the characterization given by A. Hantoute, M. A. López and C. Zalinescu [Subdifferential calculus rules in convex analysis: a unifying approach via pointwise supremum functions, SIAM J. Optim. 19 (2008) 863--882; Theorem 4], which uses the ε-subdifferential at the reference point.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

New duality results for evenly convex optimization problems

  • Fajardo, Maria Dolores
  • Grad, Sorin-Mihai
  • Vidal, José
  • Fajardo, Maria Dolores|||/items/f4594791-3589-4782-bb7a-5e213efccaf8
We present new results on optimization problems where the involved functions are evenly convex. By means of a generalized conjugation scheme and the perturbation theory introduced by Rockafellar, we propose an alternative dual problem for a general optimization one defined on a separated locally convex topological space. Sufficient conditions for converse and total duality involving the even convexity of the perturbation function and c-subdifferentials are given. Formulae for the c-subdifferential and biconjugate of the objective function of a general optimization problem are provided, too. We also characterize the total duality by means of the saddle-point theory for a notion of Lagrangian adapted to the considered framework.
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)

Moreau-Rockafellar-Type Formulas for the Subdifferential of the Supremum Function

  • Correa, Rafael
  • Hantoute, Abderrahim
  • López Cerdá, Marco A.
  • Hantoute, Abderrahim|||/items/257fa651-9a93-4e26-b88e-d90594995ecc
We characterize the subdifferential of the supremum function of finitely and infinitely indexed families of convex functions. The main contribution of this paper consists of providing formulas for such a subdifferential under weak continuity assumptions. The resulting formulas are given in terms of the exact subdifferential of the data functions at the reference point, and not at nearby points as in [Valadier, C. R. Math. Acad. Sci. Paris, 268 (1969), pp. 39--42]. We also derive new Fritz John- and KKT-type optimality conditions for semi-infinite convex optimization, omitting the continuity/closedness assumptions in [Dinh et al., ESAIM Control Optim. Calc. Var., 13 (2007), pp. 580--597]. When the family of functions is finite, we use continuity conditions concerning only the active functions, and not all the data functions as in [Rockafellar, Proc. Lond. Math. Soc. (3), 39 (1979), pp. 331--355; Volle, Acta Math. Vietnam., 19 (1994), pp. 137--148].
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Calmness of partially perturbed linear systems with an application to the central path

  • Cánovas Cánovas, María Josefa
  • Hall, Julian A.J.
  • López Cerdá, Marco A.
  • Parra López, Juan
In this paper we develop point-based formulas for the calmness modulus of the feasible set mapping in the context of linear inequality systems with a fixed abstract constraint and (partially) perturbed linear constraints. The case of totally perturbed linear systems was previously analyzed in [Cánovas MJ, López MA, Parra J, et al. Calmness of the feasible set mapping for linear inequality systems. Set-Valued Var Anal. 2014;22:375–389, Section 5]. We point out that the presence of such an abstract constraint yields the current paper to appeal to a notable different methodology with respect to previous works on the calmness modulus in linear programming. The interest of this model comes from the fact that partially perturbed systems naturally appear in many applications. As an illustration, the paper includes an example related to the classical central path construction. In this example we consider a certain feasible set mapping whose calmness modulus provides a measure of the convergence of the central path. Finally, we underline the fact that the expression for the calmness modulus obtained in this paper is (conceptually) implementable as far as it only involves the nominal data.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Necessary and Sufficient Conditions for Strong Fenchel–Lagrange Duality via a Coupling Conjugation Scheme

  • Fajardo, Maria Dolores
  • Vidal, José
  • Fajardo, Maria Dolores|||/items/f4594791-3589-4782-bb7a-5e213efccaf8
Given a general primal problem and its Fenchel–Lagrange dual one, which is obtained by using a conjugation scheme based on coupling functions and the perturbational approach, the aim in this work is to establish conditions under which strong duality can be guaranteed. To this purpose, even convexity and properness are a compulsory requirement over the involved functions in the primal problem. Furthermore, two closedness-type regularity conditions and a characterization for strong duality are derived.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

On Finite Linear Systems Containing Strict Inequalities

  • Rodríguez Álvarez, Margarita
  • Vicente-Pérez, José
  • Rodríguez Álvarez, Margarita|||/items/81d9e7c1-c8aa-48b0-b6c7-5a4bd3e26327
  • Vicente-Pérez, José|||/items/7fad998a-2853-4a32-852d-d0c16df35750
This paper deals with linear systems containing finitely many weak and/or strict inequalities, whose solution sets are referred to as evenly convex polyhedral sets. The classical Motzkin theorem states that every (closed and convex) polyhedron is the Minkowski sum of a convex hull of finitely many points and a finitely generated cone. In this sense, similar representations for evenly convex polyhedra have been recently given by using the standard version for classical polyhedra. In this work, we provide a new dual tool that completely characterizes finite linear systems containing strict inequalities and it constitutes the key for obtaining a generalization of Motzkin theorem for evenly convex polyhedra.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Stability of the Duality Gap in Linear Optimization

  • Goberna, Miguel A.
  • Ridolfi, Andrea Beatriz
  • Vera de Serio, Virginia N.
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
In this paper we consider the duality gap function g that measures the difference between the optimal values of the primal problem and of the dual problem in linear programming and in linear semi-infinite programming. We analyze its behavior when the data defining these problems may be perturbed, considering seven different scenarios. In particular we find some stability results by proving that, under mild conditions, either the duality gap of the perturbed problems is zero or + ∞ around the given data, or g has an infinite jump at it. We also give conditions guaranteeing that those data providing a finite duality gap are limits of sequences of data providing zero duality gap for sufficiently small perturbations, which is a generic result.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Isolated Calmness and Sharp Minima via Hölder Graphical Derivatives

  • Kruger, Alexander Y.
  • López Cerdá, Marco A.
  • Yang, Xiaoqi
  • Zhu, Jiangxing
The paper utilizes Hölder graphical derivatives for characterizing Hölder strong subregularity, isolated calmness and sharp minimum. As applications, we characterize Hölder isolated calmness in linear semi-infinite optimization and Hölder sharp minimizers of some penalty functions for constrained optimization.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Optimality conditions in convex multiobjective SIP

  • Goberna, Miguel A.
  • Kanzi, Nader
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
The purpose of this paper is to characterize the weak efficient solutions, the efficient solutions, and the isolated efficient solutions of a given vector optimization problem with finitely many convex objective functions and infinitely many convex constraints. To do this, we introduce new and already known data qualifications (conditions involving the constraints and/or the objectives) in order to get optimality conditions which are expressed in terms of either Karusk–Kuhn–Tucker multipliers or a new gap function associated with the given problem.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Farkas-Type Results for Vector-Valued Functions with Applications

  • Dinh, Nguyen
  • Goberna, Miguel A.
  • López Cerdá, Marco A.
  • Mo, Tran Hong
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
The main purpose of this paper consists of providing characterizations of the inclusion of the solution set of a given conic system posed in a real locally convex topological space into a variety of subsets of the same space defined by means of vector-valued functions. These Farkas-type results are used to derive characterizations of the weak solutions of vector optimization problems (including multiobjective and scalar ones), vector variational inequalities, and vector equilibrium problems.
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)

A Polarity Theory for Sets of Desirable Gambles

  • Benavoli, Alessio
  • Facchini, Alessandro
  • Zaffalon, Marco
  • Vicente-Pérez, José
  • Vicente-Pérez, José|||/items/7fad998a-2853-4a32-852d-d0c16df35750
Coherent sets of almost desirable gambles and credal sets are known to be equivalent models. That is, there exists a bijection between the two collections of sets preserving the usual operations, e.g. conditioning. Such a correspondence is based on the polarity theory for closed convex cones. Learning from this simple observation, in this paper we introduce a new (lexicographic) polarity theory for general convex cones and then we apply it in order to establish an analogous correspondence between coherent sets of desirable gambles and convex sets of lexicographic probabilities.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Hölder Error Bounds and Hölder Calmness with Applications to Convex Semi-infinite Optimization

  • Kruger, Alexander Y.
  • López Cerdá, Marco A.
  • Yang, Xiaoqi
  • Zhu, Jiangxing
Using techniques of variational analysis, necessary and sufficient subdifferential conditions for Hölder error bounds are investigated and some new estimates for the corresponding modulus are obtained. As an application, we consider the setting of convex semi-infinite optimization and give a characterization of the Hölder calmness of the argmin mapping in terms of the level set mapping (with respect to the objective function) and a special supremum function. We also estimate the Hölder calmness modulus of the argmin mapping in the framework of linear programming.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Lipschitz modulus of linear and convex inequality systems with the Hausdorff metric

  • Beer, Gerald
  • Cánovas Cánovas, María Josefa
  • López Cerdá, Marco A.
  • Parra López, Juan
This paper analyzes the Lipschitz behavior of the feasible set mapping associated with linear and convex inequality systems in Rn. To start with, we deal with the parameter space of linear (finite/semi-infinite) systems identified with the corresponding sets of coefficient vectors, which are assumed to be closed subsets of Rn+1. In this framework the size of perturbations is measured by means of the (extended) Hausdorff distance. A direct antecedent, extensively studied in the literature, comes from considering the parameter space of all linear systems with a fixed index set, T, where the Chebyshev (extended) distance is used to measure perturbations. In the present work we propose an appropriate indexation strategy which allows us to establish the equality of the Lipschitz moduli of the feasible set mappings in both parametric contexts, as well as to benefit from existing results in the Chebyshev setting for transferring them to the Hausdorff one. In a second stage, the possibility of perturbing directly the set of coefficient vectors of a linear system leads to new contributions on the Lipschitz behavior of convex systems via linearization techniques.
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)

Convexity and closedness in stable robust duality

  • Dinh, Nguyen
  • Goberna, Miguel A.
  • López Cerdá, Marco A.
  • Volle, Michel
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
The paper deals with optimization problems with uncertain constraints and linear perturbations of the objective function, which are associated with given families of perturbation functions whose dual variable depends on the uncertainty parameters. More in detail, the paper provides characterizations of stable strong robust duality and stable robust duality under convexity and closedness assumptions. The paper also reviews the classical Fenchel duality of the sum of two functions by considering a suitable family of perturbation functions.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Perturbation of error bounds

  • Kruger, Alexander Y.
  • López Cerdá, Marco A.
  • Théra, Michel
Our aim in the current article is to extend the developments in Kruger et al. (SIAM J Optim 20(6):3280–3296, 2010. doi: 10.1137/100782206) and, more precisely, to characterize, in the Banach space setting, the stability of the local and global error bound property of inequalities determined by lower semicontinuous functions under data perturbations. We propose new concepts of (arbitrary, convex and linear) perturbations of the given function defining the system under consideration, which turn out to be a useful tool in our analysis. The characterizations of error bounds for families of perturbations can be interpreted as estimates of the ‘radius of error bounds’. The definitions and characterizations are illustrated by examples.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Set-Valued Evenly Convex Functions: Characterizations and C-Conjugacy

  • Fajardo, Maria Dolores
  • Fajardo, Maria Dolores|||/items/f4594791-3589-4782-bb7a-5e213efccaf8
In this work we deal with set-valued functions with values in the power set of a separated locally convex space where a nontrivial pointed convex cone induces a partial order relation. A set-valued function is evenly convex if its epigraph is an evenly convex set, i.e., it is the intersection of an arbitrary family of open half-spaces. In this paper we characterize evenly convex set-valued functions as the pointwise supremum of its set-valued e-affine minorants. Moreover, a suitable conjugation pattern will be developed for these functions, as well as the counterpart of the biconjugation Fenchel-Moreau theorem.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Recent contributions to linear semi-infinite optimization: an update

  • Goberna, Miguel A.
  • López Cerdá, Marco A.
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
This paper reviews the state-of-the-art in the theory of deterministic and uncertain linear semi-infinite optimization, presents some numerical approaches to this type of problems, and describes a selection of recent applications in a variety of fields. Extensions to related optimization areas, as convex semi-infinite optimization, linear infinite optimization, and multi-objective linear semi-infinite optimization, are also commented.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Recent contributions to linear semi-infinite optimization

  • Goberna, Miguel A.
  • López Cerdá, Marco A.
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
This paper reviews the state-of-the-art in the theory of deterministic and uncertain linear semi-infinite optimization, presents some numerical approaches to this type of problems, and describes a selection of recent applications in a variety of fields. Extensions to related optimization areas, as convex semi-infinite optimization, linear infinite optimization, and multi-objective linear semi-infinite optimization, are also commented.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

A Unifying Approach to Robust Convex Infinite Optimization Duality

  • Dinh, Nguyen
  • Goberna, Miguel A.
  • López Cerdá, Marco A.
  • Volle, Michel
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
This paper considers an uncertain convex optimization problem, posed in a locally convex decision space with an arbitrary number of uncertain constraints. To this problem, where the uncertainty only affects the constraints, we associate a robust (pessimistic) counterpart and several dual problems. The paper provides corresponding dual variational principles for the robust counterpart in terms of the closed convexity of different associated cones.
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.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Radius of robust feasibility formulas for classes of convex programs with uncertain polynomial constraints

  • Goberna, Miguel A.
  • Jeyakumar, Vaithilingam
  • Li, Guoyin
  • Linh, Nguyen
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
The radius of robust feasibility of a convex program with uncertain constraints gives a value for the maximal ‘size’ of an uncertainty set under which robust feasibility can be guaranteed. This paper provides an upper bound for the radius for convex programs with uncertain convex polynomial constraints and exact formulas for convex programs with SOS-convex polynomial constraints (or convex quadratic constraints) under affine data uncertainty. These exact formulas allow the radius to be computed by commonly available software.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

A comparative note on the relaxation algorithms for the linear semi-infinite feasibility problem

  • Ferrer, Alberto
  • Goberna, Miguel A.
  • González-Gutiérrez, Enrique
  • Todorov, Maxim I.
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
The problem (LFP) of finding a feasible solution to a given linear semi-infinite system arises in different contexts. This paper provides an empirical comparative study of relaxation algorithms for (LFP). In this study we consider, together with the classical algorithm, implemented with different values of the fixed parameter (the step size), a new relaxation algorithm with random parameter which outperforms the classical one in most test problems whatever fixed parameter is taken. This new algorithm converges geometrically to a feasible solution under mild conditions. The relaxation algorithms under comparison have been implemented using the extended cutting angle method for solving the global optimization subproblems.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Towards Supremum-Sum Subdifferential Calculus Free of Qualification Conditions

  • Correa, Rafael
  • Hantoute, Abderrahim
  • López Cerdá, Marco A.
  • Hantoute, Abderrahim|||/items/257fa651-9a93-4e26-b88e-d90594995ecc
We give a formula for the subdifferential of the sum of two convex functions where one of them is the supremum of an arbitrary family of convex functions. This is carried out under a weak assumption expressing a natural relationship between the lower semicontinuous envelopes of the data functions in the domain of the sum function. We also provide a new rule for the subdifferential of the sum of two convex functions, which uses a strategy of augmenting the involved functions. The main feature of our analysis is that no continuity-type condition is required. Our approach allows us to unify, recover, and extend different results in the recent literature.
Dipòsit Digital de Documents de la UAB
Publicación Artículo científico (JournalArticle)

The doctrinal paradox, comparison of decision rules in a probabilistic framework

  • Alabert, Aureli|||0000-0002-6575-5661
  • Farré, Mercè|||0000-0002-4184-5160
The doctrinal paradox is analysed from a probabilistic point of view assuming a simple parametric model for the committee's behaviour. The well known premise-based and conclusion-based majority rules are compared in this model, by means of the concepts of false positive rate (FPR), false negative rate (FNR) and Receiver Operating Characteristics (ROC) space. We introduce also a new rule that we call path-based, which is somehow halfway between the other two. Under our model assumptions, the premise-based rule is shown to be the best of the three according to an optimality criterion based in ROC maps, for all values of the model parameters (committee size and competence of its members), when equal weight is given to FPR and FNR. We extend this result to prove that, for unequal weights of FNR and FPR, the relative goodness of the rules depends on the values of the competence and the weights, in a way which is precisely described. The results are illustrated with some numerical examples.