-
作者：Yamashita, Nobuo
作者单位：Kyoto University
摘要：Quasi-Newton methods are powerful techniques for solving unconstrained minimization problems. Variable metric methods, which include the BFGS and DFP methods, generate dense positive definite approximations and, therefore, are not applicable to large-scale problems. To overcome this difficulty, a sparse quasi-Newton update with positive definite matrix completion that exploits the sparsity pattern E := {( i, j) vertical bar (del(2) f (x))(i j) not equal 0 for some x is an element of R-n} of th...
-
作者：Iwata, Satoru
作者单位：Kyoto University
摘要：Submodular functions often arise in various fields of operations research including discrete optimization, game theory, queueing theory and information theory. In this survey paper, we give overview on the fundamental properties of submodular functions and recent algorithmic devolopments of their minimization.
-
作者：Brinkhuis, Jan; Zhang, Shuzhong
作者单位：Erasmus University Rotterdam - Excl Erasmus MC; Erasmus University Rotterdam; Chinese University of Hong Kong
摘要：This paper attempts to extend the notion of duality for convex cones, by basing it on a prescribed conic ordering and a fixed bilinear mapping. This is an extension of the standard definition of dual cones, in the sense that the nonnegativity of the inner-product is replaced by a pre-specified conic ordering, defined by a convex cone D, and the inner-product itself is replaced by a general multi-dimensional bilinear mapping. This new type of duality is termed the D-induced duality in the paper...
-
作者：Acary, Vincent; Brogliato, Bernard; Goeleven, Daniel
摘要：In this paper we present an extension of Moreau's sweeping process for higher order systems. The dynamical framework is carefully introduced, qualitative, dissipativity, stability, existence, regularity and uniqueness results are given. The time-discretization of these nonsmooth systems with a time-stepping algorithm is also presented. This differential inclusion can be seen as a mathematical formulation of complementarity dynamical systems with arbitrary dimension and arbitrary relative degre...
-
作者：Jansen, Klaus; Zhang, Hu
作者单位：McMaster University; University of Kiel
摘要：In this paper we present approximation algorithms based on a Lagrangian decomposition via a logarithmic potential reduction to solve a general packing or min-max resource sharing problem with M non-negative convex constraints on a convex set B. We generalize a method by Grigoriadis et al. to the case with weak approximate block solvers ( i.e., with only constant, logarithmic or even worse approximation ratios). Given an accuracy e. ( 0, 1), we show that our algorithm needs O( M( ln M + epsilon...
