-
作者：Giner, Emmanuel; Penot, Jean-Paul
作者单位：Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Universite Paris Cite; Sorbonne Universite
摘要：We examine how the subdifferentials of nonconvex integral functionals can be deduced from the subdifferentials of the corresponding integrand or at least be estimated with the help of them. In fact, assuming some regularity properties of the integrands, we obtain exact expressions for the subdifferentials of the integral functionals. We draw some consequences in terms of duality for such integral functionals, extending in this way the early work of Rockafellar to the nonconvex case.
-
作者：Braun, Gabor; Pokutta, Sebastian; Roy, Aurko
作者单位：University System of Georgia; Georgia Institute of Technology; University System of Georgia; Georgia Institute of Technology
摘要：We generalize the reduction mechanism for linear programming problems and semidefinite programming problems from Braun et al. (Inapproximability of combinatorial problems via small LPs and SDPs, 2015) in two ways (1) relaxing the requirement of affineness, and (2) extending to fractional optimization problems. As applications we provide several new LP-hardness and SDP-hardness results, e.g., for the SparsestCut problem, the BalancedSeparator problem, and the MaxCut problem and show how to exte...
-
作者：Svensson, Ola; Tarnawski, Jakub; Vegh, Laszlo A.
作者单位：Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; University of London; London School Economics & Political Science
摘要：We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the case of unit edge weights, the first constant factor approximation was given recently by Svensson. This was accomplished by introducing an easier problem called Local-Connectivity ATSP and showing that a good solution to this problem can be used to obtain a constant factor approximation for ATSP. In this paper, we s...
-
作者：Chen, R.; Menickelly, M.; Scheinberg, K.
作者单位：Bosch; Lehigh University
摘要：In this paper, we propose and analyze a trust-region model-based algorithm for solving unconstrained stochastic optimization problems. Our framework utilizes random models of an objective function f(x), obtained from stochastic observations of the function or its gradient. Our method also utilizes estimates of function values to gauge progress that is being made. The convergence analysis relies on requirements that these models and these estimates are sufficiently accurate with high enough, bu...
-
作者：Ahmadi, Amir Ali; Hall, Georgina
作者单位：Princeton University
摘要：We consider the problem of decomposing a multivariate polynomial as the difference of two convex polynomials. We introduce algebraic techniques which reduce this task to linear, second order cone, and semidefinite programming. This allows us to optimize over subsets of valid difference of convex decompositions (dcds) and find ones that speed up the convex-concave procedure. We prove, however, that optimizing over the entire set of dcds is NP-hard.
-
作者：Gotoh, Jun-ya; Takeda, Akiko; Tono, Katsuya
作者单位：Chuo University; Research Organization of Information & Systems (ROIS); Institute of Statistical Mathematics (ISM) - Japan; RIKEN; NEC Corporation
摘要：We propose a DC (Difference of two Convex functions) formulation approach for sparse optimization problems having a cardinality or rank constraint. With the largest-k norm, an exact DC representation of the cardinality constraint is provided. We then transform the cardinality-constrained problem into a penalty function form and derive exact penalty parameter values for some optimization problems, especially for quadratic minimization problems which often appear in practice. A DC Algorithm (DCA...
-
作者：Cseh, Agnes; Kavitha, Telikepalli
作者单位：Hungarian Academy of Sciences; Corvinus University Budapest; Tata Institute of Fundamental Research (TIFR)
摘要：Given a bipartite graph G = (A. B, E) with strict preference lists and given an edge e *. E, we ask if there exists a popular matching in G that contains e *. We call this the popular edge problem. Amatching M is popular if there is no matching M such that the vertices that prefer M to M outnumber those that prefer M to M . It is known that every stable matching is popular; however G may have no stable matching with the edge e *. In this paper we identify another natural subclass of popular ma...
-
作者：Adam, Lukas; Henrion, Rene; Outrata, Jiri
作者单位：Czech Academy of Sciences; Institute of Information Theory & Automation of the Czech Academy of Sciences; Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics
摘要：Depending on whether a mathematical program with equilibrium constraints (MPEC) is considered in its original or its enhanced (via KKT conditions) form, the assumed qualification conditions as well as the derived necessary optimality conditions may differ significantly. In this paper, we study this issue when imposing one of the weakest possible qualification conditions, namely the calmness of the perturbation mapping associated with the respective generalized equations in both forms of the MP...
-
作者：Campi, M. C.; Garatti, S.
作者单位：University of Brescia; Polytechnic University of Milan
摘要：We consider convex optimization problems with uncertain, probabilistically described, constraints. In this context, scenario optimization is a well recognized methodology where a sample of the constraints is used to describe uncertainty. One says that the scenario solution generalizes well, or has a high robustness level, if it satisfies most of the other constraints besides those in the sample. Over the past 10 years, the main theoretical investigations on the scenario approach have related t...
-
作者：Del Pia, Alberto
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：Concave mixed- integer quadratic programming is the problem of minimizing a concave quadratic polynomial over the mixed- integer points in a polyhedral region. In this work we describe an algorithm that finds an - approximate solution to a concave mixed- integer quadratic programming problem. The running time of the proposed algorithm is polynomial in the size of the problem and in 1/ , provided that the number of integer variables and the number of negative eigenvalues of the objective functi...
