1-2期

最新文章

• Hessian averaging in stochastic Newton methods achieves superlinear convergence AI翻译
  作者：Na, Sen; Derezinski, Michal; Mahoney, Michael W.
  作者单位：University of California System; University of California Berkeley; University of California System; University of California Berkeley; University of Michigan System; University of Michigan
  摘要：We consider minimizing a smooth and strongly convex objective function using a stochastic Newton method. At each iteration, the algorithm is given an oracle access to a stochastic estimate of the Hessian matrix. The oracle model includes popular algorithms such as Subsampled Newton and Newton Sketch, which can efficiently construct stochastic Hessian estimates for many tasks, e.g., training machine learning models. Despite using second-order information, these existing methods do not exhibit s...
• A semismooth Newton based augmented Lagrangian method for nonsmooth optimization on matrix manifolds AI翻译
  作者：Zhou, Yuhao; Bao, Chenglong; Ding, Chao; Zhu, Jun
  作者单位：Tsinghua University; Tsinghua University; Yanqi Lake Beijing Institute of Mathematical Sciences & Applications; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
  摘要：This paper is devoted to studying an augmented Lagrangian method for solving a class of manifold optimization problems, which have nonsmooth objective functions and nonlinear constraints. Under the constant positive linear dependence condition on manifolds, we show that the proposed method converges to a stationary point of the nonsmooth manifold optimization problem. Moreover, we propose a globalized semismooth Newton method to solve the augmented Lagrangian subproblem on manifolds efficientl...
• An exponential lower bound for Zadeh's pivot rule AI翻译
  作者：Disser, Yann; Friedmann, Oliver; Hopp, Alexander, V
  作者单位：Technical University of Darmstadt; University of Munich; Merck KGaA
  摘要：The question whether the Simplex Algorithm admits an efficient pivot rule remains one of the most important open questions in discrete optimization. While many natural, deterministic pivot rules are known to yield exponential running times, the random-facet rule was shown to have a subexponential running time. For a long time, Zadeh's rule remained the most prominent candidate for the first deterministic pivot rule with subexponential running time. We present a lower bound construction that sh...
• Convergence of augmented Lagrangian methods in extensions beyond nonlinear programming AI翻译
  作者：Rockafellar, R. Tyrrell
  作者单位：University of Washington; University of Washington Seattle
  摘要：The augmented Lagrangian method (ALM) is extended to a broader-than-ever setting of generalized nonlinear programming in convex and nonconvex optimization that is capable of handling many common manifestations of nonsmoothness. With the help of a recently developed sufficient condition for local optimality, it is shown to be derivable from the proximal point algorithm through a kind of local duality corresponding to an optimal solution and accompanying multiplier vector that furnish a local sa...
• Discrete potential mean field games: duality and numerical resolution AI翻译
  作者：Bonnans, J. Frederic; Lavigne, Pierre; Pfeiffer, Laurent
  作者单位：Universite Paris Saclay; Centre National de la Recherche Scientifique (CNRS); Inria; Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Inria; Institut Polytechnique de Paris; Ecole Polytechnique
  摘要：We propose and investigate a general class of discrete time and finite state space mean field game (MFG) problems with potential structure. Our model incorporates interactions through a congestion term and a price variable. It also allows hard constraints on the distribution of the agents. We analyze the connection between the MFG problem and two optimal control problems in duality. We present two families of numerical methods and detail their implementation: (i) primal-dual proximal methods (...
• Subgradient ellipsoid method for nonsmooth convex problems AI翻译
  作者：Rodomanov, Anton; Nesterov, Yurii
  摘要：In this paper, we present a new ellipsoid-type algorithm for solving nonsmooth problems with convex structure. Examples of such problems include nonsmooth convex minimization problems, convex-concave saddle-point problems and variational inequalities with monotone operator. Our algorithm can be seen as a combination of the standard Subgradient and Ellipsoid methods. However, in contrast to the latter one, the proposed method has a reasonable convergence rate even when the dimensionality of the...
• A new perspective on low-rank optimization AI翻译
  作者：Bertsimas, Dimitris; Cory-Wright, Ryan; Pauphilet, Jean
  作者单位：Massachusetts Institute of Technology (MIT); Imperial College London; International Business Machines (IBM); IBM USA; University of London; London Business School
  摘要：A key question in many low-rank problems throughout optimization, machine learning, and statistics is to characterize the convex hulls of simple low-rank sets and judiciously apply these convex hulls to obtain strong yet computationally tractable relaxations. We invoke the matrix perspective function-the matrix analog of the perspective function-to characterize explicitly the convex hull of epigraphs of simple matrix convex functions under low-rank constraints. Further, we combine the matrix p...
• Exact computation of an error bound for the balanced linear complementarity problem with unique solution AI翻译
  作者：Dussault, Jean-Pierre; Gilbert, Jean Charles
  作者单位：University of Sherbrooke
  摘要：This paper considers the balanced form of the standard linear complementarity problem with unique solution and provides a more precise expression of an upper error bound discovered by Chen and Xiang and published in 2006. This expression has at least two advantages. It makes possible the exact computation of the error bound factor and it provides a satisfactory upper estimate of that factor in terms of the data bitlength when the data is formed of rational numbers. Along the way, we show that,...
• New valid inequalities and formulations for the static joint Chance-constrained Lot-sizing problem AI翻译
  作者：Zhang, Zeyang; Gao, Chuanhou; Luedtke, James
  作者单位：Zhejiang University; University of Wisconsin System; University of Wisconsin Madison
  摘要：We study the static joint chance-constrained lot-sizing problem, in which production decisions over a planning horizon are made before knowing random future demands, and the inventory variables are then determined by the demand realizations. The joint chance constraint imposes a service level requirement that the probability that all demands are met on time be above a threshold. We model uncertain outcomes with a finite set of scenarios and begin by applying existing results about chance-const...
• Sample average approximation with heavier tails I: non-asymptotic bounds with weak assumptions and stochastic constraints AI翻译
  作者：Oliveira, Roberto, I; Thompson, Philip
  作者单位：Purdue University System; Purdue University; Purdue University System; Purdue University
  摘要：We derive new and improved non-asymptotic deviation inequalities for the sample average approximation (SAA) of an optimization problem. Our results give strong error probability bounds that are sub-Gaussian even when the randomness of the problem is fairly heavy tailed. Additionally, we obtain good (often optimal) dependence on the sample size and geometrical parameters of the problem. Finally, we allow for random constraints on the SAA and unbounded feasible sets, which also do not seem to ha...