2021

最新文章

• The confined primal integral: a measure to benchmark heuristic MINLP solvers against global MINLP solvers AI翻译
  作者：Berthold, Timo; Csizmadia, Zsolt
  摘要：It is a challenging task to fairly compare local solvers and heuristics against each other and against global solvers. How does one weigh a faster termination time against a better quality of the found solution? In this paper, we introduce the confined primal integral, a new performance measure that rewards a balance of speed and solution quality. It emphasizes the early part of the solution process by using an exponential decay. Thereby, it avoids that the order of solvers can be inverted by ...
• Inexact stochastic mirror descent for two-stage nonlinear stochastic programs AI翻译
  作者：Guigues, Vincent
  作者单位：Getulio Vargas Foundation
  摘要：We introduce an inexact variant of stochastic mirror descent (SMD), called inexact stochastic mirror descent (ISMD), to solve nonlinear two-stage stochastic programs where the second stage problem has linear and nonlinear coupling constraints and a nonlinear objective function which depends on both first and second stage decisions. Given a candidate first stage solution and a realization of the second stage random vector, each iteration of ISMD combines a stochastic subgradient descent using a...
• Lipschitz-like property relative to a set and the generalized Mordukhovich criterion AI翻译
  作者：Meng, K. W.; Li, M. H.; Yao, W. F.; Yang, X. Q.
  作者单位：Southwestern University of Finance & Economics - China; Chongqing University of Arts & Sciences; Hong Kong Polytechnic University
  摘要：In this paper we will establish some necessary condition and sufficient condition respectively for a set-valued mapping to have the Lipschitz-like property relative to a closed set by employing regular normal cone and limiting normal cone of a restricted graph of the set-valued mapping. We will obtain a complete characterization for a set-valued mapping to have the Lipschitz-property relative to a closed and convex set by virtue of the projection of the coderivative onto a tangent cone. Furthe...
• Convergence rates for an inertial algorithm of gradient type associated to a smooth non-convex minimization AI翻译
  作者：Laszlo, Szilard Csaba
  作者单位：Technical University of Cluj Napoca
  摘要：We investigate an inertial algorithm of gradient type in connection with the minimization of a non-convex differentiable function. The algorithm is formulated in the spirit of Nesterov's accelerated convex gradient method. We prove some abstract convergence results which applied to our numerical scheme allow us to show that the generated sequences converge to a critical point of the objective function, provided a regularization of the objective function satisfies the Kurdyka-Lojasiewicz proper...
• Generalized stochastic Frank-Wolfe algorithm with stochastic substitute gradient for structured convex optimization AI翻译
  作者：Lu, Haihao; Freund, Robert M.
  作者单位：University of Chicago; Massachusetts Institute of Technology (MIT)
  摘要：The stochastic Frank-Wolfe method has recently attracted much general interest in the context of optimization for statistical and machine learning due to its ability to work with a more general feasible region. However, there has been a complexity gap in the dependence on the optimality tolerance epsilon in the guaranteed convergence rate for stochastic Frank-Wolfe compared to its deterministic counterpart. In this work, we present a new generalized stochastic Frank-Wolfe method which closes t...
• Subregular recourse in nonlinear multistage stochastic optimization AI翻译
  作者：Dentcheva, Darinka; Ruszczynski, Andrzej
  作者单位：Stevens Institute of Technology; Rutgers University System; Rutgers University New Brunswick
  摘要：We consider nonlinear multistage stochastic optimization problems in the spaces of integrable functions. We allow for nonlinear dynamics and general objective functionals, including dynamic risk measures. We study causal operators describing the dynamics of the system and derive the Clarke subdifferential for a penalty function involving such operators. Then we introduce the concept of subregular recourse in nonlinear multistage stochastic optimization and establish subregularity of the result...
• Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria AI翻译
  作者：Drusvyatskiy, D.; Ioffe, A. D.; Lewis, A. S.
  作者单位：University of Washington; University of Washington Seattle; Technion Israel Institute of Technology; Cornell University
  摘要：We consider optimization algorithms that successively minimize simple Taylor-like models of the objective function. Methods of Gauss-Newton type for minimizing the composition of a convex function and a smooth map are common examples. Our main result is an explicit relationship between the step-size of any such algorithm and the slope of the function at a nearby point. Consequently, we (1) show that the step-sizes can be reliably used to terminate the algorithm, (2) prove that as long as the s...
• Shorter tours and longer detours: uniform covers and a bit beyond AI翻译
  作者：Haddadan, Arash; Newman, Alantha; Ravi, R.
  作者单位：Carnegie Mellon University; Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA)
  摘要：Motivated by the well known four-thirds conjecture for the traveling salesman problem (TSP), we study the problem of uniform covers. A graph G = ( V, E) has an a-uniform cover for TSP (2EC, respectively) if the everywhere a vector (i.e., {a} E) dominates a convex combination of incidence vectors of tours (2-edge-connected spanning multigraphs, respectively). The polyhedral analysis of Christofides' algorithm directly implies that a 3-edge-connected, cubic graph has a 1-uniform cover for TSP. S...
• On the linear convergence rates of exchange and continuous methods for total variation minimization AI翻译
  作者：Flinth, Axel; de Gournay, Frederic; Weiss, Pierre
  作者单位：Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Centre National de la Recherche Scientifique (CNRS); Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse; Universite Toulouse III - Paul Sabatier; University of Gothenburg; Chalmers University of Technology
  摘要：We analyze an exchange algorithm for the numerical solution total-variation regularized inverse problems over the space M(Omega) of Radon measures on a subset Omega of R-d. Our main result states that under some regularity conditions, the method eventually converges linearly. Additionally, we prove that continuously optimizing the amplitudes of positions of the target measure will succeed at a linear rate with a good initialization. Finally, we propose to combine the two approaches into an alt...
• Sensitivity analysis of maximally monotone inclusions via the proto-differentiability of the resolvent operator AI翻译
  作者：Adly, Samir; Rockafellar, R. Tyrrell
  作者单位：Universite de Limoges; University of Washington; University of Washington Seattle
  摘要：This paper is devoted to the study of sensitivity to perturbation of parametrized variational inclusions involving maximally monotone operators in a Hilbert space. The perturbation of all the data involved in the problem is taken into account. Using the concept of proto-differentiability of a multifunction and the notion of semi-differentiability of a single-valued map, we establish the differentiability of the solution of a parametrized monotone inclusion. We also give an exact formula of the...