-
作者：Malick, Jerome; Roupin, Frederic
作者单位：Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS); Inria; Universite Paris 13; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Information Sciences & Technologies (INS2I)
摘要：This article presents a family of semidefinite programming bounds, obtained by Lagrangian duality, for 0-1 quadratic optimization problems with linear or quadratic constraints. These bounds have useful computational properties: they have a good ratio of tightness to computing time, they can be optimized by a quasi-Newton method, and their final tightness level is controlled by a real parameter. These properties are illustrated on three standard combinatorial optimization problems: unconstraine...
-
作者：Nesterov, Yu
作者单位：Universite Catholique Louvain
摘要：In this paper we analyze several new methods for solving optimization problems with the objective function formed as a sum of two terms: one is smooth and given by a black-box oracle, and another is a simple general convex function with known structure. Despite the absence of good properties of the sum, such problems, both in convex and nonconvex cases, can be solved with efficiency typical for the first part of the objective. For convex problems of the above structure, we consider primal and ...
-
作者：Durea, Marius; Huu Tron Nguyen; Strugariu, Radu
作者单位：Alexandru Ioan Cuza University; Universite de Limoges; Centre National de la Recherche Scientifique (CNRS); GH Asachi Technical University
摘要：In this work we combine in a meaningful way two techniques of variational analysis and nonsmooth optimization. On one hand, we use the error bound approach to study the metric regularity of some special types of multifunctions and, on the other hand, we exploit the incompatibility between the metric regularity and the Pareto minimality. This method allows us to present some -Fermat rules for set-valued optimization problem in the setting of general Banach spaces. Our results are comparable to ...
-
作者：Dempe, S.; Zemkoho, A. B.
作者单位：Technical University Freiberg
摘要：We consider the bilevel programming problem and its optimal value and KKT one level reformulations. The two reformulations are studied in a unified manner and compared in terms of optimal solutions, constraint qualifications and optimality conditions. We also show that any bilevel programming problem where the lower level problem is linear with respect to the lower level variable, is partially calm without any restrictive assumption. Finally, we consider the bilevel demand adjustment problem i...
-
作者：Powell, M. J. D.
作者单位：University of Cambridge
摘要：Some highly successful algorithms for unconstrained minimization without derivatives construct changes to the variables by applying trust region methods to quadratic approximations to the objective function . A quadratic model has (n + 1) (n + 2)/2 independent parameters, but each new model may interpolate only 2n + 1 values of F, for instance. The symmetric Broyden method takes up the remaining freedom by minimizing the Frobenius norm of the difference between the second derivative matrices o...
-
作者：Chen, Xiaojun; Xiang, Shuhuang
作者单位：Hong Kong Polytechnic University; Central South University
摘要：We propose a generalized Newton method for solving the system of nonlinear equations with linear complementarity constraints in the implicit or semi-implicit time-stepping scheme for differential linear complementarity systems (DLCS). We choose a specific solution from the solution set of the linear complementarity constraints to define a locally Lipschitz continuous right-hand-side function in the differential equation. Moreover, we present a simple formula to compute an element in the Clarke...
-
作者：Kong, Nan; Schaefer, Andrew J.; Ahmed, Shabbir
作者单位：Purdue University System; Purdue University; Pennsylvania Commonwealth System of Higher Education (PCSHE); University of Pittsburgh; University System of Georgia; Georgia Institute of Technology
摘要：We consider totally unimodular (TU) stochastic programs, that is, two-stage stochastic programs whose extensive-form constraint matrix is TU. We generalize the notion of total unimodularity to apply to sets of matrices and provide properties of such sets. We provide several sufficient conditions on stochastic programs to be TU. When solving TU stochastic problems using the L-shaped method, it is not clear whether the integrality restrictions should be imposed on the master problem. Such restri...
-
作者：Fischer, Anja; Helmberg, Christoph
作者单位：Technische Universitat Chemnitz
摘要：In the quadratic traveling salesman problem a cost is associated with any three nodes traversed in succession. This structure arises, e. g., if the succession of two edges represents energetic conformations, a change of direction or a possible change of transportation means. In the symmetric case, costs do not depend on the direction of traversal. We study the polyhedral structure of a linearized integer programming formulation of the symmetric quadratic traveling salesman problem. Our constru...
-
作者：Hildebrand, Roland
作者单位：Centre National de la Recherche Scientifique (CNRS); Communaute Universite Grenoble Alpes; Universite Grenoble Alpes (UGA)
摘要：Let K subset of R-n be a regular convex cone, let e(1), ... , e(n) is an element of partial derivative K be linearly independent points on the boundary of a compact affine section of the cone, and let x* is an element of K-0 be a point in the relative interior of this section. For k = 1, ... , n, let l(k) be the line through the points e(k) and x*, let y(k) be the intersection point of l(k) with partial derivative K opposite to e(k), and let z(k) be the intersection point of l(k) with the line...
-
作者：Schiro, Dane A.; Pang, Jong-Shi; Shanbhag, Uday V.
作者单位：University of Illinois System; University of Illinois Urbana-Champaign
摘要：Affine generalized Nash equilibrium problems (AGNEPs) represent a class of non-cooperative games in which players solve convex quadratic programs with a set of (linear) constraints that couple the players' variables. The generalized Nash equilibria (GNE) associated with such games are given by solutions to a linear complementarity problem (LCP). This paper treats a large subclass of AGNEPs wherein the coupled constraints are shared by, i.e., common to, the players. Specifically, we present sev...
