-
作者：Sun, DF; Sun, J
作者单位：National University of Singapore; National University of Singapore; National University of Singapore
摘要：We show that the Fischer-Burmeister complementarity functions, associated to the semidefinite cone (SDC) and the second order cone (SOC), respectively, are strongly semismooth everywhere. Interestingly enough, the proof relys on a relationship between the singular value decomposition of a nonsymmetric matrix and the spectral decomposition of a symmetric matrix.
-
作者：Ioffe, A; Lucchetti, RE
作者单位：Technion Israel Institute of Technology; Polytechnic University of Milan
摘要：In this paper we consider the collection of convex programming problems with inequality and equality constraints, in which every problem of the collection is obtained by linear perturbations of the cost function and right-hand side perturbation of the constraints, while the core'' cost function and the left-hand side constraint functions are kept fixed. The main result shows that the set of the problems which are not well-posed is sigma-porous in a certain strong sense. Our results concern bot...
-
作者：Chudak, FA; Williamson, DP
作者单位：International Business Machines (IBM); IBM USA
摘要：In a surprising result, Korupolu, Plaxton, and Rajaraman [13] showed that a simple local search heuristic for the capacitated facility location problem (CFLP) in which the service costs obey the triangle inequality produces a solution in polynomial time which is within a factor of 8 + epsilon of the value of an optimal solution. By simplifying their analysis, we are able to show that the same heuristic produces a solution which is within a factor of 6(1 + epsilon) of the value of an optimal so...
-
作者：Harrington, JE; Hobbs, BF; Pang, JS; Liu, A; Roch, G
作者单位：Johns Hopkins University; Johns Hopkins University; Rensselaer Polytechnic Institute; Johns Hopkins University
摘要：A Nash-based collusive game among a finite set of players is one in which the players coordinate in order for each to gain higher payoffs than those prescribed by the Nash equilibrium solution. In this paper, we study the optimization problem of such a collusive game in which the players collectively maximize the Nash bargaining objective subject to a set of incentive compatibility constraints. We present a smooth reformulation of this optimization problem in terms of a nonlinear complementari...
-
作者：Seiden, SS; Woeginger, GJ
作者单位：Louisiana State University System; Louisiana State University; Eindhoven University of Technology
摘要：In the strip packing problem (a standard version of the two-dimensional cutting stock problem), the goal is to pack a given set of rectangles into a vertical strip of unit width so as to minimize the total height of the strip needed. The k-stage Guillotine packings form a particularly simple and attractive family of feasible solutions for strip packing. We present a complete analysis of the quality of k-stage Guillotine strip packings versus globally optimal packings: k = 2 stages cannot guara...
-
作者：Nowak, N
作者单位：Humboldt University of Berlin
摘要：The purpose of this paper is threefold. First we propose splitting schemes for reformulating non-separable problems as block-separable problems. Second we show that the Lagrangian dual of a block-separable mixed-integer all-quadratic program (MIQQP) can be formulated as an eigenvalue optimization problem keeping the block-separable structure. Finally we report numerical results on solving the eigenvalue optimization problem by a proximal bundle algorithm applying Lagrangian decomposition. The ...
-
作者：Dai, YH; Fletcher, R
作者单位：Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
摘要：The Barzilai-Borwein (BB) gradient method, and some other new gradient methods have shown themselves to be competitive with conjugate gradient methods for solving large dimension nonlinear unconstrained optimization problems. Little is known about the asymptotic behaviour, even when applied to n-dimensional quadratic functions, except in the case that n = 2. We show in the quadratic case how it is possible to compute this asymptotic behaviour, and observe that as n increases there is a transit...
-
作者：Andersen, K; Cornuéjols, G; Li, YJ
作者单位：Carnegie Mellon University; Purdue University System; Purdue University
摘要：In the seventies, Balas introduced intersection cuts for a Mixed Integer Linear Program (MILP), and showed that these cuts can be obtained by a closed form formula from a basis of the standard linear programming relaxation. In the early nineties, Cook, Kannan and Schrijver introduced the split closure of a MILP, and showed that the split closure is a polyhedron. In this paper, we show that the split closure can be obtained using only intersection cuts. We give two different proofs of this resu...
-
作者：Edmond, JF; Thibault, L
作者单位：Universite de Montpellier
摘要：We establish first, in the setting of infinite dimensional Hilbert space, a result concerning the existence of solutions for perturbed sweeping processes whose perturbations are Lipschitz single-valued maps. Then we use this result to extend to the infinite dimensional setting a relaxation result concerning optimal control problems involving such processes.
-
作者：Neumaier, A; Shcherbina, O; Huyer, W; Vinkó, T
作者单位：University of Vienna; Hungarian Academy of Sciences; Szeged University
摘要：Results are reported of testing a number of existing state of the art solvers for global constrained optimization and constraint satisfaction on a set of over 1000 test problems in up to 1000 variables, collected from the literature. The test problems are available online in AMPL and were translated into the input formats of the various solvers using routines from the COCONUT environment. These translators are available online, too.
