-
作者：Burke, JV; Lewis, AS; Overton, ML
作者单位：University of Washington; University of Washington Seattle; Cornell University; New York University
摘要：The Gauss-Lucas Theorem on the roots of polynomials nicely simplifies the computation of the subderivative and regular subdifferential of the abscissa mapping on polynomials (the maximum of the real parts of the roots). This paper extends this approach to more general functions of the roots. By combining the Gauss-Lucas methodology with an analysis of the splitting behavior of the roots, we obtain characterizations of the subderivative and regular subdifferential for these functions as well. I...
-
作者：Iwata, S; Moriguchi, S; Murota, K
作者单位：University of Tokyo
摘要：This paper presents a faster algorithm for the M-convex submodular flow problem, which is a generalization of the minimum-cost flow problem with an M-convex cost function for the flow-boundary, where an M-convex function is a nonlinear nonseparable discrete convex function on integer points. The algorithm extends the capacity scaling approach for the submodular flow problem by Fleischer, Iwata and McCormick (2002) with the aid of a novel technique of changing the potential by solving maximum s...
-
作者：Liuzzi, G; Lucidi, S; Piccialli, V; Sotgiu, A
作者单位：Sapienza University Rome; Consiglio Nazionale delle Ricerche (CNR); Istituto Nazionale per la Fisica della Materia (INFM-CNR); University of L'Aquila
摘要：In this paper we are concerned with the design of a small low-cost, low-field multipolar magnet for Magnetic Resonance Imaging with a high field uniformity. By introducing appropriate variables, the considered design problem is converted into a global optimization one. This latter problem is solved by means of a new derivative free global optimization method which is a distributed multi-start type algorithm controlled by means of a simulated annealing criterion. In particular, the proposed met...
-
作者：Dentcheva, D; Römisch, W
作者单位：Stevens Institute of Technology; Humboldt University of Berlin
摘要：We consider multistage stochastic optimization models containing nonconvex constraints, e.g., due to logical or integrality requirements. We study three variants of Lagrangian relaxations and of the corresponding decomposition schemes, namely, scenario, nodal and geographical decomposition. Based on convex equivalents for the Lagrangian duals, we compare the duality gaps for these decomposition schemes. The first main result states that scenario decomposition provides a smaller or equal dualit...
-
作者：Goldfarb, D; Scheinberg, K
作者单位：Columbia University; International Business Machines (IBM); IBM USA
摘要：Cholesky factorization has become the method of choice for solving the symmetric system of linear equations arising in interior point methods (IPMs) for linear programming (LP), its main advantages being numerical stability and efficiency for sparse systems. However in the presence of dense columns there is dramatic loss of efficiency. A typical approach to remedy this problem is to apply the Sherman-Morrison-Woodbury (SMW) update formula to the dense part. This approach while being very effic...
-
作者：Prieto-Rumeau, T
作者单位：Universidad Nacional de Educacion a Distancia (UNED)
摘要：We consider a linear programming problem with unknown objective function. Random observations related to the unknown objective function are sequentially available. We define a stochastic algorithm, based on the simplex method, that estimates an optimal solution of the linear programming problem. It is shown that this algorithm converges with probability one to the set of optimal solutions and that its failure probability is of order inversely proportional to the sample size. We also introduce ...
-
作者：Kocvara, M; Outrata, JV
作者单位：University of Erlangen Nuremberg; Czech Academy of Sciences; Institute of Information Theory & Automation of the Czech Academy of Sciences
摘要：We consider a class of optimization problems with a generalized equation among the constraints. This class covers several problem types like MPEC (Mathematical Programs with Equilibrium Constraints) and MPCC (Mathematical Programs with Complementarity Constraints). We briefly review techniques used for numerical solution of these problems: penalty methods, nonlinear programming (NLP) techniques and Implicit Programming approach (ImP). We further present a new theoretical framework for the ImP ...
-
作者：Hall, JAJ; McKinnon, KIM
作者单位：University of Edinburgh
摘要：This paper introduces a class of linear programming examples that cause the simplex method to cycle and that are the simplest possible examples showing this behaviour. The structure of examples from this class repeats after two iterations. Cycling is shown to occur for both the most negative reduced cost and steepest-edge column selection criteria. In addition it is shown that the EXPAND anti-cycling procedure of Gill et al. is not guaranteed to prevent cycling.
-
作者：Dentcheva, D; Ruszczynski, A
作者单位：Stevens Institute of Technology; Rutgers University System; Rutgers University New Brunswick
摘要：We consider a new class of optimization problems involving stochastic dominance constraints of second order. We develop a new splitting approach to these models, optimality conditions and duality theory. These results are used to construct special decomposition methods.
-
作者：Elhedhli, S; Goffin, JL
作者单位：University of Waterloo; McGill University; Universite de Montreal
摘要：This paper presents a novel integration of interior point cutting plane methods within branch-and-price algorithms. Unlike the classical method, columns are generated at a ''central'' dual solution by applying the analytic centre cutting plane method (ACCPM) on the dual of the full master problem. First, we introduce some modifications to ACCPM. We propose a new procedure to recover primal feasibility after adding cuts and use, for the first time, a dual Newton's method to calculate the new an...
