1-2期

最新文章

• A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs AI翻译
  作者：Gouveia, Joao; Laurent, Monique; Parrilo, Pablo A.; Thomas, Rekha
  作者单位：University of Washington; University of Washington Seattle; Universidade de Coimbra; Centrum Wiskunde & Informatica (CWI); Tilburg University; Massachusetts Institute of Technology (MIT)
  摘要：The theta bodies of a polynomial ideal are a series of semidefinite programming relaxations of the convex hull of the real variety of the ideal. In this paper we construct the theta bodies of the vanishing ideal of cycles in a binary matroid. Applied to cuts in graphs, this yields a new hierarchy of semidefinite programming relaxations of the cut polytope of the graph. If the binary matroid avoids certain minors we can characterize when the first theta body in the hierarchy equals the cycle po...
• A continuous-time linear complementarity system for dynamic user equilibria in single bottleneck traffic flows AI翻译
  作者：Pang, Jong-Shi; Han, Lanshan; Ramadurai, Gitakrishnan; Ukkusuri, Satish
  作者单位：University of Illinois System; University of Illinois Urbana-Champaign; Purdue University System; Purdue University; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Madras
  摘要：This paper formally introduces a linear complementarity system (LCS) formulation for a continuous-time, multi-user class, dynamic user equilibrium (DUE) model for the determination of trip timing decisions in a simplified single bottleneck model. Existence of a Lipschitz solution trajectory to the model is established by a constructive time-stepping method whose convergence is rigorously analyzed. The solvability of the time-discretized subproblems by Lemke's algorithm is also proved. Combinin...
• Newton's method for computing a normalized equilibrium in the generalized Nash game through fixed point formulation AI翻译
  作者：von Heusinger, Anna; Kanzow, Christian; Fukushima, Masao
  作者单位：University of Wurzburg; Kyoto University
  摘要：We consider the generalized Nash equilibrium problem (GNEP), where not only the players' cost functions but also their strategy spaces depend on the rivals' decision variables. Existence results for GNEPs are typically shown by using a fixed point argument for a certain set-valued function. Here we use a regularization of this set-valued function in order to obtain a single-valued function that is easier to deal with from a numerical point of view. We show that the fixed points of the latter f...
• A line search exact penalty method using steering rules AI翻译
  作者：Byrd, Richard H.; Lopez-Calva, Gabriel; Nocedal, Jorge
  作者单位：Northwestern University; University of Colorado System; University of Colorado Boulder; Northwestern University
  摘要：Line search algorithms for nonlinear programming must include safeguards to enjoy global convergence properties. This paper describes an exact penalization approach that extends the class of problems that can be solved with line search sequential quadratic programming methods. In the new algorithm, the penalty parameter is adjusted at every iteration to ensure sufficient progress in linear feasibility and to promote acceptance of the step. A trust region is used to assist in the determination ...
• Convex optimization methods for dimension reduction and coefficient estimation in multivariate linear regression AI翻译
  作者：Lu, Zhaosong; Monteiro, Renato D. C.; Yuan, Ming
  作者单位：Simon Fraser University; University System of Georgia; Georgia Institute of Technology
  摘要：In this paper, we study convex optimization methods for computing the nuclear (or, trace) norm regularized least squares estimate in multivariate linear regression. The so-called factor estimation and selection method, recently proposed by Yuan et al. (J Royal Stat Soc Ser B (Statistical Methodology) 69(3):329-346, 2007) conducts parameter estimation and factor selection simultaneously and have been shown to enjoy nice properties in both large and finite samples. To compute the estimates, howe...
• Multicriteria optimization with a multiobjective golden section line search AI翻译
  作者：Vieira, Douglas A. G.; Takahashi, Ricardo H. C.; Saldanha, Rodney R.
  作者单位：Universidade Federal de Minas Gerais; Universidade Federal de Minas Gerais
  摘要：This work presents an algorithm for multiobjective optimization that is structured as: (i) a descent direction is calculated, within the cone of descent and feasible directions, and (ii) a multiobjective line search is conducted over such direction, with a new multiobjective golden section segment partitioning scheme that directly finds line-constrained efficient points that dominate the current one. This multiobjective line search procedure exploits the structure of the line-constrained effic...
• New results on the Windy Postman Problem AI翻译
  作者：Corberan, Angel; Oswald, Marcus; Plana, Isaac; Reinelt, Gerhard; Sanchis, Jose M.
  作者单位：University of Valencia; Ruprecht Karls University Heidelberg; University of Valencia; Universitat Politecnica de Valencia
  摘要：In this paper, we study the Windy Postman Problem (WPP). This is a well-known Arc Routing Problem that contains the Mixed Chinese Postman Problem (MCPP) as a special case. We extend to arbitrary dimension some new inequalities that complete the description of the polyhedron associated with the Windy Postman Problem over graphs with up to four vertices and ten edges. We introduce two new families of facet-inducing inequalities and prove that these inequalities, along with the already known odd ...
• Minmax-distance approximation and separation problems: geometrical properties AI翻译
  作者：Plastria, Frank; Carrizosa, Emilio
  作者单位：Vrije Universiteit Brussel; University of Sevilla
  摘要：A center hyperplane in the d-dimensional space minimizes the maximum of its distances from a finite set of points A with respect to possibly different gauges. In this note it is shown that a center hyperplane exists which is at (equal) maximum distance from at least d + 1 points of A. Moreover the projections of the points among these which lie above the center hyperplane cannot be separated by another hyperplane from the projections of those that are below it. When all gauges involved are smo...
• Alternatives for testing total dual integrality AI翻译
  作者：O'Shea, Edwin; Seboe, Andras
  作者单位：University College Cork; Communaute Universite Grenoble Alpes; Institut National Polytechnique de Grenoble; Universite Grenoble Alpes (UGA); Centre National de la Recherche Scientifique (CNRS)
  摘要：In this paper we provide characterizing properties of totally dual integral (TDI) systems, among others the following: a system of linear inequalities is TDI if and only if its coefficient vectors form a Hilbert basis, and there exists a test-set for the system's dual integer programs where all test vectors have positive entries equal to 1. Reformulations of this provide relations between computational algebra and integer programming and they contain Applegate, Cook and McCormick's sufficient ...
• Extending the QCR method to general mixed-integer programs AI翻译
  作者：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...