1-2期

最新文章

• Dynamic stochastic approximation for multi-stage stochastic optimization AI翻译
  作者：Lan, Guanghui; Zhou, Zhiqiang
  作者单位：University System of Georgia; Georgia Institute of Technology
  摘要：In this paper, we consider multi-stage stochastic optimization problems with convex objectives and conic constraints at each stage. We present a new stochastic first-order method, namely the dynamic stochastic approximation (DSA) algorithm, for solving these types of stochastic optimization problems. We show that DSA can achieve an optimal O(1/epsilon 4) rate of convergence in terms of the total number of required scenarios when applied to a three-stage stochastic optimization problem. We furt...
• On sparsity of the solution to a random quadratic optimization problem AI翻译
  作者：Chen, Xin; Pittel, Boris
  作者单位：University of Illinois System; University of Illinois Urbana-Champaign; University System of Ohio; Ohio State University
  摘要：The standard quadratic optimization problem (StQP), i.e. the problem of minimizing a quadratic form x(T) Qx on the standard simplex {x >= 0 : x(T) e = 1}, is studied. The StQP arises in numerous applications, and it is known to be NP-hard. Chen, Peng and Zhang showed that almost certainly the StQP with a large random matrix Q = Q(T), Q(i, j), (i <= j) being independent and identically concave-distributed, attains its minimum at a point x with support size vertical bar{j : x(j) > 0}vertical bar...
• Quasi-Monte Carlo methods for two-stage stochastic mixed-integer programs AI翻译
  作者：Leovey, H.; Roemisch, W.
  作者单位：Humboldt University of Berlin
  摘要：We consider randomized QMC methods for approximating the expected recourse in two-stage stochastic optimization problems containing mixed-integer decisions in the second stage. It is known that the second-stage optimal value function is piecewise linear-quadratic with possible kinks and discontinuities at the boundaries of certain convex polyhedral sets. This structure is exploited to provide conditions implying that first and higher order terms of the integrand's ANOVA decomposition (Math. Co...
• Duality for constrained robust sum optimization problems AI翻译
  作者：Dinh, N.; Goberna, M. A.; Long, D. H.; Volle, M.
  作者单位：Vietnam National University Ho Chi Minh City (VNUHCM) System; Universitat d'Alacant; Vietnam National University Ho Chi Minh City (VNUHCM) System; Tien Giang University; Avignon Universite
  摘要：Given an infinite family of extended real-valued functions fi, i. I, and a familyHof nonempty finite subsets of I, the H-partial robust sum of fi, i. I, is the supremum, for J. H, of the finite sums j. J f j. These infinite sums arise in a natural way in location problems as well as in functional approximation problems, and include as particular cases the well-known sup function and the so-called robust sum function, corresponding to the set H of all nonempty finite subsets of I, whose unconst...
• Convergence rates of an inertial gradient descent algorithm under growth and flatness conditions AI翻译
  作者：Apidopoulos, Vassilis; Aujol, Jean-Francois; Dossal, Charles; Rondepierre, Aude
  作者单位：University of Genoa; Universite de Bordeaux; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Universite Federale Toulouse Midi-Pyrenees (ComUE); Institut National des Sciences Appliquees de Toulouse; Centre National de la Recherche Scientifique (CNRS); Universite de Toulouse
  摘要：In this paper we study the convergence properties of a Nesterov's family of inertial schemes which is a specific case of inertial Gradient Descent algorithm in the context of a smooth convex minimization problem, under some additional hypotheses on the local geometry of the objective function F, such as the growth (or Lojasiewicz) condition. In particular we study the different convergence rates for the objective function and the local variation, depending on these geometric conditions. In thi...
• Characterization of Filippov representable maps and Clarke subdifferentials AI翻译
  作者：Bivas, Mira; Daniilidis, Aris; Quincampoix, Marc
  作者单位：University of Sofia; Bulgarian Academy of Sciences; Universidad de Chile; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite de Bretagne Occidentale
  摘要：The ordinary differential equation (x) over dot(t) = f (x(t)), t >= 0, for f measurable, is not sufficiently regular to guarantee existence of solutions. To remedy this we may relax the problem by replacing the function f with its Filippov regularization F-f and consider the differential inclusion (x) over dot(t) is an element of F-f (x(t)) which always has a solution. It is interesting to know, inversely, when a set-valued map Phi can be obtained as the Filippov regularization of a (single-va...
• Hypergraph k-cut in randomized polynomial time AI翻译
  作者：Chandrasekaran, Karthekeyan; Xu, Chao; Yu, Xilin
  作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Yahoo! Inc
  摘要：For a fixed integer the hypergraph k-cut problem asks for a smallest subset of hyperedges whose removal leads to at least k connected components in the remaining hypergraph. While graph k-cut is solvable efficiently (Goldschmidt and Hochbaum in Math. Oper. Res. 19(1):24-37, 1994), the complexity of hypergraph k-cut has been open. In this work, we present a randomized polynomial time algorithm to solve the hypergraph k-cut problem. Our algorithmic technique extends to solve the more general hed...
• Statistical robustness in utility preference robust optimization models AI翻译
  作者：Guo, Shaoyan; Xu, Huifu
  作者单位：Dalian University of Technology; Chinese University of Hong Kong
  摘要：Utility preference robust optimization (PRO) concerns decision making problems where information on decision maker's utility preference is incomplete and has to be elicited through partial information and the optimal decision is based on the worst case utility function elicited. A key assumption in the PRO models is that the true probability distribution is either known or can be recovered by real data generated by the true distribution. In data-driven optimization, this assumption may not be ...
• The salesman's improved tours for fundamental classes AI翻译
  作者：Boyd, Sylvia; Sebo, Andras
  作者单位：University of Ottawa; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
  摘要：Finding the exact integrality gap a for the LP relaxation of the metric travelling salesman problem (TSP) has been an open problem for over 30 years, with little progress made. It is known that 4/3 = alpha = 3/2, and a famous conjecture states alpha = 4/3. It has also been conjectured that the integrality gap is achieved for half-integer basic solutions of the linear program. For this problem, essentially two fundamental classes of instances have been proposed. This fundamental property means ...
• Fully asynchronous stochastic coordinate descent: a tight lower bound on the parallelism achieving linear speedup AI翻译
  作者：Cheung, Yun Kuen; Cole, Richard; Tao, Yixin
  作者单位：Singapore University of Technology & Design; New York University
  摘要：We seek tight bounds on the viable parallelism in asynchronous implementations of coordinate descent that achieves linear speedup. We focus on asynchronous coordinate descent (ACD) algorithms on convex functions which consist of the sum of a smooth convex part and a possibly non-smooth separable convex part. We quantify the shortfall in progress compared to the standard sequential stochastic gradient descent. This leads to a simple yet tight analysis of the standard stochastic ACD in a partial...