-
作者：Meyer, CA; Floudas, CA
作者单位：Princeton University
摘要：Deterministic global optimization algorithms frequently rely on the convex underestimation of nonconvex functions. In this paper we describe the structure of the polyhedral convex envelopes of edge-concave functions over polyhedral domains using geometric arguments. An algorithm for computing the facets of the convex envelope over hyperrectangles in R-3 is described. Sufficient conditions are described under which the convex envelope of a sum of edge-concave functions may be shown to be equiva...
-
作者：Burke, JV; Deng, S
作者单位：University of Washington; University of Washington Seattle; Northern Illinois University
摘要：The notion of weak sharp minima is an important tool in the analysis of the perturbation behavior of certain classes of optimization problems as well as in the convergence analysis of algorithms designed to solve these problems. It has been studied extensively by several authors. This paper is the second of a series on this subject where the basic results on weak sharp minima in Part I are applied to a number of important problems in convex programming. In Part II we study applications to the ...
-
作者：Fischetti, M; Glover, F; Lodi, A
作者单位：University of Padua; University of Colorado System; University of Colorado Boulder; University of Bologna
摘要：In this paper we consider the NP-hard problem of finding a feasible solution ( if any exists) for a generic MIP problem of the form min{c(T) x : Ax >= b, x(j) integer for all j is an element of I}. Trivially, a feasible solution can be defined as a point x*is an element of P := {x : Ax >= b} that is equal to its rounding (x) over tilde, where the rounded point (x) over tilde x is defined by (x) over tilde (j) := [ x*(j)] if j is an element of I and (x) over tilde (j)* := x(j)* otherwise, and [...
-
作者：Neto, JXD; Ferreira, OP; Monteiro, RDC
作者单位：Universidade Federal do Piaui; Universidade Federal de Goias; University System of Georgia; Georgia Institute of Technology
摘要：This paper studies the asymptotic behavior of the central path (X(nu), S(nu), y(nu)) as nu down arrow 0 for a class of degenerate semidefinite programming (SDP) problems, namely those that do not have strictly complementary primal-dual optimal solutions and whose degenerate diagonal blocks X-T(nu) and S-T(nu) of the central path are assumed to satisfy max{||X-T(nu)||, ||S-T(nu)||} = O(root nu). We establish the convergence of the central path towards a primal-dual optimal solution, which is ch...
-
作者：Tawarmalani, M; Sahinidis, NV
作者单位：Purdue University System; Purdue University; University of Illinois System; University of Illinois Urbana-Champaign
摘要：A variety of nonlinear, including semidefinite, relaxations have been developed in recent years for nonconvex optimization problems. Their potential can be realized only if they can be solved with sufficient speed and reliability. Unfortunately, state-of-the-art nonlinear programming codes are significantly slower and numerically unstable compared to linear programming software. In this paper, we facilitate the reliable use of nonlinear convex relaxations in global optimization via a polyhedra...
-
作者：Auslender, A; Teboulle, M
作者单位：Universite Claude Bernard Lyon 1; Tel Aviv University
摘要：We propose new interior projection type methods for solving monotone variational inequalities. The methods can be viewed as a natural extension of the extragradient and hyperplane projection algorithms, and are based on using non Euclidean projection-like maps. We prove global convergence results and establish rate of convergence estimates. The projection-like maps are given by analytical formulas for standard constraints such as box, simplex, and conic type constraints, and generate interior ...
-
作者：Borradaile, G; Van Hentenryck, P
作者单位：Brown University
摘要：Global optimization problems are often approached by branch and bound algorithms which use linear relaxations of the nonlinear constraints computed from the current variable bounds. This paper studies how to derive safe linear relaxations to account for numerical errors arising when computing the linear coefficients. It first proposes two classes of safe linear estimators for univariate functions. Class-1 estimators generalize previously suggested estimators from quadratic to arbitrary functio...
-
作者：Chen, JS; Tseng, P
作者单位：National Taiwan Normal University; University of Washington; University of Washington Seattle
摘要：A popular approach to solving the nonlinear complementarity problem (NCP) is to reformulate it as the global minimization of a certain merit function over R-n. A popular choice of the merit function is the squared norm of the Fischer-Burmeister function, shown to be smooth over R-n and, for monotone NCP, each stationary point is a solution of the NCP. This merit function and its analysis were subsequently extended to the semidefinite complementarity problem (SDCP), although only differentiabil...
-
作者：Balas, E; de Souza, CC
作者单位：Carnegie Mellon University; Universidade Estadual de Campinas
摘要：The vertex separator (VS) problem in a graph G = (V, E) asks for a partition of V into nonempty subsets A, B, C such that there is no edge between A and B, and |C| is minimized subject to a bound on max {|A|, |B|}. We give a mixed integer programming formulation of the problem and investigate the vertex separator polytope (VSP), the convex hull of incidence vectors of vertex separators. Necessary and sufficient conditions are given for the VSP to be full dimensional. Central to our investigati...
-
作者：Ramaswamy, R; Orlin, JB; Chakravarti, N
作者单位：Infosys Limited; Massachusetts Institute of Technology (MIT)
摘要：This paper addresses sensitivity analysis questions concerning the shortest path problem and the maximum capacity path problem in an undirected network. For both problems, we determine the maximum and minimum weights that each edge can have so that a given path remains optimal. For both problems, we show how to determine these maximum and minimum values for all edges in O(m + K log K) time, where m is the number of edges in the network, and K is the number of edges on the given optimal path.
