A counterexample to De Pierro's conjecture on the convergence of under-relaxed cyclic projections

  • Authors: Cominetti, Roberto , Roshchina, Vera , Williamson, Andrew
  • Date: 2019
  • Type: Text , Journal article , acceptedVersion
  • Relation: Optimization Vol. 68, no. 1 (2019), p. 3-12
  • Full Text:
  • Reviewed:
  • Description: The convex feasibility problem consists in finding a point in the intersection of a finite family of closed convex sets. When the intersection is empty, a best compromise is to search for a point that minimizes the sum of the squared distances to the sets. In 2001, de Pierro conjectured that the limit cycles generated by the ε-under-relaxed cyclic projection method converge when ε ↓ 0 towards a least squares solution. While the conjecture has been confirmed under fairly general conditions, we show that it is false in general by constructing a system of three compact convex sets in R3 for which the ε-under-relaxed cycles do not converge. © 2018 Informa UK Limited, trading as Taylor & Francis Group.

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

  • Authors: Cánovas, Maria , Hall, Julian , López, Marco , Parra, Juan
  • Date: 2019
  • Type: Text , Journal article
  • Relation: Optimization Vol. 68, no. 2-3 (2019), p. 465-483
  • Full Text:
  • Reviewed:
  • Description: 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 [Canovas MJ, Lopez 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.

Characterizations of nonsmooth robustly quasiconvex functions

  • Authors: Bui, Hoa , Khanh, Pham , Tran, Thi
  • Date: 2019
  • Type: Text , Journal article
  • Relation: Journal of Optimization Theory and Applications Vol. 180, no. 3 (2019), p. 775-786
  • Full Text:
  • Reviewed:
  • Description: Two criteria for the robust quasiconvexity of lower semicontinuous functions are established in terms of Fréchet subdifferentials in Asplund spaces. The first criterion extends to such spaces a result established by Barron et al. (Discrete Contin Dyn Syst Ser B 17:1693–1706, 2012). The second criterion is totally new even if it is applied to lower semicontinuous functions on finite-dimensional spaces. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.

Convexity and closedness in stable robust duality

  • Authors: Dinh, Nguyen , Goberna, Miguel , López, Marco , Volle, Michel
  • Date: 2019
  • Type: Text , Journal article
  • Relation: Optimization Letters Vol. 13, no. 2 (2019), p. 325-339
  • Relation: http://purl.org/au-research/grants/arc/DP160100854
  • Full Text:
  • Reviewed:
  • Description: 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.

New Farkas-type results for vector-valued functions : A non-abstract approach

  • Authors: Dinh, Nguyen , Goberna, Miguel , Long, Dang , Lopez-Cerda, Marco
  • Date: 2019
  • Type: Text , Journal article
  • Relation: Journal of Optimization Theory and Applications Vol. 182, no. 1 (2019), p. 4-29
  • Full Text:
  • Reviewed:
  • Description: 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.

On the reconstruction of polytopes

  • Authors: Doolittle, Joseph , Nevo, Eran , Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David
  • Date: 2019
  • Type: Text , Journal article
  • Relation: Discrete and Computational Geometry Vol. 61, no. 2 (2019), p. 285-302
  • Full Text:
  • Reviewed:
  • Description: Blind and Mani, and later Kalai, showed that the face lattice of a simple polytope is determined by its graph, namely its 1-skeleton. Call a vertex of a d-polytope nonsimple if the number of edges incident to it is more than d. We show that (1) the face lattice of any d-polytope with at most two nonsimple vertices is determined by its 1-skeleton; (2) the face lattice of any d-polytope with at most d- 2 nonsimple vertices is determined by its 2-skeleton; and (3) for any d> 3 there are two d-polytopes with d- 1 nonsimple vertices, isomorphic (d- 3) -skeleta and nonisomorphic face lattices. In particular, the result (1) is best possible for 4-polytopes. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.

Outer limits of subdifferentials for min–max type functions

  • Authors: Eberhard, Andrew , Roshchina, Vera , Sang, Tian
  • Date: 2019
  • Type: Text , Journal article
  • Relation: Optimization Vol. 68, no. 7 (2019), p. 1391-1409
  • Full Text:
  • Reviewed:
  • Description: We generalize the outer subdifferential construction suggested by Cánovas, Henrion, López and Parra for max type functions to pointwise minima of regular Lipschitz functions. We also answer an open question about the relation between the outer subdifferential of the support of a regular function and the end set of its subdifferential posed by Li, Meng and Yang.

The Demyanov–Ryabova conjecture is false

  • Authors: Roshchina, Vera
  • Date: 2019
  • Type: Text , Journal article
  • Relation: Optimization Letters Vol. 13, no. 1 (2019), p. 227-234
  • Full Text:
  • Reviewed:
  • Description: It was conjectured by Demyanov and Ryabova (Discrete Contin Dyn Syst 31(4):1273–1292, 2011) that the minimal cycle in the sequence obtained via repeated application of the Demyanov converter to a finite family of polytopes is at most two. We construct a counterexample for which the minimal cycle has length 4.

Two curve Chebyshev approximation and its application to signal clustering

  • Authors: Sukhorukova, Nadezda
  • Date: 2019
  • Type: Text , Journal article
  • Relation: Applied Mathematics and Computation Vol. 356, no. (2019), p. 42-49
  • Full Text:
  • Reviewed:
  • Description: In this paper, we extend a number of important results of the classical Chebyshev approximation theory to the case of simultaneous approximation of two or more functions. The need for this extension is application driven, since such kind of problems appears in the area of curve (signal) clustering. In this paper, we propose a new efficient algorithm for signal clustering and develop a procedure that allows one to reuse the results obtained at the previous iteration without recomputing the cluster centres from scratch. This approach is based on the extension of the classical de la Vallee-Poussin procedure originally developed for polynomial approximation. We also develop necessary and sufficient optimality conditions for two curve Chebyshev approximation, which is our core tool for curve clustering. These results are based on application of nonsmooth convex analysis. (C) 2019 Elsevier Inc. All rights reserved. In this paper, we extend a number of important results of the classical Chebyshev approximation theory to the case of simultaneous approximation of two or more functions. The need for this extension is application driven, since such kind of problems appears in the area of curve (signal) clustering. In this paper, we propose a new efficient algorithm for signal clustering and develop a procedure that allows one to reuse the results obtained at the previous iteration without recomputing the cluster centres from scratch. This approach is based on the extension of the classical de la Vallee-Poussin procedure originally developed for polynomial approximation. We also develop necessary and sufficient optimality conditions for two curve Chebyshev approximation, which is our core tool for curve clustering. These results are based on application of nonsmooth convex analysis. (C) 2019 Elsevier Inc. All rights reserved.

Variational analysis Down Under open problem session

Double bundle method for finding clarke stationary points in nonsmooth dc programming

  • Authors: Joki, Kaisa , Bagirov, Adil , Karmitsa, Napsu , Makela, Marko , Taheri, Sona
  • Date: 2018
  • Type: Text , Journal article
  • Relation: SIAM Journal on Optimization Vol. 28, no. 2 (2018), p. 1892-1919
  • Relation: http://purl.org/au-research/grants/arc/DP140103213
  • Full Text:
  • Reviewed:
  • Description: The aim of this paper is to introduce a new proximal double bundle method for unconstrained nonsmooth optimization, where the objective function is presented as a difference of two convex (DC) functions. The novelty in our method is a new escape procedure which enables us to guarantee approximate Clarke stationarity for solutions by utilizing the DC components of the objective function. This optimality condition is stronger than the criticality condition typically used in DC programming. Moreover, if a candidate solution is not approximate Clarke stationary, then the escape procedure returns a descent direction. With this escape procedure, we can avoid some shortcomings encountered when criticality is used. The finite termination of the double bundle method to an approximate Clarke stationary point is proved by assuming that the subdifferentials of DC components are polytopes. Finally, some encouraging numerical results are presented.

Perturbation of error bounds

  • Authors: Kruger, Alexander , López, Marco , Théra, Michel
  • Date: 2018
  • Type: Text , Journal article
  • Relation: Mathematical Programming Vol. 168, no. 1-2 (2018), p. 533-554
  • Relation: http://purl.org/au-research/grants/arc/DP160100854
  • Full Text:
  • Reviewed:
  • Description: 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. © 2017, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.

Set regularities and feasibility problems

Characterization theorem for best polynomial spline approximation with free knots, variable degree and fixed tails

  • Authors: Crouzeix, Jean-Pierre , Sukhorukova, Nadezda , Ugon, Julien
  • Date: 2017
  • Type: Text , Journal article
  • Relation: Journal of Optimization Theory and Applications Vol. 172, no. 3 (2017), p. 950-964
  • Full Text:
  • Reviewed:
  • Description: In this paper, we derive a necessary condition for a best approximation by piecewise polynomial functions of varying degree from one interval to another. Based on these results, we obtain a characterization theorem for the polynomial splines with fixed tails, that is the value of the spline is fixed in one or more knots (external or internal). We apply nonsmooth nonconvex analysis to obtain this result, which is also a necessary and sufficient condition for inf-stationarity in the sense of Demyanov-Rubinov. This paper is an extension of a paper where similar conditions were obtained for free tails splines. The main results of this paper are essential for the development of a Remez-type algorithm for free knot spline approximation.

Farkas-type results for vector-valued functions with applications

  • Authors: Dinh, Nguyen , Goberna, Miguel , López, Marco , Mo, T. H.
  • Date: 2017
  • Type: Text , Journal article
  • Relation: Journal of Optimization Theory and Applications Vol. 173, no. 2 (2017), p. 357-390
  • Full Text:
  • Reviewed:
  • Description: 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.

On modeling and global solutions for d.c. optimization problems by canonical duality theory

  • Authors: Jin, Zhong , Gao, David
  • Date: 2017
  • Type: Text , Journal article
  • Relation: Applied Mathematics and Computation Vol. 296, no. (2017), p. 168-181
  • Full Text:
  • Reviewed:
  • Description: This paper presents a canonical d.c. (difference of canonical and convex functions) programming problem, which can be used to model general global optimization problems in complex systems. It shows that by using the canonical duality theory, a large class of nonconvex minimization problems can be equivalently converted to a unified concave maximization problem over a convex domain, which can be solved easily under certain conditions. Additionally, a detailed proof for triality theory is provided, which can be used to identify local extremal solutions. Applications are illustrated and open problems are presented.
  • Description: This paper presents a canonical d.c. (difference of canonical and convex functions) programming problem, which can be used to model general global optimization problems in complex systems. It shows that by using the canonical duality theory, a large class of nonconvex minimization problems can be equivalently converted to a unified concave maximization problem over a convex domain, which can be solved easily under certain conditions. Additionally, a detailed proof for triality theory is provided, which can be used to identify local extremal solutions. Applications are illustrated and open problems are presented. © 2016 Elsevier Inc.

On the Aubin property of a class of parameterized variational systems

  • Authors: Gfrerer, Helmut , Outrata, Jiri
  • Date: 2017
  • Type: Text , Journal article
  • Relation: Mathematical Methods of Operations Research Vol. 86, no. 3 (2017), p. 443-467
  • Relation: http://purl.org/au-research/grants/arc/DP160100854
  • Full Text:
  • Reviewed:
  • Description: The paper deals with a new sharp condition ensuring the Aubin property of solution maps to a class of parameterized variational systems. This class encompasses various types of parameterized variational inequalities/generalized equations with fairly general constraint sets. The new condition requires computation of directional limiting coderivatives of the normal-cone mapping for the so-called critical directions. The respective formulas have the form of a second-order chain rule and extend the available calculus of directional limiting objects. The suggested procedure is illustrated by means of examples. © 2017, Springer-Verlag GmbH Germany.

A generalization of a theorem of Arrow, Barankin and Blackwell to a nonconvex case

  • Authors: Kasimbeyli, Nergiz , Kasimbeyli, Refail , Mammadov, Musa
  • Date: 2016
  • Type: Text , Journal article
  • Relation: Optimization Vol. 65, no. 5 (May 2016), p. 937-945
  • Full Text:
  • Reviewed:
  • Description: The paper presents a generalization of a known density theorem of Arrow, Barankin, and Blackwell for properly efficient points defined as support points of sets with respect to monotonically increasing sublinear functions. This result is shown to hold for nonconvex sets of a partially ordered reflexive Banach space.

Canonical duality for solving general nonconvex constrained problems

  • Authors: Latorre, Vittorio , Gao, David
  • Date: 2016
  • Type: Text , Journal article
  • Relation: Optimization Letters Vol. 10, no. 8 (2016), p. 1763-1779
  • Full Text:
  • Reviewed:
  • Description: This paper presents a canonical duality theory for solving a general nonconvex constrained optimization problem within a unified framework to cover Lagrange multiplier method and KKT theory. It is proved that if both target function and constraints possess certain patterns necessary for modeling real systems, a perfect dual problem (without duality gap) can be obtained in a unified form with global optimality conditions provided.While the popular augmented Lagrangian method may produce more difficult nonconvex problems due to the nonlinearity of constraints. Some fundamental concepts such as the objectivity and Lagrangian in nonlinear programming are addressed.

Directional Holder metric regularity

  • Authors: Ngai, Huynh Van , Tron, Nguyen Huu , Thera, Michel
  • Date: 2016
  • Type: Text , Journal article
  • Relation: Journal of Optimization Theory and Applications Vol. 171, no. 3 (2016), p. 785-819
  • Full Text:
  • Reviewed:
  • Description: This paper sheds new light on regularity of multifunctions through various characterizations of directional Holder/Lipschitz metric regularity, which are based on the concepts of slope and coderivative. By using these characterizations, we show that directional Holder/Lipschitz metric regularity is stable, when the multifunction under consideration is perturbed suitably. Applications of directional Holder/Lipschitz metric regularity to investigate the stability and the sensitivity analysis of parameterized optimization problems are also discussed.