Search

In this paper, we consider a class of structured fractional minimization problems where the numerator part of the objective is the sum of a convex function and a Lipschitz differentiable (possibly) nonconvex function, while the denominator part is a convex function. By exploiting the structure of the problem, we propose a first-order algorithm, namely, a proximal-gradient-subgradient algorithm with backtracked extrapolation (PGSA_BE) for solving this type of optimization problem. It is worth pointing out that there are a few differences between our backtracked extrapolation and other popular extrapolations used in convex and nonconvex optimization. One of such differences is as follows: if the new iterate obtained from the extrapolated iteration satisfies a backtracking condition, then this new iterate will be replaced by the one generated from the non-extrapolated iteration. We show that any accumulation point of the sequence generated by PGSA_BE is a critical point of the problem regarded. In addition, by assuming that some auxiliary functions satisfy the Kurdyka-Łojasiewicz property, we are able to establish global convergence of the entire sequence, in the case where the denominator is locally Lipschitz differentiable, or its conjugate satisfies the calmness condition. Finally, we present some preliminary numerical results to illustrate the efficiency of PGSA_BE. [ABSTRACT FROM AUTHOR]

This paper provides operative point-based formulas (only involving the nominal data, and not data in a neighborhood) for computing or estimating the calmness modulus of the optimal set (argmin) mapping in linear optimization under uniqueness of nominal optimal solutions. Our analysis is developed in two different parametric settings. First, in the framework of canonical perturbations (i.e., perturbations of the objective function and the right-hand-side of the constraints), the paper provides a computationally tractable formula for the calmness modulus, which goes beyond some preliminary results of the literature. Second, in the framework of full perturbations (perturbations of all coefficients), after characterizing the calmness property for the optimal set mapping, the paper provides an operative upper bound for the corresponding calmness modulus, as well as some illustrative examples. We provide two applications related to algorithms traced out from the literature: the first one to a descent method in LP, and the second to a regularization method for linear programs with complementarity constraints. [ABSTRACT FROM AUTHOR]

Our paper deals with the interrelation of optimization methods and Lipschitz stability of multifunctions in arbitrary Banach spaces. Roughly speaking, we show that linear convergence of several first order methods and Lipschitz stability mean the same. Particularly, we characterize calmness and the Aubin property by uniformly (with respect to certain starting points) linear convergence of descent methods and approximate projection methods. So we obtain, e.g., solution methods (for solving equations or variational problems) which require calmness only. The relations of these methods to several known basic algorithms are discussed, and errors in the subroutines as well as deformations of the given mappings are permitted. We also recall how such deformations are related to standard algorithms like barrier, penalty or regularization methods in optimization. [ABSTRACT FROM AUTHOR]