-
作者：Vieira, Douglas A. G.; Takahashi, Ricardo H. C.; Saldanha, Rodney R.
作者单位：Universidade Federal de Minas Gerais; Universidade Federal de Minas Gerais
摘要：This work presents an algorithm for multiobjective optimization that is structured as: (i) a descent direction is calculated, within the cone of descent and feasible directions, and (ii) a multiobjective line search is conducted over such direction, with a new multiobjective golden section segment partitioning scheme that directly finds line-constrained efficient points that dominate the current one. This multiobjective line search procedure exploits the structure of the line-constrained effic...
-
作者：Anstreicher, Kurt M.
作者单位：University of Iowa
摘要：We consider convex relaxations for the problem of minimizing a (possibly nonconvex) quadratic objective subject to linear and (possibly nonconvex) quadratic constraints. Let denote the feasible region for the linear constraints. We first show that replacing the quadratic objective and constraint functions with their convex lower envelopes on is dominated by an alternative methodology based on convexifying the range of the quadratic form for . We next show that the use of BB underestimators as ...
-
作者：Misener, Ruth; Floudas, Christodoulos A.
作者单位：Princeton University
摘要：We propose a deterministic global optimization approach, whose novel contributions are rooted in the edge-concave and piecewise-linear underestimators, to address nonconvex mixed-integer quadratically-constrained quadratic programs (MIQCQP) to epsilon-global optimality. The facets of low-dimensional (n <= 3) edge-concave aggregations dominating the termwise relaxation of MIQCQP are introduced at every node of a branch-and-bound tree. Concave multivariable terms and sparsely distributed bilinea...
-
作者：Corberan, Angel; Oswald, Marcus; Plana, Isaac; Reinelt, Gerhard; Sanchis, Jose M.
作者单位：University of Valencia; Ruprecht Karls University Heidelberg; University of Valencia; Universitat Politecnica de Valencia
摘要：In this paper, we study the Windy Postman Problem (WPP). This is a well-known Arc Routing Problem that contains the Mixed Chinese Postman Problem (MCPP) as a special case. We extend to arbitrary dimension some new inequalities that complete the description of the polyhedron associated with the Windy Postman Problem over graphs with up to four vertices and ten edges. We introduce two new families of facet-inducing inequalities and prove that these inequalities, along with the already known odd ...
-
作者：D'Ambrosio, Claudia; Frangioni, Antonio; Liberti, Leo; Lodi, Andrea
作者单位：University of Bologna; Institut Polytechnique de Paris; Ecole Polytechnique; University of Pisa
摘要：One of the foremost difficulties in solving Mixed-Integer Nonlinear Programs, either with exact or heuristic methods, is to find a feasible point. We address this issue with a new feasibility pump algorithm tailored for nonconvex Mixed-Integer Nonlinear Programs. Feasibility pumps are algorithms that iterate between solving a continuous relaxation and a mixed-integer relaxation of the original problems. Such approaches currently exist in the literature for Mixed-Integer Linear Programs and con...
-
作者：Byrd, Richard H.; Chin, Gillian M.; Nocedal, Jorge; Wu, Yuchen
作者单位：Northwestern University; University of Colorado System; University of Colorado Boulder; Alphabet Inc.; Google Incorporated
摘要：This paper presents a methodology for using varying sample sizes in batch-type optimization methods for large-scale machine learning problems. The first part of the paper deals with the delicate issue of dynamic sample selection in the evaluation of the function and gradient. We propose a criterion for increasing the sample size based on variance estimates obtained during the computation of a batch gradient. We establish an complexity bound on the total cost of a gradient method. The second pa...
-
作者：Plastria, Frank; Carrizosa, Emilio
作者单位：Vrije Universiteit Brussel; University of Sevilla
摘要：A center hyperplane in the d-dimensional space minimizes the maximum of its distances from a finite set of points A with respect to possibly different gauges. In this note it is shown that a center hyperplane exists which is at (equal) maximum distance from at least d + 1 points of A. Moreover the projections of the points among these which lie above the center hyperplane cannot be separated by another hyperplane from the projections of those that are below it. When all gauges involved are smo...
-
作者：Dorsch, D.; Guerra-Vazquez, F.; Guenzel, H.; Jongen, H. Th.; Rueckmann, J. -J.
作者单位：University of Birmingham; RWTH Aachen University; Universidad Americas Puebla (UDLAP)
摘要：We consider semi-infinite programming problems depending on a finite dimensional parameter . Provided that is a strongly stable stationary point of , there exists a locally unique and continuous stationary point mapping . This defines the local critical value function , where denotes the objective function of for a given parameter vector . We show that is the sum of a convex function and a smooth function. In particular, this excludes the appearance of negative kinks in the graph of .
-
作者：O'Shea, Edwin; Seboe, Andras
作者单位：University College Cork; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
摘要：In this paper we provide characterizing properties of totally dual integral (TDI) systems, among others the following: a system of linear inequalities is TDI if and only if its coefficient vectors form a Hilbert basis, and there exists a test-set for the system's dual integer programs where all test vectors have positive entries equal to 1. Reformulations of this provide relations between computational algebra and integer programming and they contain Applegate, Cook and McCormick's sufficient ...
-
作者：Amaldi, Edoardo; Bosio, Sandro; Malucelli, Federico
作者单位：Polytechnic University of Milan
摘要：Motivated by a challenging problem arising in wireless network design, we investigate a new nonlinear variant of the set covering problem with hyperbolic objective function. Each ground-set element (user) competes with all its neighbors (interfering users) for a shared resource (the network access time), and the goal is to maximize the sum of the resource share assigned to each ground-set element (the network efficiency) while covering all of them. The hyperbolic objective function privileges ...
