-
作者：Dash, Sanjeeb; Dobbs, Neil B.; Guenluek, Oktay; Nowicki, Tomasz J.; Swirszcz, Grzegorz M.
作者单位：International Business Machines (IBM); IBM USA; University of Helsinki
摘要：In this paper we study the relationship between valid inequalities for mixed-integer sets, lattice-free sets associated with these inequalities and the multi-branch split cuts introduced by Li and Richard (Discret Optim 5:724-734, 2008). By analyzing -dimensional lattice-free sets, we prove that for every integer there exists a positive integer such that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with integer variables is a -branch split cut. We use th...
-
作者：Murota, Kazuo; Shioura, Akiyoshi
作者单位：University of Tokyo; Tohoku University
摘要：Dijkstra's algorithm is a well-known algorithm for the single-source shortest path problem in a directed graph with nonnegative edge length. We discuss Dijkstra's algorithm from the viewpoint of discrete convex analysis, where the concept of discrete convexity called L-convexity plays a central role. We observe first that the dual of the linear programming (LP) formulation of the shortest path problem can be seen as a special case of L-concave function maximization. We then point out that the ...
-
作者：Conforti, Michele; Del Pia, Alberto
作者单位：University of Padua; Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：Given a polyhedron with facets, whose interior contains no integral points, and a polyhedron , recent work in integer programming has focused on characterizing the convex hull of minus the interior of . We show that to obtain such a characterization it suffices to consider all relaxations of defined by at most among the inequalities defining . This extends a result by Andersen, Cornu,jols, and Li.
-
作者：Dentcheva, Darinka; Ruszczynski, Andrzej
作者单位：Stevens Institute of Technology; Rutgers University System; Rutgers University New Brunswick
摘要：We propose a novel approach to quantification of risk preferences on the space of nondecreasing functions. When applied to law invariant risk preferences among random variables, it compares their quantile functions. The axioms on quantile functions impose relations among comonotonic random variables. We infer the existence of a numerical representation of the preference relation in the form of a quantile-based measure of risk. Using conjugate duality theory by pairing the Banach space of bound...
-
作者：Khajavirad, Aida; Michalek, Jeremy J.; Sahinidis, Nikolaos V.
作者单位：International Business Machines (IBM); IBM USA; Carnegie Mellon University; Carnegie Mellon University; Carnegie Mellon University
摘要：We propose to strengthen standard factorable relaxations of global optimization problems through the use of functional transformations of intermediate expressions. In particular, we exploit convex transformability of the component functions of factorable programs as a tool in the generation of bounds. We define suitable forms of transforming functions and assess, theoretically and computationally, the sharpness of the resulting relaxations in comparison to existing schemes.
-
作者：Bouchitte, Guy; Fragala, Ilaria; Lucardesi, Ilaria
作者单位：Universite de Toulon; Polytechnic University of Milan
摘要：For varying among open bounded sets in , we consider shape functionals defined as the infimum over a Sobolev space of an integral energy of the kind , under Dirichlet or Neumann conditions on . Under fairly weak assumptions on the integrands and , we prove that, when a given domain is deformed into a one-parameter family of domains through an initial velocity field , the corresponding shape derivative of at in the direction of exists. Under some further regularity assumptions, we show that the...
-
作者：Oliveira, W. de; Sagastizabal, C.; Lemarechal, C.
作者单位：Instituto Nacional de Matematica Pura e Aplicada (IMPA); Instituto Nacional de Matematica Pura e Aplicada (IMPA); Inria
摘要：The last few years have seen the advent of a new generation of bundle methods, capable to handle inexact oracles, polluted by noise. Proving convergence of a bundle method is never simple and coping with inexact oracles substantially increases the technicalities. Besides, several variants exist to deal with noise, each one needing an ad hoc proof to show convergence. We state a synthetic convergence theory, in which we highlight the main arguments and specify which assumption is used to establ...
-
作者：Drusvyatskiy, D.; Lewis, A. S.
作者单位：Cornell University
摘要：Around a solution of an optimization problem, an identifiable subset of the feasible region is one containing all nearby solutions after small perturbations to the problem. A quest for only the most essential ingredients of sensitivity analysis leads us to consider identifiable sets that are minimal. This new notion lays a broad and intuitive variational-analytic foundation for optimality conditions, sensitivity, and active set methods.
-
作者：Jeyakumar, V.; Li, G. Y.
作者单位：University of New South Wales Sydney
摘要：The trust-region problem, which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonlinear optimization problems. It enjoys many attractive properties such as an exact semi-definite linear programming relaxation (SDP-relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having extra linear constraints. This paper shows that two useful and powerful features of the ...
-
作者：Bolte, Jerome; Sabach, Shoham; Teboulle, Marc
作者单位：Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Tel Aviv University
摘要：We introduce a proximal alternating linearized minimization (PALM) algorithm for solving a broad class of nonconvex and nonsmooth minimization problems. Building on the powerful Kurdyka-Aojasiewicz property, we derive a self-contained convergence analysis framework and establish that each bounded sequence generated by PALM globally converges to a critical point. Our approach allows to analyze various classes of nonconvex-nonsmooth problems and related nonconvex proximal forward-backward algori...
