1-2期

最新文章

• Configuration balancing for stochastic requests AI翻译
  作者：Eberle, Franziska; Gupta, Anupam; Megow, Nicole; Moseley, Benjamin; Zhou, Rudy
  作者单位：Technical University of Berlin; New York University; University of Bremen; Carnegie Mellon University
  摘要：The configuration balancing problem with stochastic requests generalizes well-studied resource allocation problems such as load balancing and virtual circuit routing. There are given m resources and n requests; each request has multiple possible configurations, each of which increases the load of each resource by some amount. The goal is to select one configuration for each request to minimize the makespan: the load of the most-loaded resource. In the stochastic setting, the amount by which a ...
• Optimal methods for convex nested stochastic composite optimization AI翻译
  作者：Zhang, Zhe; Lan, Guanghui
  作者单位：University System of Georgia; Georgia Institute of Technology
  摘要：Recently, convex nested stochastic composite optimization (NSCO) has received considerable interest for its applications in reinforcement learning and risk-averse optimization. However, existing NSCO algorithms have worse stochastic oracle complexities, by orders of magnitude, than those for simpler stochastic optimization problems without nested structures. Additionally, these algorithms require all outer-layer functions to be smooth, a condition violated by some important applications. This ...
• Convergence rates for sums-of-squares hierarchies with correlative sparsity AI翻译
  作者：Korda, Milan; Magron, Victor; Rios-Zertuche, Rodolfo
  作者单位：Centre National de la Recherche Scientifique (CNRS); Czech Technical University Prague; UiT The Arctic University of Tromso
  摘要：This work derives upper bounds on the convergence rate of the moment-sum-of-squares hierarchy with correlative sparsity for global minimization of polynomials on compact basic semialgebraic sets. The main conclusion is that both sparse hierarchies based on the Schmudgen and Putinar Positivstellensatze enjoy a polynomial rate of convergence that depends on the size of the largest clique in the sparsity graph but not on the ambient dimension. Interestingly, the sparse bounds outperform the best ...
• On solving a rank regularized minimization problem via equivalent factorized column-sparse regularized models AI翻译
  作者：Li, Wenjing; Bian, Wei; Toh, Kim-Chuan
  作者单位：Harbin Institute of Technology; National University of Singapore
  摘要：Rank regularized minimization problem is an ideal model for the low-rank matrix completion/recovery problem. The matrix factorization approach can transform the high-dimensional rank regularized problem to a low-dimensional factorized column-sparse regularized problem. The latter can greatly facilitate fast computations in applicable algorithms, but needs to overcome the simultaneous non-convexity of the loss and regularization functions. In this paper, we consider the factorized column-sparse...
• Generalized scaling for the constrained maximum-entropy sampling problem AI翻译
  作者：Chen, Zhongzhu; Fampa, Marcia; Lee, Jon
  作者单位：University of Michigan System; University of Michigan; Universidade Federal do Rio de Janeiro
  摘要：The best practical techniques for exact solution of instances of the constrained maximum-entropy sampling problem, a discrete-optimization problem arising in the design of experiments, are via a branch-and-bound framework, working with a variety of concave continuous relaxations of the objective function. A standard and computationally-important bound-enhancement technique in this context is (ordinary) scaling, via a single positive parameter. Scaling adjusts the shape of continuous relaxation...
• Global optimization for cardinality-constrained minimum sum-of-squares clustering via semidefinite programming AI翻译
  作者：Piccialli, Veronica; Sudoso, Antonio M.
  作者单位：Sapienza University Rome
  摘要：The minimum sum-of-squares clustering (MSSC), or k-means type clustering, has been recently extended to exploit prior knowledge on the cardinality of each cluster. Such knowledge is used to increase performance as well as solution quality. In this paper, we propose a global optimization approach based on the branch-and-cut technique to solve the cardinality-constrained MSSC. For the lower bound routine, we use the semidefinite programming (SDP) relaxation recently proposed by Rujeerapaiboon et...
• Accelerated-gradient-based generalized Levenberg-Marquardt method with oracle complexity bound and local quadratic convergence AI翻译
  作者：Marumo, Naoki; Okuno, Takayuki; Takeda, Akiko
  作者单位：University of Tokyo; Seikei University; RIKEN
  摘要：Minimizing the sum of a convex function and a composite function appears in various fields. The generalized Levenberg-Marquardt (LM) method, also known as the prox-linear method, has been developed for such optimization problems. The method iteratively solves strongly convex subproblems with a damping term. This study proposes a new generalized LM method for solving the problem with a smooth composite function. The method enjoys three theoretical guarantees: iteration complexity bound, oracle ...
• An update-and-stabilize framework for the minimum-norm-point problem AI翻译
  作者：Fujishige, Satoru; Kitahara, Tomonari; Vegh, Laszlo A.
  作者单位：Kyoto University; Kyushu University; University of London; London School Economics & Political Science
  摘要：We consider the minimum-norm-point (MNP) problem over polyhedra, a well-studied problem that encompasses linear programming. We present a general algorithmic framework that combines two fundamental approaches for this problem: active set methods and first order methods. Our algorithm performs first order update steps, followed by iterations that aim to 'stabilize' the current iterate with additional projections, i.e., find a locally optimal solution whilst keeping the current tight inequalitie...
• Level constrained first order methods for function constrained optimization AI翻译
  作者：Boob, Digvijay; Deng, Qi; Lan, Guanghui
  作者单位：Southern Methodist University; Shanghai Jiao Tong University; University System of Georgia; Georgia Institute of Technology
  摘要：We present a new feasible proximal gradient method for constrained optimization where both the objective and constraint functions are given by summation of a smooth, possibly nonconvex function and a convex simple function. The algorithm converts the original problem into a sequence of convex subproblems. Formulating those subproblems requires the evaluation of at most one gradient-value of the original objective and constraint functions. Either exact or approximate subproblems solutions can b...
• Nonlinear conjugate gradient methods: worst-case convergence rates via computer-assisted analyses AI翻译
  作者：Das Gupta, Shuvomoy; Freund, Robert M.; Sun, Xu Andy; Taylor, Adrien
  作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Centre National de la Recherche Scientifique (CNRS); Universite PSL; Inria
  摘要：We propose a computer-assisted approach to the analysis of the worst-case convergence of nonlinear conjugate gradient methods (NCGMs). Those methods are known for their generally good empirical performances for large-scale optimization, while having relatively incomplete analyses. Using our computer-assisted approach, we establish novel complexity bounds for the Polak-Ribi & egrave;re-Polyak (PRP) and the Fletcher-Reeves (FR) NCGMs for smooth strongly convex minimization. In particular, we con...