-
作者：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...
-
作者：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...
