-
作者：Giallombardo, Giovanni; Ralph, Daniel
作者单位：University of Calabria; University of Cambridge
摘要：We study piecewise decomposition methods for mathematical programs with equilibrium constraints (MPECs) for which all constraint functions are linear. At each iteration of a decomposition method, one step of a nonlinear programming scheme is applied to one piece of the MPEC to obtain the next iterate. Our goal is to understand global convergence to B-stationary points of these methods when the embedded nonlinear programming solver is a trust-region scheme, and the selection of pieces is determ...
-
作者：Drummond, L. M. Grana; Maculan, N.; Svaiter, B. F.
作者单位：Universidade Federal do Rio de Janeiro; Universidade Federal do Rio de Janeiro
摘要：We present a geometrical interpretation of the weighting method for constrained (finite dimensional) vector optimization. This approach is based on rigid movements which separate the image set from the negative of the ordering cone. We study conditions on the existence of such translations in terms of the boundedness of the scalar problems produced by the weighting method. Finally, using recession cones, we obtain the main result of our work: a sufficient condition under which weighting vector...
-
作者：Corvellec, Jean-Noel; Motreanu, Viorica V.
作者单位：Universite Perpignan Via Domitia
摘要：As a development of the theory of linear error bounds for lower semicontinuous functions defined on complete metric spaces, introduced in Aze et al. (Nonlinear Anal 49, 643-670, 2002) and refined in Aze and Corvellec (ESAIM Control Optim Calc Var 10, 409-425, 2004), we propose a similar approach to nonlinear error bounds, based on the notion of strong slope, the variational principle, and the change-of-metric principle, the latter allowing to obtain sharp estimates for such error bounds throug...
-
作者：Hu, Jian-Feng; Pan, Ping-Qi
作者单位：Southeast University - China
摘要：The simplex algorithm computes the simplex multipliers by solving a system (or two triangular systems) at each iteration. This note offers an efficient approach to updating the simplex multipliers in conjunction with the Bartels-Golub and Forrest-Tomlin updates for LU factors of the basis. It only solves one triangular system. The approach was implemented within and tested against MINOS 5.51 on 129 problems from Netlib, Kennington and BPMPD. Computational results show that the new approach imp...
-
作者：Lam, Fumei; Newman, Alantha
作者单位：Massachusetts Institute of Technology (MIT); Max Planck Society
摘要：In the traveling salesman path problem, we are given a set of cities, traveling costs between city pairs and fixed source and destination cities. The objective is to find a minimum cost path from the source to destination visiting all cities exactly once. In this paper, we study polyhedral and combinatorial properties of a variant we call the traveling salesman walk problem, in which the objective is to find a minimum cost walk from the source to destination visiting all cities at least once. ...
-
作者：Naumann, Uwe
作者单位：RWTH Aachen University
摘要：We show that the problem of accumulating Jacobian matrices by using a minimal number of floating-point operations is NP-complete by reduction from Ensemble Computation. The proof makes use of the fact that, deviating from the state-of-the-art assumption, algebraic dependences can exist between the local partial derivatives. It follows immediately that the same problem for directional derivatives, adjoints, and higher derivatives is NP-complete, too.
-
作者：Ben-Tal, Aharon; Nemirovski, Arkadi
作者单位：University System of Georgia; Georgia Institute of Technology; Technion Israel Institute of Technology
摘要：Robust Optimization is a rapidly developing methodology for handling optimization problems affected by non-stochastic uncertain-but- bounded data perturbations. In this paper, we overview several selected topics in this popular area, specifically, (1) recent extensions of the basic concept of robust counterpart of an optimization problem with uncertain data, (2) tractability of robust counterparts, (3) links between RO and traditional chance constrained settings of problems with stochastic dat...
-
作者：Monteiro, Renato D. C.; Tsuchiya, Takashi
作者单位：University System of Georgia; Georgia Institute of Technology; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan
摘要：The main goals of this paper are to: i) relate two iteration-complexity bounds derived for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) algorithm for linear programming (LP), and; ii) study the geometrical structure of the LP central path. The first iteration-complexity bound for the MTY P-C algorithm considered in this paper is expressed in terms of the integral of a certain curvature function over the traversed portion of the central path. The second iteration-complexity bound, derived r...
-
作者：Zhao, M.; de Farias, I. R., Jr.
作者单位：State University of New York (SUNY) System; University at Buffalo, SUNY; State University of New York (SUNY) System; SUNY Optometry; SUNY Maritime College; SUNY Community College
摘要：We study the set = {(x, y) is an element of R+ x Z(n) : x + B(j)y(j) >= b(j), j=1,..., n}, where B-j, b(j) is an element of R+ -{0}, j = 1,..., n, and B-1 vertical bar...vertical bar B-n. The set S generalizes the mixed-integer rounding (MIR) set of Nemhauser and Wolsey and the mixing-MIR set of Gunluk and Pochet. In addition, it arises as a substructure in general mixed-integer programming (MIP), such as in lot-sizing. Despite its importance, a number of basic questions about S remain unanswe...
-
作者：Noyan, Nilay; Ruszczynski, Andrzej
作者单位：Rutgers University System; Rutgers University New Brunswick; Sabanci University
摘要：Stochastic dominance relations are well studied in statistics, decision theory and economics. Recently, there has been significant interest in introducing dominance relations into stochastic optimization problems as constraints. In the discrete case, stochastic optimization models involving second order stochastic dominance constraints can be solved by linear programming. However, problems involving first order stochastic dominance constraints are potentially hard due to the non-convexity of t...
