2004

最新文章

• Optimal accumulation of Jacobian matrices by elimination methods on the dual computational graph AI翻译
  作者：Naumann, U
  作者单位：United States Department of Energy (DOE); Argonne National Laboratory
  摘要：The accumulation of the Jacobian matrix F' of a vector function F : R-n --> R-m can be regarded as a transformation of its linearized computational graph into a subgraph of the directed complete bipartite graph K-n,K-m. This transformation can be performed by applying different elimination techniques that may lead to varying costs for computing F'. This paper introduces face elimination as the basic technique for accumulating Jacobian matrices by using a minimal number of arithmetic operations...
• Polynomiality of an inexact infeasible interior point algorithm for semidefinite programming AI翻译
  作者：Zhou, GL; Toh, KC
  作者单位：Nanyang Technological University; Massachusetts Institute of Technology (MIT); Singapore-MIT Alliance for Research & Technology Centre (SMART); National University of Singapore
  摘要：In this paper we present a primal-dual inexact infeasible interior-point algorithm for semidefinite programming problems (SDP). This algorithm allows the use of search directions that are calculated from the defining linear system with only moderate accuracy, and does not require feasibility to be maintained even if the initial iterate happened to be a feasible solution of the problem. Under a mild assumption on the inexactness, we show that the algorithm can find an epsilon-approximate soluti...
• An accelerated central cutting plane algorithm for linear semi-infinite programming AI翻译
  作者：Betrò, B
  作者单位：Consiglio Nazionale delle Ricerche (CNR); Istituto di Matematica Applicata e Tecnologie Informatiche Enrico Magenes (IMATI-CNR)
  摘要：An algorithm for linear semi-infinite programming is presented which accelerates the convergence of the central cutting plane algorithm first proposed in [4]. Compared with other algorithms, the algorithm in [4] has the advantage of being applicable under mild conditions and of providing feasible solutions. However its convergence has been shown to be rather slow in practical instances. The algorithm proposed in this paper introduces a simple acceleration scheme which gives faster convergence,...
• A mesh-independence result for semismooth Newton methods AI翻译
  作者：Hintermüller, M; Ulbrich, M
  作者单位：University of Graz; Rice University; University of Hamburg
  摘要：For a class of semismooth operator equations a mesh independence result for generalized Newton methods is established. The main result states that the continuous and the discrete Newton process, when initialized properly, converge q-linearly with the same rate. The problem class considered in the paper includes MCP-function based reformulations of first order conditions of a class of control constrained optimal control problems for partial differential equations for which a numerical validatio...
• On the superlinear local convergence of a filter-SQP method AI翻译
  作者：Ulbrich, S
  作者单位：Technical University of Munich
  摘要：Transition to superlinear local convergence is shown for a modified version of the trust-region filter-SQP method for nonlinear programming introduced by Fletcher, Leyffer, and Toint [8]. Hereby, the original trust-region SQP-steps can be used without an additional second order correction. The main modification consists in using the Lagrangian function value instead of the objective function value in the filter together with an appropriate infeasibility measure. Moreover, it is shown that the ...
• An optimization approach to the problem of protein structure prediction AI翻译
  作者：Eskow, E; Bader, B; Byrd, R; Crivelli, S; Head-Gordon, T; Lamberti, V; Schnabel, R
  作者单位：University of Colorado System; University of Colorado Boulder; United States Department of Energy (DOE); Lawrence Berkeley National Laboratory; University of California System; University of California Berkeley; University of California System; University of California Berkeley; United States Department of Energy (DOE); Lawrence Berkeley National Laboratory; United States Department of Energy (DOE); Lawrence Berkeley National Laboratory; University of California System; University of California Berkeley
  摘要：We describe a large-scale, stochastic-perturbation global optimization algorithm used for determining the structure of proteins. The method incorporates secondary structure predictions (which describe the more basic elements of the protein structure) into the starting structures, and thereafter minimizes using a purely physics-based energy model. Results show this method to be particularly successful on protein targets where structural information from similar proteins is unavailable, i.e., th...
• Sub-quadratic convergence of a smoothing Newton algorithm for the P0 and monotone LCP AI翻译
  作者：Huang, ZH; Qi, LQ; Sun, DF
  作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; Hong Kong Polytechnic University; National University of Singapore
  摘要：Given M is an element of R-nxn and q is an element of R-n, the linear complementarity problem (LCP) is to find (x, s) is an element of R-n x R-n such that (x, s) greater than or equal to 0, s = M-x + q, x(T)s = 0. By using the Chen-Harker-Kanzow-Sniale (CHKS) smoothing function, the LCP is reformulated as a system of parameterized smooth-nonsmooth equations. As a result, a smoothing Newton algorithm, which is a modified version of the Qi-Sun-Zhou algorithm [Matheniatical Programming, Vol. 87, ...
• Proximity theorems of discrete convex functions AI翻译
  作者：Murota, K; Tamura, A
  作者单位：University of Tokyo; Japan Science & Technology Agency (JST); Kyoto University
  摘要：A Proximity theorem is a statement that, given an optimization problem and its relaxation, an optimal solution to the original problem exists in a certain neighborhood of a solution to the relaxation. Proximity theorems have been used successfully, for example, in designing efficient algorithms for discrete resource allocation problems. After reviewing the recent results for L-convex and M-convex functions, this paper establishes Proximity theorems for larger classes of discrete convex functio...
• Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation AI翻译
  作者：Chudak, FA; Roughgarden, T; Williamson, DP
  作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; University of California System; University of California Berkeley; International Business Machines (IBM); IBM USA
  摘要：Garg [10] gives two approximation algorithms for the minimum-cost tree spanning k vertices in an undirected graph. Recently Jain and Vazirani [15] discovered primal-dual approximation algorithms for the metric uncapacitated facility location and k-median problems. In this paper we show how Garg's algorithms can be explained simply with ideas introduced by Jain and Vazirani, in particular via a Lagrangean relaxation technique together with the primal-dual method for approximation algorithms. We...
• A globally convergent primal-dual interior-point filter method for nonlinear programming AI翻译
  作者：Ulbrich, M; Ulbrich, S; Vicente, LN
  作者单位：University of Hamburg; University of Munich; Universidade de Coimbra; Rice University; Rice University
  摘要：In this paper, the filter technique of Fletcher and Leyffer (1997) is used to globalize the primal-dual interior-point algorithm for nonlinear programming, avoiding the use of merit functions and the updating of penalty parameters. The new algorithm decomposes the primal-dual step obtained from the perturbed first-order necessary conditions into a normal and a tangential step, whose sizes are controlled by a trust-region type parameter. Each entry in the filter is a pair of coordinates: one re...