rate of convergence

Global convergence of a BFGS-type algorithm for nonconvex multiobjective optimization problems

  • Leandro Fonseca Prudente
  • D. R. Souza
    • Categories Multi-Criteria Optimization Tags , , , , , ,

    We propose a modified BFGS algorithm for multiobjective optimization problems with global convergence, even in the absence of convexity assumptions on the objective functions. Furthermore, we establish the superlinear convergence of the method under usual conditions. Our approach employs Wolfe step sizes and ensures that the Hessian approximations are updated and corrected at each iteration … Read more

    Monotonicity and Complexity of Multistage Stochastic Variational Inequalities

  • Jie Jiang
  • Hailin Sun
    • Categories Complementarity and Variational Inequalities, Stochastic Programming Tags , , ,

    In this paper, we consider multistage stochastic variational inequalities (MSVIs). First, we give multistage stochastic programs and multistage multi-player noncooperative game problems as source problems. After that, we derive the monotonicity properties of MSVIs under less restrictive conditions. Finally, the polynomial rate of convergence with respect to sample sizes between the original problem and its … Read more

    An Adaptive Patch Approximation Algorithm for Bicriteria Convex Mixed Integer problems

  • Erik Diessel
    • Categories (Mixed) Integer Nonlinear Programming, Multi-Criteria Optimization Tags , , ,

    Pareto frontiers of bicriteria continuous convex problems can be efficiently computed and optimal theoretical performance bounds have been established. In the case of bicriteria mixed-integer problems, the approximation of the Pareto frontier becomes, however, significantly harder. In this paper, we propose a new algorithm for approximating the Pareto frontier of bicriteria mixed-integer programs with convex … Read more

    Optimal Transport Based Distributionally Robust Optimization: Structural Properties and Iterative Schemes

  • Jose Blanchet
  • Karthyek Murthy
  • Fan Zhang
    • Categories Robust Optimization, Stochastic Programming Tags , , , , , , ,

    We consider optimal transport based distributionally robust optimization (DRO) problems with locally strongly convex transport cost functions and affine decision rules. Under conventional convexity assumptions on the underlying loss function, we obtain structural results about the value function, the optimal policy, and the worst-case optimal transport adversarial model. These results expose a rich structure embedded … Read more

    Global convergence of the Heavy-ball method for convex optimization

  • Hamid Reza Feyzmahdavian
  • Euhanna Ghadimi
  • Mikael Johansson
    • Categories Convex Optimization, Unconstrained Optimization Tags , , , , ,

    This paper establishes global convergence and provides global bounds of the convergence rate of the Heavy-ball method for convex optimization problems. When the objective function has Lipschitz-continuous gradient, we show that the Cesa ́ro average of the iterates converges to the optimum at a rate of $O(1/k)$ where k is the number of iterations. When … Read more

    Error estimates for the Euler discretization of an optimal control problem with first-order state constraints

  • Joseph Frédéric Bonnans
  • Adriano Festa
    • Categories Control Applications, Systems governed by Differential Equations Optimization Tags , , , ,

    We study the error introduced in the solution of an optimal control problem with first order state constraints, for which the trajectories are approximated with a classical Euler scheme. We obtain order one approximation results in the $L^\infty$ norm (as opposed to the order 2/3 obtained in the literature). We assume either a strong second … Read more

    Rate analysis of inexact dual first order methods: Application to distributed MPC for network systems

  • Ion Necoara
  • Valentin Nedelcu
    • Categories Convex Optimization, Distributed Control, Parallel Algorithms Tags , , , , ,

    In this paper we propose two dual decomposition methods based on inexact dual gradient information for solving large-scale smooth convex optimization problems. The complicating constraints are moved into the cost using the Lagrange multipliers. The dual problem is solved by inexact first order methods based on approximate gradients and we prove sublinear rate of convergence … Read more

    Greedy approximation in convex optimization

  • Vladimir Temlyakov
    • Categories Convex Optimization Tags , , ,

    We study sparse approximate solutions to convex optimization problems. It is known that in many engineering applications researchers are interested in an approximate solution of an optimization problem as a linear combination of elements from a given system of elements. There is an increasing interest in building such sparse approximate solutions using different greedy-type algorithms. … Read more

    Greedy expansions in convex optimization

  • Vladimir Temlyakov
    • Categories Convex Optimization Tags , , ,

    This paper is a follow up to the previous author’s paper on convex optimization. In that paper we began the process of adjusting greedy-type algorithms from nonlinear approximation for finding sparse solutions of convex optimization problems. We modified there three the most popular in nonlinear approximation in Banach spaces greedy algorithms — Weak Chebyshev Greedy … Read more

    A Note on the Behavior of the Randomized Kaczmarz Algorithm of Strohmer and Vershynin

  • Yair Censor
  • Gabor T. Herman
  • Ming Jiang
    • Categories Biomedical Applications, Convex Optimization Tags , ,

    In a recent paper by Strohmer and Vershynin (J. Fourier Anal. Appl. 15:262–278, 2009) a “randomized Kaczmarz algorithm” is proposed for solving consistent systems of linear equations {ai, x = bi }m i=1. In that algorithm the next equation to be used in an iterative Kaczmarz process is selected with a probability proportional to ai2. … Read more