Convex and Nonsmooth Optimization

Nearly optimal first-order methods for convex optimization under gradient norm measure: An adaptive regularization approach

  • Mituhiro Fukuda
  • Masaru Ito
    • Categories Convex Optimization, Nonsmooth Optimization

    In the development of first-order methods for smooth (resp., composite) convex optimization problems minimizing smooth functions, the gradient (resp., gradient mapping) norm is a fundamental optimality measure for which a regularization technique of first-order methods is known to be nearly optimal. In this paper, we report an adaptive regularization approach attaining this iteration complexity without … Read more

    The Fermat Rule for Set Optimization Problems with Lipschitzian Set-Valued Mappings

  • Gemayqzel Bouza
  • Christiane Tammer
  • Ernest Quintana
  • Vu Anh Tuan
    • Categories Multi-Criteria Optimization, Nonsmooth Optimization, Robust Optimization Tags , , , ,

    n this paper, we consider set optimization problems with respect to the set approach. Specifically, we deal with the lower less and the upper less set relations. First, we derive properties of convexity and Lipschitzianity of suitable scalarizing functionals, under the same assumption on the set-valued objective mapping. We then obtain upper estimates of the … Read more

    A Limiting Analysis on Regularization of Singular SDP and its Implication to Infeasible Interior-point Algorithms

  • Bruno F. Lourenço
  • Masakazu Muramatsu
  • Takashi Tsuchiya
  • Takayuki Okuno
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    We consider primal-dual pairs of semidefinite programs and assume that they are ill-posed, i.e., both primal and dual are either weakly feasible or weakly infeasible. Under such circumstances, strong duality may break down and the primal and dual might have a nonzero duality gap. Nevertheless, there are arbitrary small perturbations to the problem data which … Read more

    A New Preconditioning Approach for an Interior Point-Proximal Method of Multipliers for Linear and Convex Quadratic Programming

  • Luca Bergamaschi
  • Jacek Gondzio
  • John W. Pearson
  • Ángeles Martínez
  • Spyridon Pougkakiotis
    • Categories Convex Optimization, Linear Programming, Quadratic Programming Tags , , , ,

    In this paper, we address the efficient numerical solution of linear and quadratic programming problems, often of large scale. With this aim, we devise an infeasible interior point method, blended with the proximal method of multipliers, which in turn results in a primal-dual regularized interior point method. Application of this method gives rise to a … Read more

    Active strict saddles in nonsmooth optimization

  • Damek Davis
  • Dmitriy Drusvyatskiy
    • Categories Nonsmooth Optimization Tags , , ,

    We introduce a geometrically transparent strict saddle property for nonsmooth functions. This property guarantees that simple proximal algorithms on weakly convex problems converge only to local minimizers, when randomly initialized. We argue that the strict saddle property may be a realistic assumption in applications, since it provably holds for generic semi-algebraic optimization problems. Article Download … Read more

    A subspace-accelerated split Bregman method for sparse data recovery with joint l1-type regularizers

  • Valentina De Simone
  • Daniela di Serafino
  • Marco Viola
    • Categories Convex Optimization, Finance and Economics, Nonsmooth Optimization Tags , , ,

    We propose a subspace-accelerated Bregman method for the linearly constrained minimization of functions of the form f(u)+tau_1 ||u||_1 + tau_2 ||D*u||_1, where f is a smooth convex function and D represents a linear operator, e.g. a finite difference operator, as in anisotropic Total Variation and fused-lasso regularizations. Problems of this type arise in a wide … Read more

    A Distributed Quasi-Newton Algorithm for Primal and Dual Regularized Empirical Risk Minimization

  • Stephen Wright
  • Cong Han Lim
  • Ching-pei Lee
    • Categories Nonsmooth Optimization, Parallel Algorithms Tags , , , , , , ,

    We propose a communication- and computation-efficient distributed optimization algorithm using second-order information for solving empirical risk minimization (ERM) problems with a nonsmooth regularization term. Our algorithm is applicable to both the primal and the dual ERM problem. Current second-order and quasi-Newton methods for this problem either do not work well in the distributed setting or … Read more

    A robust method based on LOVO functions for solving least squares problems

  • E. V. Castelani
  • R. Lopes
  • W. V. I. Shirabayashi
  • Francisco N. C. Sobral
    • Categories Nonlinear Systems and Least-Squares, Nonsmooth Optimization, Parallel Algorithms Tags , , ,

    The robust adjustment of nonlinear models to data is considered in this paper. When data comes from real experiments, it is possible that measurement errors cause the appearance of discrepant values, which should be ignored when adjusting models to them. This work presents a Lower Order-value Optimization (LOVO) version of the Levenberg-Marquardt algorithm, which is … Read more

    Data-compatibility of algorithms

  • Yair Censor
  • Maroun Zaknoon
  • Alexander J. Zaslavski
    • Categories Constrained Nonlinear Optimization, Convex Optimization Tags , , , , , , , ,

    The data-compatibility approach to constrained optimization, proposed here, strives to a point that is “close enough” to the solution set and whose target function value is “close enough” to the constrained minimum value. These notions can replace analysis of asymptotic convergence to a solution point of infinite sequences generated by specific algorithms. We consider a … Read more

    Dynamic string-averaging CQ-methods for the split feasibility problem with percentage violation constraints arising in radiation therapy treatment planning

  • Mark Brooke
  • Yair Censor
  • Aviv Gibali
    • Categories Biomedical Applications, Constrained Nonlinear Optimization, Convex Optimization Tags , , , , , , , , ,

    In this paper we study a feasibility-seeking problem with percentage violation con- straints. These are additional constraints, that are appended to an existing family of constraints, which single out certain subsets of the existing constraints and declare that up to a speci ed fraction of the number of constraints in each subset is allowed to be … Read more