-
作者：Simonetti, Luidi; da Cunha, Alexandre Salles; Lucena, Abilio
作者单位：Universidade Federal Fluminense; Universidade Federal de Minas Gerais; Universidade Federal do Rio de Janeiro
摘要：Given an undirected graph G with vertex and edge weights, the k-cardinality tree problem asks for a minimum weight tree of G containing exactly k edges. In this paper we consider a directed graph reformulation of the problem and carry out a polyhedral investigation of the polytope defined by the convex hull of its feasible integral solutions. Three new families of valid inequalities are identified and two of them are proven to be facet implying for that polytope. Additionally, a Branch-and-cut...
-
作者：Robinson, Stephen M.
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：This paper studies the local analysis of equations on a product U x U of Banach spaces, whose variables lie in a subset having the special property that it is locally Lipschitz-homeomorphic to an open subset of U. A prominent example, to which we devote most of the paper, is a system of equations whose variables lie in the graph of a maximal monotone operator. This general formulation covers many specific problems of interest, and our objective is to understand the local behavior of solutions ...
-
作者：Bouza Allende, Gemayqzel; Still, Georg
作者单位：Universidad de la Habana; University of Twente
摘要：Bilevel programs (BL) form a special class of optimization problems. They appear in many models in economics, game theory and mathematical physics. BL programs show a more complicated structure than standard finite problems. We study the so-called KKT-approach for solving bilevel problems, where the lower level minimality condition is replaced by the KKT- or the FJ-condition. This leads to a special structured mathematical program with complementarity constraints. We analyze the KKT-approach f...
-
作者：Schiela, Anton
作者单位：Zuse Institute Berlin
摘要：We propose and analyze an interior point path-following method in function space for state constrained optimal control. Our emphasis is on proving convergence in function space and on constructing a practical path-following algorithm. In particular, the introduction of a pointwise damping step leads to a very efficient method, as verified by numerical experiments.
-
作者：Aggarwal, Ankit; Louis, Anand; Bansal, Manisha; Garg, Naveen; Gupta, Neelima; Gupta, Shubham; Jain, Surabhi
作者单位：University System of Georgia; Georgia Institute of Technology; University of Delhi; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Delhi; Alphabet Inc.; Google Incorporated; Alphabet Inc.; Google Incorporated
摘要：We consider the facility location problem where each facility can serve at most U clients. We analyze a local search algorithm for this problem which uses only the operations of add, delete and swap and prove that any locally optimum solution is no more than 3 times the global optimum. This improves on a result of Chudak and Williamson who proved an approximation ratio of for the same algorithm. We also provide an example which shows that any local search algorithm which uses only these three ...
-
作者：Lewis, Adrian S.; Overton, Michael L.
作者单位：Cornell University; New York University
摘要：We investigate the behavior of quasi-Newton algorithms applied to minimize a nonsmooth function f, not necessarily convex. We introduce an inexact line search that generates a sequence of nested intervals containing a set of points of nonzero measure that satisfy the Armijo and Wolfe conditions if f is absolutely continuous along the line. Furthermore, the line search is guaranteed to terminate if f is semi-algebraic. It seems quite difficult to establish a convergence theorem for quasi-Newton...
-
作者：Adly, Samir; Chau, Oanh
作者单位：Universite de Limoges; University of La Reunion
摘要：We study a class of dynamic thermal sub-differential contact problems with friction, for long memory visco-elastic materials, without the clamped condition, which can be put into a general model of system defined by a second order evolution inequality, coupled with a first order evolution equation. We present and establish an existence and uniqueness result, by using general results on first order evolution inequality, with monotone operators and fixed point methods. Finally a fully discrete s...
-
作者：Dai, Yu-Hong
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
摘要：Consider the BFGS quasi-Newton method applied to a general non-convex function that has continuous second derivatives. This paper aims to construct a four-dimensional example such that the BFGS method need not converge. The example is perfect in the following sense: (a) All the stepsizes are exactly equal to one; the unit stepsize can also be accepted by various line searches including the Wolfe line search and the Arjimo line search; (b) The objective function is strongly convex along each se...
-
作者：Juditsky, Anatoli; Karzan, Fatma Kilinc; Nemirovski, Arkadi
作者单位：Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA); Carnegie Mellon University; University System of Georgia; Georgia Institute of Technology
摘要：In this paper we propose randomized first-order algorithms for solving bilinear saddle points problems. Our developments are motivated by the need for sub-linear time algorithms to solve large-scale parametric bilinear saddle point problems where cheap online assessment of the solution quality is crucial. We present the theoretical efficiency estimates of our algorithms and discuss a number of applications, primarily to the problem of l(1) minimization arising in sparsity-oriented signal proce...
-
作者：Liu, Yongchao; Xu, Huifu
作者单位：Dalian Maritime University; University of Southampton
摘要：In this paper we present a stability analysis of a stochastic optimization problem with stochastic second order dominance constraints. We consider a perturbation of the underlying probability measure in the space of regular measures equipped with pseudometric discrepancy distance (Romisch in Stochastic Programming. Elsevier, Amsterdam, pp 483-554, 2003). By exploiting a result on error bounds in semi-infinite programming due to Gugat (Math Program Ser B 88:255-275, 2000), we show under the Sla...
