-
作者：Bansal, Nikhil
作者单位：Eindhoven University of Technology
摘要：Recently, there have been several new developments in discrepancy theory based on connections to semidefinite programming. This connection has been useful in several ways. It gives efficient polynomial time algorithms for several problems for which only non-constructive results were previously known. It also leads to several new structural results in discrepancy itself, such as tightness of the so-called determinant lower bound, improved bounds on the discrepancy of the union of set systems an...
-
作者：Billionnet, Alain; Elloumi, Sourour; Lambert, Amelie
作者单位：heSam Universite; Conservatoire National Arts & Metiers (CNAM); Institut Polytechnique de Paris; ENSTA Paris; Ecole Nationale Superieure d'Informatique pour l'Industrie et l'Entreprise (ENSIIE)
摘要：Let (MQP) be a general mixed integer quadratic program that consists of minimizing a quadratic function subject to linear constraints. In this paper, we present a convex reformulation of (MQP), i.e. we reformulate (MQP) into an equivalent program, with a convex objective function. Such a reformulation can be solved by a standard solver that uses a branch and bound algorithm. We prove that our reformulation is the best one within a convex reformulation scheme, from the continuous relaxation poi...
-
作者：Levi, Retsef; Shmoys, David B.; Swamy, Chaitanya
作者单位：Massachusetts Institute of Technology (MIT); Cornell University; Cornell University; University of Waterloo
摘要：In the capacitated facility location problem with hard capacities, we are given a set of facilities, F, and a set of clients D in a common metric space. Each facility i has a facility opening cost f(i) and capacity u(i) that specifies the maximum number of clients that may be assigned to this facility. We want to open some facilities from the set F and assign each client to an open facility so that at most ui clients are assigned to any open facility i. The cost of assigning client j to facili...
-
作者：Stein, Oliver; Steuermann, Paul
作者单位：Helmholtz Association; Karlsruhe Institute of Technology
摘要：A numerical solution method for semi-infinite optimization problems with arbitrary, not necessarily box-shaped, index sets is presented. Following the ideas of Floudas and Stein (SIAM J Optim 18:1187-1208, 2007), convex relaxations of the lower level problem are adaptively constructed and then reformulated as mathematical programs with complementarity constraints and solved. Although the index set is arbitrary, this approximation produces feasible iterates for the original problem. The convex ...
-
作者：Royset, J. O.
作者单位：United States Department of Defense; United States Navy; Naval Postgraduate School
摘要：Optimality functions define stationarity in nonlinear programming, semi-infinite optimization, and optimal control in some sense. In this paper, we consider optimality functions for stochastic programs with nonlinear, possibly nonconvex, expected value objective and constraint functions. We show that an optimality function directly relates to the difference in function values at a candidate point and a local minimizer. We construct confidence intervals for the value of the optimality function ...
-
作者：Chen, Xiaojun
作者单位：Hong Kong Polytechnic University
摘要：We consider a class of smoothing methods for minimization problems where the feasible set is convex but the objective function is not convex, not differentiable and perhaps not even locally Lipschitz at the solutions. Such optimization problems arise from wide applications including image restoration, signal reconstruction, variable selection, optimal control, stochastic equilibrium and spherical approximations. In this paper, we focus on smoothing methods for solving such optimization problem...
-
作者：Hu, Jing; Mitchell, John E.; Pang, Jong-Shi
作者单位：Rensselaer Polytechnic Institute; University of Illinois System; University of Illinois Urbana-Champaign
摘要：Filling a gap in nonconvex quadratic programming, this paper shows that the global resolution of a feasible quadratic program (QP), which is not known to be bounded or unbounded below, can be accomplished in finite time by solving two linear programs with linear complementarity constraints, i.e., LPCCs. Specifically, this task can be divided into two LPCCs: the first confirms whether the QP is bounded below on the feasible set and, if not, computes a feasible ray on which the QP is unbounded; ...
-
作者：Curtis, Frank E.; Huber, Johannes; Schenk, Olaf; Waechter, Andreas
作者单位：Northwestern University; Lehigh University; University of Basel; Universita della Svizzera Italiana
摘要：This paper describes an implementation of an interior-point algorithm for large-scale nonlinear optimization. It is based on the algorithm proposed by Curtis et al. (SIAM J Sci Comput 32:3447-3475, 2010), a method that possesses global convergence guarantees to first-order stationary points with the novel feature that inexact search direction calculations are allowed in order to save computational expense. The implementation follows the proposed algorithm, but includes many practical enhanceme...
-
作者：Luedtke, James; Namazifar, Mahdi; Linderoth, Jeff
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：We study approaches for obtaining convex relaxations of global optimization problems containing multilinear functions. Specifically, we compare the concave and convex envelopes of these functions with the relaxations that are obtained with a standard relaxation approach, due to McCormick. The standard approach reformulates the problem to contain only bilinear terms and then relaxes each term independently. We show that for a multilinear function having a single product term, this approach yiel...
-
作者：Fletcher, Roger
作者单位：University of Dundee
摘要：The possibilities inherent in steepest descent methods have been considerably amplified by the introduction of the Barzilai-Borwein choice of step-size, and other related ideas. These methods have proved to be competitive with conjugate gradient methods for the minimization of large dimension unconstrained minimization problems. This paper suggests a method which is able to take advantage of the availability of a few additional 'long' vectors of storage to achieve a significant improvement in ...
