1期

最新文章

• Special issue: Optimization models and algorithms for data science PREFACE AI翻译
  作者：Parpas, Panos; Ralph, Daniel; Wiesemann, Wolfram
  作者单位：Imperial College London; Imperial College London; University of Cambridge
• A study of the difference-of-convex approach for solving linear programs with complementarity constraints AI翻译
  作者：Jara-Moroni, Francisco; Pang, Jong-Shi; Wachter, Andreas
  作者单位：Northwestern University; University of Southern California
  摘要：This paper studies the difference-of-convex (DC) penalty formulations and the associated difference-of-convex algorithm (DCA) for computing stationary solutions of linear programs with complementarity constraints (LPCCs). We focus on three such formulations and establish connections between their stationary solutions and those of the LPCC. Improvements of the DCA are proposed to remedy some drawbacks in a straightforward adaptation of the DCA to these formulations. Extensive numerical results,...
• Primal and dual predicted decrease approximation methods AI翻译
  作者：Beck, Amir; Pauwels, Edouard; Sabach, Shoham
  作者单位：Technion Israel Institute of Technology; Universite de Toulouse; Universite Toulouse III - Paul Sabatier
  摘要：We introduce the notion of predicted decrease approximation (PDA) for constrained convex optimization, a flexible framework which includes as special cases known algorithms such as generalized conditional gradient, proximal gradient, greedy coordinate descent for separable constraints and working set methods for linear equality constraints with bounds. The new scheme allows the development of a unified convergence analysis for these methods. We further consider a partially strongly convex nons...
• On minimizing difference of a SOS-convex polynomial and a support function over a SOS-concave matrix polynomial constraint AI翻译
  作者：Lee, Jae Hyoung; Lee, Gue Myung
  作者单位：Pukyong National University
  摘要：In this paper, we establish tractable sum of squares characterizations of the containment of a convex set, defined by a SOS-concave matrix inequality, in a non-convex set, defined by difference of a SOS-convex polynomial and a support function, with Slater's condition. Using our set containment characterization, we derive a zero duality gap result for a DC optimization problem with a SOS-convex polynomial and a support function, its sum of squares polynomial relaxation dual problem, the semide...
• Competitive online algorithms for resource allocation over the positive semidefinite cone AI翻译
  作者：Eghbahi, Reza; Saunderson, James; Fazel, Maryam
  作者单位：Cisco Systems Inc; Cisco USA; Monash University; University of Washington; University of Washington Seattle
  摘要：We consider a new and general online resource allocation problem, where the goal is to maximize a function of a positive semidefinite (PSD) matrix with a scalar budget constraint. The problem data arrives online, and the algorithm needs to make an irrevocable decision at each step. Of particular interest are classic experiment design problems in the online setting, with the algorithm deciding whether to allocate budget to each experiment as new experiments become available sequentially. We ana...
• Algorithmic and modeling insights via volumetric comparison of polyhedral relaxations AI翻译
  作者：Lee, Jon; Skipper, Daphne; Speakman, Emily
  作者单位：University of Michigan System; University of Michigan; United States Department of Defense; United States Navy; United States Naval Academy; Otto von Guericke University
  摘要：This is mostly a survey on some mathematical results concerning volumes of polytopes of interest in non-convex optimization. Our motivation is in geometrically comparing relaxations in the context of mixed-integer linear and nonlinear optimization, with the goal of gaining algorithmic and modeling insights. We consider relaxations of: fixed-charge formulations, vertex packing polytopes, boolean-quadric polytopes, and relaxations of graphs of monomials on box domains. Besides surveying the area...
• Special Issue: DC Programming - Theory, Algorithms and Applications Preface AI翻译
  作者：Hoai An Le Thi; Tao Pham Dinh
  作者单位：Universite de Lorraine
• Accelerating the DC algorithm for smooth functions AI翻译
  作者：Aragon Artacho, Francisco J.; Fleming, Ronan M. T.; Vuong, Phan T.
  作者单位：Universitat d'Alacant; University of Luxembourg
  摘要：We introduce two new algorithms to minimise smooth difference of convex (DC) functions that accelerate the convergence of the classical DC algorithm (DCA). We prove that the point computed by DCA can be used to define a descent direction for the objective function evaluated at this point. Our algorithms are based on a combination of DCA together with a line search step that uses this descent direction. Convergence of the algorithms is proved and the rate of convergence is analysed under the Ao...
• Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming AI翻译
  作者：Wu, Chenchen; Wang, Yishui; Lu, Zaixin; Pardalos, Panos M.; Xu, Dachuan; Zhang, Zhao; Du, Ding-Zhu
  作者单位：Tianjin University of Technology; Beijing University of Technology; Washington State University; State University System of Florida; University of Florida; Beijing University of Technology; Zhejiang Normal University
  摘要：In this paper, we consider the maximum and minimum versions of degree-concentrated fault-tolerant spanning subgraph problem which has many applications in network communications. We prove that both this two problems are NP-hard. For the maximum version, we use DC programming relaxation to propose a heuristic algorithm. Numerical tests indicate that the proposed algorithm is efficient and effective. For the minimum version, we also formulate it as a DC program, and show that the DC algorithm do...
• Monotone operator theory in convex optimization AI翻译
  作者：Combettes, Patrick L.
  作者单位：North Carolina State University
  摘要：Several aspects of the interplay between monotone operator theory and convex optimization are presented. The crucial role played by monotone operators in the analysis and the numerical solution of convex minimization problems is emphasized. We review the properties of subdifferentials as maximally monotone operators and, in tandem, investigate those of proximity operators as resolvents. In particular, we study new transformations which map proximity operators to proximity operators, and establ...