Pasar al contenido principal

CONVEX OPTIMIZATION WITH UNCERTAIN DATA: ROBUSTNESS, REGULARITY, AND APPLICATIONS

MTM2011-29064-C03-02

•
Nombre agencia financiadora Ministerio de Ciencia e Innovación
Acrónimo agencia financiadora MICINN
Programa Programa Nacional de Proyectos de Investigación Fundamental
Subprograma Subprograma de Proyectos de Investigación Fundamental no Orientada
Convocatoria Proyectos I+D
Año convocatoria 2011
Plan Estatal 2008-2011 Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica
Unidad de gestión Subdirección General de Proyectos de Investigación
Centro beneficiario UNIVERSIDAD DE ALICANTE
Identificador persistente http://dx.doi.org/10.13039/501100004837

Resultados relacionados

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

Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

A BRILS metaheuristic for non-smooth flow-shop problems with failure-risk costs

  • Ferrer, Alberto
  • Guimarans, Daniel
  • Ramalhinho-Lourenço, Helena
  • Juan, Angel A.
This paper analyzes a realistic variant of the Permutation Flow-Shop Problem (PFSP) by considering a non-smooth objective function that takes into account not only the traditional makespan cost but also failure-risk costs due to uninterrupted operation of machines. After completing a literature review on the issue, the paper formulates an original mathematical model to describe this new PFSP variant. Then, a Biased-Randomized Iterated Local Search (BRILS) algorithm is proposed as an efficient solving approach. An oriented (biased) random behavior is introduced in the well-known NEH heuristic to generate an initial solution. From this initial solution, the algorithm is able to generate a large number of alternative good solutions without requiring a complex setting of parameters. The relative simplicity of our approach is particularly useful in the presence of non-smooth objective functions, for which exact optimization methods may fail to reach their full potential. The gains of considering failure-risk costs during the exploration of the solution space are analyzed throughout a series of computational experiments. To promote reproducibility, these experiments are based on a set of traditional benchmark instances. Moreover, the performance of the proposed algorithm is compared against other state-of-the-art metaheuristic approaches, which have been conveniently adapted to consider failure-risk costs during the solving process. The proposed BRILS approach can be easily extended to other combinatorial optimization problems with similar non-smooth objective functions., This research has been partially supported by the Spanish Ministry of Economy and Competitiveness, projects MTM2011-29064-C03-02, MTM2014-59179-C2-01 & TRA2013-48180-C3-P, and FEDER. NICTA is funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Even convexity, subdifferentiability, and Γ-regularization in general topological vector spaces

  • Vicente-Pérez, José
  • Volle, Michel
  • Vicente-Pérez, José|||/items/7fad998a-2853-4a32-852d-d0c16df35750
In this paper we provide new results on even convexity and extend some others to the framework of general topological vector spaces. We first present a characterization of the even convexity of an extended real-valued function at a point. We then establish the links between even convexity and subdifferentiability and the Γ-regularization of a given function. Consequently, we derive a sufficient condition for strong duality fulfillment in convex optimization problems.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Calmness modulus of linear semi-infinite programs

  • Cánovas Cánovas, María Josefa
  • Kruger, Alexander Y.
  • López Cerdá, Marco A.
  • Parra López, Juan
  • Théra, Michel
Our main goal is to compute or estimate the calmness modulus of the argmin mapping of linear semi-infinite optimization problems under canonical perturbations, i.e., perturbations of the objective function together with continuous perturbations of the right-hand side of the constraint system (with respect to an index ranging in a compact Hausdorff space). Specifically, we provide a lower bound on the calmness modulus for semi-infinite programs with unique optimal solution which turns out to be the exact modulus when the problem is finitely constrained. The relationship between the calmness of the argmin mapping and the same property for the (sub)level set mapping (with respect to the objective function), for semi-infinite programs and without requiring the uniqueness of the nominal solution, is explored, too, providing an upper bound on the calmness modulus of the argmin mapping. When confined to finitely constrained problems, we also provide a computable upper bound as it only relies on the nominal data and parameters, not involving elements in a neighborhood. Illustrative examples are provided.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Constraint qualifications in linear vector semi-infinite optimization

  • Goberna, Miguel A.
  • Guerra Vázquez, Francisco
  • Todorov, Maxim I.
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
Linear vector semi-infinite optimization deals with the simultaneous minimization of finitely many linear scalar functions subject to infinitely many linear constraints. This paper provides characterizations of the weakly efficient, efficient, properly efficient and strongly efficient points in terms of cones involving the data and Karush–Kuhn–Tucker conditions. The latter characterizations rely on different local and global constraint qualifications. The global constraint qualifications are illustrated on a collection of selected applications.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Modified Lagrangian duality for the supremum of convex functions

  • Goberna, Miguel A.
  • López Cerdá, Marco A.
  • Volle, Michel
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
In this paper we associate with the problem (P) consisting of minimizing the supremum h of a family of extended real-valued convex functions on a given closed convex set C a modified Lagrange dual problem (D). Exploiting recent developments of the authors on convex duality, we provide min-sup and inf-max duality theorems for the pair (P)-(D), characterize the subdifferentials of the objective function g of the reformulation of (P) as an unconstrained problem (nothing else than the sum of h with the indicator of C) and its conjugate g^{?}, and give an explicit expression for the optimal set of (P).
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Robust optimization revisited via robust vector Farkas lemmas

  • Dinh, Nguyen
  • Goberna, Miguel A.
  • López Cerdá, Marco A.
  • Mo, Tran Hong
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
This paper provides characterizations of the weakly minimal elements of vector optimization problems and the global minima of scalar optimization problems posed on locally convex spaces whose objective functions are deterministic while the uncertain constraints are treated under the robust (or risk-averse) approach, i.e. requiring the feasibility of the decisions to be taken for any possible scenario. To get these optimality conditions we provide Farkas-type results characterizing the inclusion of the robust feasible set into the solution set of some system involving the objective function and possibly uncertain parameters. In the particular case of scalar convex optimization problems, we characterize the optimality conditions in terms of the convexity and closedness of an associated set regarding a suitable point.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

The Voronoi inverse mapping

  • Goberna, Miguel A.
  • Martínez Legaz, Juan Enrique
  • Vera de Serio, Virginia N.
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
Given an arbitrary set T in the Euclidean space whose elements are called sites, and a particular site s, the Voronoi cell of s , denoted by VT(s)VT(s), consists of all points closer to s than to any other site. The Voronoi mapping of s , denoted by ψsψs, associates to each set T∋sT∋s the Voronoi cell VT(s)VT(s) of s w.r.t. T . These Voronoi cells are solution sets of linear inequality systems, so they are closed convex sets. In this paper we study the Voronoi inverse problem consisting in computing, for a given closed convex set F∋sF∋s, the family of sets T∋sT∋s such that ψs(T)=Fψs(T)=F. More in detail, the paper analyzes relationships between the elements of this family, ψs−1(F), and the linear representations of F , provides explicit formulas for maximal and minimal elements of ψs−1(F), and studies the closure operator that assigns, to each closed set T containing s , the largest element of ψs−1(F), where F=VT(s)F=VT(s).
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

On Evenly Convex Sets and Functions

  • 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
A subset of R^n is said to be evenly convex (e-convex, in breaf) if it is the intersection of some family (possibly empty) of open halfspaces. In this paper, we collect some published results which show that this large class of convex sets enjoys a lot of the well-known properties of the subclass of closed convex sets. We also consider functions whose epigraphs are e-convex sets, the so-called e-convex functions, and we show the main properties of this class of convex functions that contains the important class of lower semicontinuous convex functions.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Primal Attainment in Convex Infinite Optimization Duality

  • Goberna, Miguel A.
  • López Cerdá, Marco A.
  • Volle, Michel
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
This article provides results guarateeing that the optimal value of a given convex infinite optimization problem and its corresponding surrogate Lagrangian dual coincide and the primal optimal value is attainable. The conditions ensuring converse strong Lagrangian (in short, minsup) duality involve the weakly-inf-(locally) compactness of suitable functions and the linearity or relative closedness of some sets depending on the data. Applications are given to different areas of convex optimization, including an extension of the Clark-Duffin Theorem for ordinary convex programs.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Robust SOS-convex polynomial optimization problems: exact SDP relaxations

  • Jeyakumar, Vaithilingam
  • Li, Guoyin
  • Vicente-Pérez, José
  • Vicente-Pérez, José|||/items/7fad998a-2853-4a32-852d-d0c16df35750
This paper studies robust solutions and semidefinite linear programming (SDP) relaxations of a class of convex polynomial optimization problems in the face of data uncertainty. The class of convex optimization problems, called robust SOS-convex polynomial optimization problems, includes robust quadratically constrained convex optimization problems and robust separable convex polynomial optimization problems. It establishes sums-of-squares polynomial representations characterizing robust solutions and exact SDP-relaxations of robust SOS-convex polynomial optimization problems under various commonly used uncertainty sets. In particular, the results show that the polytopic and ellipsoidal uncertainty sets, that allow second-order cone re-formulations of robust quadratically constrained optimization problems, continue to permit exact SDP-relaxations for a broad class of robust SOS-convex polynomial optimization problems.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Motzkin decomposition of closed convex sets via truncation

  • Goberna, Miguel A.
  • Iusem, Alfredo Noel
  • Martínez Legaz, Juan Enrique
  • Todorov, Maxim I.
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
A nonempty set F is called Motzkin decomposable when it can be expressed as the Minkowski sum of a compact convex set C with a closed convex cone D. In that case, the sets C and D are called compact and conic components of F. This paper provides new characterizations of the Motzkin decomposable sets involving truncations of F (i.e., intersections of FF with closed halfspaces), when F contains no lines, and truncations of the intersection F̂ of F with the orthogonal complement of the lineality of F, otherwise. In particular, it is shown that a nonempty closed convex set F is Motzkin decomposable if and only if there exists a hyperplane H parallel to the lineality of F such that one of the truncations of F̂ induced by H is compact whereas the other one is a union of closed halflines emanating from H. Thus, any Motzkin decomposable set F can be expressed as F=C+D, where the compact component C is a truncation of F̂. These Motzkin decompositions are said to be of type T when F contains no lines, i.e., when C is a truncation of F. The minimality of this type of decompositions is also discussed.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Lagrange Duality for Evenly Convex Optimization Problems

  • Fajardo, Maria Dolores
  • Rodríguez Álvarez, Margarita
  • Vidal, José
  • Fajardo, Maria Dolores|||/items/f4594791-3589-4782-bb7a-5e213efccaf8
  • Rodríguez Álvarez, Margarita|||/items/81d9e7c1-c8aa-48b0-b6c7-5a4bd3e26327
An evenly convex function on a locally convex space is an extended real-valued function, whose epigraph is the intersection of a family of open halfspaces. In this paper, we consider an infinite-dimensional optimization problem, for which both objective function and constraints are evenly convex, and we recover the classical Lagrange dual problem for it, via perturbational approach. The aim of the paper was to establish regularity conditions for strong duality between both problems, formulated in terms of even convexity.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Calmness of the Feasible Set Mapping for Linear Inequality Systems

  • Cánovas Cánovas, María Josefa
  • López Cerdá, Marco A.
  • Parra López, Juan
  • Toledo, Francisco Javier
In this paper we deal with parameterized linear inequality systems in the n-dimensional Euclidean space, whose coefficients depend continuosly on an index ranging in a compact Hausdorff space. The paper is developed in two different parametric settings: the one of only right-hand-side perturbations of the linear system, and that in which both sides of the system can be perturbed. Appealing to the backgrounds on the calmness property, and exploiting the specifics of the current linear structure, we derive different characterizations of the calmness of the feasible set mapping, and provide an operative expresion for the calmness modulus when confined to finite systems. In the paper, the role played by the Abadie constraint qualification in relation to calmness is clarified, and illustrated by different examples. We point out that this approach has the virtue of tackling the calmness property exclusively in terms of the system’s data.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

On the stability of the Motzkin representation of closed convex sets

  • Goberna, Miguel A.
  • Todorov, Maxim I.
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
A set is called Motzkin decomposable when it can be expressed as the Minkowski sum of a compact convex set with a closed convex cone. This paper analyzes the continuity properties of the set-valued mapping associating to each couple (C,D) formed by a compact convex set C and a closed convex cone D its Minkowski sum C + D. The continuity properties of other related mappings are also analyzed.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

From the Farkas Lemma to the Hahn–Banach Theorem

  • Dinh, Nguyen
  • Goberna, Miguel A.
  • López Cerdá, Marco A.
  • Mo, Tran Hong
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
This paper provides new versions of the Farkas lemma characterizing those inequalities of the form f(x) ≥ 0 which are consequences of a composite convex inequality (S ◦ g)(x) ≤ 0 on a closed convex subset of a given locally convex topological vector space X, where f is a proper lower semicontinuous convex function defined on X, S is an extended sublinear function, and g is a vector-valued S-convex function. In parallel, associated versions of a stable Farkas lemma, considering arbitrary linear perturbations of f, are also given. These new versions of the Farkas lemma, and their corresponding stable forms, are established under the weakest constraint qualification conditions (the so-called closedness conditions), and they are actually equivalent to each other, as well as equivalent to an extended version of the so-called Hahn–Banach–Lagrange theorem, and its stable version, correspondingly. It is shown that any of them implies analytic and algebraic versions of the Hahn–Banach theorem and the Mazur–Orlicz theorem for extended sublinear functions.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Robust Solutions of MultiObjective Linear Semi-Infinite Programs under Constraint Data Uncertainty

  • Goberna, Miguel A.
  • Jeyakumar, Vaithilingam
  • Li, Guoyin
  • Vicente-Pérez, José
  • Vicente-Pérez, José|||/items/7fad998a-2853-4a32-852d-d0c16df35750
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
The multiobjective optimization model studied in this paper deals with simultaneous minimization of finitely many linear functions subject to an arbitrary number of uncertain linear constraints. We first provide a radius of robust feasibility guaranteeing the feasibility of the robust counterpart under affine data parametrization. We then establish dual characterizations of robust solutions of our model that are immunized against data uncertainty by way of characterizing corresponding solutions of robust counterpart of the model. Consequently, we present robust duality theorems relating the value of the robust model with the corresponding value of its dual problem.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Local convergence of quasi-Newton methods under metric regularity

  • Aragón Artacho, Francisco Javier
  • Belyakov, Anton O.
  • Dontchev, Asen L.
  • López Cerdá, Marco A.
  • Aragón Artacho, Francisco Javier|||/items/1606bcd1-4dcb-4543-98d2-cba4400516f6
We consider quasi-Newton methods for generalized equations in Banach spaces under metric regularity and give a sufficient condition for q-linear convergence. Then we show that the well-known Broyden update satisfies this sufficient condition in Hilbert spaces. We also establish various modes of q-superlinear convergence of the Broyden update under strong metric subregularity, metric regularity and strong metric regularity. In particular, we show that the Broyden update applied to a generalized equation in Hilbert spaces satisfies the Dennis–Moré condition for q-superlinear convergence. Simple numerical examples illustrate the results.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Lower semicontinuity of the feasible set mapping of linear systems relative to their domains

  • Daniilidis, Aris
  • Goberna, Miguel A.
  • López Cerdá, Marco A.
  • Lucchetti, Roberto
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
This paper deals with stability properties of the feasible set of linear inequality systems having a finite number of variables and an arbitrary number of constraints. Several types of perturbations preserving consistency are considered, affecting respectively, all of the data, the left-hand side data, or the right-hand side coefficients.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

Robust solutions to multi-objective linear programs with uncertain data

  • Goberna, Miguel A.
  • Jeyakumar, Vaithilingam
  • Li, Guoyin
  • Vicente-Pérez, José
  • Vicente-Pérez, José|||/items/7fad998a-2853-4a32-852d-d0c16df35750
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
In this paper we examine multi-objective linear programming problems in the face of data uncertainty both in the objective function and the constraints. First, we derive a formula for the radius of robust feasibility guaranteeing constraint feasibility for all possible scenarios within a specified uncertainty set under affine data parametrization. We then present numerically tractable optimality conditions for minmax robust weakly efficient solutions, i.e., the weakly efficient solutions of the robust counterpart. We also consider highly robust weakly efficient solutions, i.e., robust feasible solutions which are weakly efficient for any possible instance of the objective matrix within a specified uncertainty set, providing lower bounds for the radius of highly robust efficiency guaranteeing the existence of this type of solutions under affine and rank-1 objective data uncertainty. Finally, we provide numerically tractable optimality conditions for highly robust weakly efficient solutions.
RUA. Repositorio Institucional de la Universidad de Alicante
Publicación Otros (Other)

New glimpses on convex infinite optimization duality

  • Goberna, Miguel A.
  • López Cerdá, Marco A.
  • Volle, Michel
  • Goberna, Miguel A.|||/items/0ddb5812-3544-4062-a814-e139c72d8c3e
Given a convex optimization problem (P) in a locally convex topological vector space X with an arbitrary number of constraints, we consider three possible dual problems of (P), namely, the usual Lagrangian dual (D), the perturbational dual (Q), and the surrogate dual (Δ), the last one recently introduced in a previous paper of the authors (Goberna et al., J Convex Anal 21(4), 2014). As shown by simple examples, these dual problems may be all different. This paper provides conditions ensuring that inf(P)=max(D), inf(P)=max(Q), and inf(P)=max(Δ) (dual equality and existence of dual optimal solutions) in terms of the so-called closedness regarding to a set. Sufficient conditions guaranteeing min(P)=sup(Q) (dual equality and existence of primal optimal solutions) are also provided, for the nominal problems and also for their perturbational relatives. The particular cases of convex semi-infinite optimization problems (in which either the number of constraints or the dimension of X, but not both, is finite) and linear infinite optimization problems are analyzed. Finally, some applications to the feasibility of convex inequality systems are described.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A BRILS metaheuristic for non-smooth flow-shop problems with failure-risk costs

  • Ferrer, Alberto
  • Guimarans, Daniel
  • Ramalhinho-Lourenço, Helena
  • Juan, Angel A.
This paper analyzes a realistic variant of the Permutation Flow-Shop Problem (PFSP) by considering a non-smooth objective function that takes into account not only the traditional makespan cost but also failure-risk costs due to uninterrupted operation of machines. After completing a literature review on the issue, the paper formulates an original mathematical model to describe this new PFSP variant. Then, a Biased-Randomized Iterated Local Search (BRILS) algorithm is proposed as an efficient solving approach. An oriented (biased) random behavior is introduced in the well-known NEH heuristic to generate an initial solution. From this initial solution, the algorithm is able to generate a large number of alternative good solutions without requiring a complex setting of parameters. The relative simplicity of our approach is particularly useful in the presence of non-smooth objective functions, for which exact optimization methods may fail to reach their full potential. The gains of considering failure-risk costs during the exploration of the solution space are analyzed throughout a series of computational experiments. To promote reproducibility, these experiments are based on a set of traditional benchmark instances. Moreover, the performance of the proposed algorithm is compared against other state-of-the-art metaheuristic approaches, which have been conveniently adapted to consider failure-risk costs during the solving process. The proposed BRILS approach can be easily extended to other combinatorial optimization problems with similar non-smooth objective functions., This research has been partially supported by the Spanish Ministry of Economy and Competitiveness, projects MTM2011-29064-C03-02, MTM2014-59179-C2-01 & TRA2013-48180-C3-P, and FEDER. NICTA is funded by the Australian Government through the Department of Communications and the Australian Research Council through the ICT Centre of Excellence Program.