-
作者：Szeszler, David
作者单位：Budapest University of Technology & Economics
摘要：We present various new results on greedoids. We prove a theorem that generalizes an equivalent formulation of Edmonds' classic matroid polytope theorem to local forest greedoids-a class of greedoids that contains matroids as well as branching greedoids. We also describe an application of this theorem in the field of measuring the reliability of networks by game-theoretical tools. Finally, we prove new results on the optimality of the greedy algorithm on greedoids and correct some mistakes that...
-
作者：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...
-
作者：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...
-
作者：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...
-
作者：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...
-
作者：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...
-
作者：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...
-
作者：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...
-
作者：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...
-
作者：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...
