-
作者：Ruszczynski, Andrzej
作者单位：Rutgers University System; Rutgers University New Brunswick
摘要：We introduce the concept of a Markov risk measure and we use it to formulate risk-averse control problems for two Markov decision models: a finite horizon model and a discounted infinite horizon model. For both models we derive risk-averse dynamic programming equations and a value iteration method. For the infinite horizon problem we develop a risk-averse policy iteration method and we prove its convergence. We also propose a version of the Newton method to solve a nonsmooth equation arising i...
-
作者：Liu, Xinwei; Yuan, Yaxiang
作者单位：Hebei University of Technology; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
摘要：We present a null-space primal-dual interior-point algorithm for solving nonlinear optimization problems with general inequality and equality constraints. The algorithm approximately solves a sequence of equality constrained barrier subproblems by computing a range-space step and a null-space step in every iteration. The a(2) penalty function is taken as the merit function. Under very mild conditions on range-space steps and approximate Hessians, without assuming any regularity, it is proved t...
-
作者：Mahjoub, A. Ridha; McCormick, S. Thomas
作者单位：Universite PSL; Universite Paris-Dauphine; Centre National de la Recherche Scientifique (CNRS); University of British Columbia
摘要：We consider the flow on paths versions of Max Flow and Min Cut when we restrict to paths having at most B arcs, and for versions where we allow fractional solutions or require integral solutions. We show that the continuous versions are polynomial even if B is part of the input, but that the integral versions are polynomial only when B <= 3. However, when B <= 3 we show how to solve the problems using ordinary Max Flow/Min Cut. We also give tight bounds on the integrality gaps between the inte...
-
作者：He, Simai; Li, Zhening; Zhang, Shuzhong
作者单位：Chinese University of Hong Kong; City University of Hong Kong
摘要：In this paper, we consider approximation algorithms for optimizing a generic multi-variate homogeneous polynomial function, subject to homogeneous quadratic constraints. Such optimization models have wide applications, e.g., in signal processing, magnetic resonance imaging (MRI), data training, approximation theory, and portfolio selection. Since polynomial functions are non-convex, the problems under consideration are all NP-hard in general. In this paper we shall focus on polynomial-time app...
-
作者：Buchheim, Christoph; Liers, Frauke; Oswald, Marcus
作者单位：University of Cologne; Dortmund University of Technology; Ruprecht Karls University Heidelberg
摘要：In many practical applications, the task is to optimize a non-linear objective function over the vertices of a well-studied polytope as, e.g., the matching polytope or the travelling salesman polytope (TSP). Prominent examples are the quadratic assignment problem and the quadratic knapsack problem; further applications occur in various areas such as production planning or automatic graph drawing. In order to apply branch-and-cut methods for the exact solution of such problems, the objective fu...
-
作者：Byrd, Richard H.; Curtis, Frank E.; Nocedal, Jorge
作者单位：Northwestern University; University of Colorado System; University of Colorado Boulder; Northwestern University
摘要：We present a matrix-free line search algorithm for large-scale equality constrained optimization that allows for inexact step computations. For strictly convex problems, the method reduces to the inexact sequential quadratic programming approach proposed by Byrd et al. [SIAM J. Optim. 19(1) 351-369, 2008]. For nonconvex problems, the methodology developed in this paper allows for the presence of negative curvature without requiring information about the inertia of the primal-dual iteration mat...
-
作者：Andersen, Kent; Louveaux, Quentin; Weismantel, Robert
作者单位：University of Liege; Otto von Guericke University
摘要：In Andersen et al. (Lecture Notes in Computer Science, vol. 4513, Springer, Berlin, pp. 1-15, 2007) we studied a mixed-integer set arising from two rows of a simplex tableau. We showed that facets of such a set can be obtained from lattice point free triangles and quadrilaterals associated with either three or four variables. In this paper we generalize our findings and show that, when upper bounds on the non-basic variables are also considered, further classes of facets arise that cannot be o...
-
作者：Musitelli, Antoine
作者单位：University of Padua
摘要：Binet matrices generalize network matrices and play an important role in combinatorial optimization. A first polynomial-time algorithm for recognizing binet matrices appeared in the author's doctoral thesis. In this paper, we present some key ideas and results involved in the design of this algorithm. We show how we can find a Camion basis of the input matrix, whenever this one is binet, and then reduce the recognition problem to that of special billet matrices called bicyclic and cyclic.
-
作者：Haddad, Tahar; Thibault, Lionel
作者单位：Universite de Montpellier; Universite de Jijel
摘要：In this paper we prove a theorem on the existence of a global solution of a differential inclusion governed by a class of nonconvex sweeping processes with unbounded pertubations. The perturbations are not required to be convex valued.
-
作者：Pochet, Yves; Wolsey, Laurence A.
作者单位：Universite Catholique Louvain; Universite Catholique Louvain; Universite Catholique Louvain
摘要：We consider the single item lot-sizing problem with capacities that are non-decreasing over time. When the cost function is (i) non-speculative or Wagner-Whitin (for instance, constant unit production costs and non-negative unit holding costs) and (ii) the production set-up costs are non-increasing over time, it is known that the minimum cost lot-sizing problem is polynomially solvable using dynamic programming. When the capacities are non-decreasing, we derive a compact mixed integer programm...
