1-2期

最新文章

• Solving bilevel programs with the KKT-approach AI翻译
  作者：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...
• An interior point method in function space for the efficient solution of state constrained optimal control problems AI翻译
  作者：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.
• A 3-approximation algorithm for the facility location problem with uniform capacities AI翻译
  作者：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 ...
• Nonsmooth optimization via quasi-Newton methods AI翻译
  作者：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...
• On some dynamic thermal non clamped contact problems AI翻译
  作者：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...
• A perfect example for the BFGS method AI翻译
  作者：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...
• Randomized first order algorithms with applications to l1-minimization AI翻译
  作者：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...
• Stability analysis of stochastic programs with second order dominance constraints AI翻译
  作者：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...
• The GUS-property of second-order cone linear complementarity problems AI翻译
  作者：Yang, Wei Hong; Yuan, Xiaoming
  作者单位：Fudan University; Hong Kong Baptist University
  摘要：The globally uniquely solvable (GUS) property of the linear transformation of the linear complementarity problems over symmetric cones has been studied recently by Gowda et al. via the approach of Euclidean Jordan algebra. In this paper, we contribute a new approach to characterizing the GUS property of the linear transformation of the second-order cone linear complementarity problems (SOCLCP) via some basic linear algebra properties of the involved matrix of SOCLCP. Some more concrete and che...
• Computing the conjugate of convex piecewise linear-quadratic bivariate functions AI翻译
  作者：Gardiner, Bryan; Lucet, Yves
  作者单位：University of British Columbia; University of British Columbia Okanagan
  摘要：We present a new algorithm to compute the Legendre-Fenchel conjugate of convex piecewise linear-quadratic (PLQ) bivariate functions. The algorithm stores a function using a (primal) planar arrangement. It then computes the (dual) arrangement associated with the conjugate by looping through vertices, edges, and faces in the primal arrangement and building associated dual vertices, edges, and faces. Using optimal computational geometry data structures, the algorithm has a linear time worst-case ...