-
作者：El Housni, Omar; Goyal, Vineet
作者单位：Columbia University
摘要：In this paper, we consider two-stage adjustable robust linear optimization problems under uncertain constraints and study the performance of piecewise static policies. These are a generalization of static policies where we divide the uncertainty set into several pieces and specify a static solution for each piece. We show that in the worst-case, there is no piecewise static policy with a polynomial number of pieces that has a significantly better performance than an optimal static policy. This...
-
作者：Bettiol, Piernicola; Vinter, Richard B.
作者单位：Universite de Bretagne Occidentale; Imperial College London
摘要：The term 'distance estimate' for state constrained control systems refers to an estimate on the distance of an arbitrary state trajectory from the subset of state trajectories that satisfy a given state constraint. Distance estimates have found widespread application in state constrained optimal control. They have been used to establish regularity properties of the value function, to establish the non-degeneracy of first order conditions of optimality, and to validate the characterization of t...
-
作者：Robinson, Stephen M.
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：The sticky face lemma describes the local behavior of the inverse of the normal-cone operator of a polyhedral convex set. This inverse, when applied to a vector, produces a face of the set. The lemma says that small perturbations of the vector produce only subfaces of the original face. This property is useful in analyzing variational analysis and optimization problems whose underlying sets are convex and polyhedral.
-
作者：Fujishige, Satoru; Tanigawa, Shin-ichi
作者单位：Kyoto University
摘要：Huber et al. (SIAM J Comput 43: 1064-1084, 2014) introduced a concept of skew bisubmodularity, as a generalization of bisubmodularity, in their complexity dichotomy theorem for valued constraint satisfaction problems over the three-value domain, and Huber and Krokhin (SIAM J Discrete Math 28: 1828-1837, 2014) showed the oracle tractability of minimization of skew-bisubmodular functions. Fujishige et al. (Discrete Optim 12: 1-9, 2014) also showed a min-max theorem that characterizes the skew-bi...
-
作者：Bader, Jorg; Hildebrand, Robert; Weismantel, Robert; Zenklusen, Rico
作者单位：Swiss Federal Institutes of Technology Domain; ETH Zurich; International Business Machines (IBM); IBM USA
摘要：We study the reformulation of integer linear programs by means of a mixed integer linear program with fewer integer variables. Such reformulations can be solved efficiently with mixed integer linear programming techniques. We exhibit examples that demonstrate how integer programs can be reformulated using far fewer integer variables. To this end, we introduce a generalization of total unimodularity called the affine TU-dimension of a matrix and study related theory and algorithms for determini...
-
作者：Bianchi, Monica; Hadjisavvas, Nicolas; Pini, Rita
作者单位：Catholic University of the Sacred Heart; King Fahd University of Petroleum & Minerals; University of Milano-Bicocca
摘要：The aim of this paper is to show that every representative function of a maximally monotone operator is the Fitzpatrick transform of a bifunction corresponding to the operator. In fact, for each representative function of the operator, there is a family of equivalent saddle functions (i.e., bifunctions which are concave in the first and convex in the second argument) each of which has as Fitzpatrick transform. In the special case where is the Fitzpatrick function of the operator, the family of...
-
作者：Baiou, Mourad; Barahona, Francisco
作者单位：Centre National de la Recherche Scientifique (CNRS); International Business Machines (IBM); IBM USA
摘要：We study the sparsest cut problem when the capacity-demand graph is planar, and give a combinatorial polynomial algorithm. In this type of graphs there is an edge for each positive capacity and also an edge for each positive demand. We extend this result to graphs with no K5 minor. We also show how to find a maximum concurrent flow in these two cases. We also prove that the sparsest cut problem is NP-hard if we only impose that the capacity-demand graph has no K6 minor. We use ideas that had...
-
作者：Jiang, Rujun; Li, Duan; Wu, Baiyi
作者单位：Chinese University of Hong Kong; Guangdong University of Foreign Studies
摘要：We investigate in this paper the generalized trust region subproblem (GTRS) of minimizing a general quadratic objective function subject to a general quadratic inequality constraint. By applying a simultaneous block diagonalization approach, we obtain a congruent canonical form for the symmetric matrices in both the objective and constraint functions. By exploiting the block separability of the canonical form, we show that all GTRSs with an optimal value bounded from below are second order con...
-
作者：Nguyen, Trang T.; Richard, Jean-Philippe P.; Tawarmalani, Mohit
作者单位：State University System of Florida; University of Florida; Purdue University System; Purdue University
摘要：We consider convex hull descriptions for certain sets described by inequality constraints over a hypercube and propose a lifting-and-projection technique to construct them. The general procedure obtains the convex hulls as an intersection of semi-infinite families of linear inequalities, each derived using lifting techniques that are interpreted using convexification tools. We demonstrate that differentiability and concavity of certain perturbation functions help reduce the number of inequalit...
-
作者：Hoai An Le Thi; Tao Pham Dinh
作者单位：Universite de Lorraine
摘要：The year 2015 marks the 30th birthday of DC (Difference of Convex functions) programming and DCA (DC Algorithms) which constitute the backbone of nonconvex programming and global optimization. In this article we offer a short survey on thirty years of developments of these theoretical and algorithmic tools. The survey is comprised of three parts. In the first part we present a brief history of the field, while in the second we summarize the state-of-the-art results and recent advances. We focu...
