-
作者：Freund, Robert M.; Lu, Haihao
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
摘要：Motivated by recent work of Renegar (A framework for applying subgradient methods to conic optimization problems, 2015) we present new computational methods and associated computational guarantees for solving convex optimization problems using first-order methods. Our problem of interest is the general convex optimization problem , where we presume knowledge of a strict lower bound . [Indeed, is naturally known when optimizing many loss functions in statistics and machine learning (least-squar...
-
作者：Dey, Santanu S.; Molinaro, Marco
作者单位：University System of Georgia; Georgia Institute of Technology; Pontificia Universidade Catolica do Rio de Janeiro
摘要：While many classes of cutting-planes are at the disposal of integer programming solvers, our scientific understanding is far from complete with regards to cutting-plane selection, i.e., the task of selecting a portfolio of cutting-planes to be added to the LP relaxation at a given node of the branch-and-bound tree. In this paper we review the different classes of cutting-planes available, known theoretical results about their relative strength, important issues pertaining to cut selection, and...
-
作者：Gribling, Sander; de Laat, David; Laurent, Monique
作者单位：Centrum Wiskunde & Informatica (CWI); Tilburg University
摘要：In this paper we study optimization problems related to bipartite quantum correlations using techniques from tracial noncommutative polynomial optimization. First we consider the problem of finding the minimal entanglement dimension of such correlations. We construct a hierarchy of semidefinite programming lower bounds and show convergence to a new parameter: the minimal average entanglement dimension, which measures the amount of entanglement needed to reproduce a quantum correlation when acc...
-
作者：Aronna, M. Soledad; Bonnans, J. Frederic; Kroner, Axel
作者单位：Getulio Vargas Foundation; Institut Polytechnique de Paris; ENSTA Paris; Ecole Polytechnique; Universite Paris Saclay
摘要：In this paper we consider second order optimality conditions for a bilinear optimal control problem governed by a strongly continuous semigroup operator, the control entering linearly in the cost function. We derive first and second order optimality conditions, taking advantage of the Goh transform. We then apply the results to the heat and wave equations.
-
作者：Carcamo, Gabriel; Flores-Bazan, Fabian
作者单位：Universidad de Concepcion; Universidad de Concepcion
摘要：Some topological and geometric characterizations of strong duality for a non convex optimization problem under a single equality and geometric constraints are established. In particular, a hidden convexity of the conic hull of joint-range of the pair of functions associated to the original problem, is obtained. Applications to derive (a characterization of the validity of) KKT conditions without standard constraints qualification, are also discussed. It goes beyond the exact penalization techn...
-
作者：Klatte, Diethard; Kummer, Bernd
作者单位：University of Zurich; Humboldt University of Berlin
摘要：We present approaches to (generalized) Newton methods in the framework of generalized equations , where f is a function and M is a multifunction. The Newton steps are defined by approximations of f and the solutions of . We give a unified view of the local convergence analysis of such methods by connecting a certain type of approximation with the desired kind of convergence and different regularity conditions for . Our paper is, on the one hand, thought as a survey of crucial parts of the topi...
-
作者：Izmailov, A. F.; Kurennoy, A. S.; Solodov, M. V.
作者单位：Lomonosov Moscow State University; Peoples Friendship University of Russia; Derzhavin Tambov State University
摘要：We show that if the equation mapping is 2-regular at a solution in some nonzero direction in the null space of its Jacobian (in which case this solution is critical; in particular, the local Lipschitzian error bound does not hold), then this direction defines a star-like domain with nonempty interior from which the iterates generated by a certain class of Newton-type methods necessarily converge to the solution in question. This is despite the solution being degenerate, and possibly non-isolat...
-
作者：Olver, Neil; Zenklusen, Rico
作者单位：Vrije Universiteit Amsterdam; Centrum Wiskunde & Informatica (CWI); Swiss Federal Institutes of Technology Domain; ETH Zurich
摘要：We consider the problem of finding a spanning tree satisfying a family of additional constraints. Several settings have been considered previously, the most famous being the problem of finding a spanning tree with degree constraints. Since the problem is hard, the goal is typically to find a spanning tree that violates the constraints as little as possible. Iterative rounding has become the tool of choice for constrained spanning tree problems. However, iterative rounding approaches are very h...
-
作者：Prakash, Anupam; Sikora, Jamie; Varvitsiotis, Antonios; Wei, Zhaohui
作者单位：Nanyang Technological University; National University of Singapore; Nanyang Technological University
摘要：An n x n matrix X is called completely positive semidefinite (cpsd) if there exist d x d Hermitian positive semidefinite matrices {P-i}(i=1)(n) (for some d >= 1) such that X-ij = Tr(P-i P-j), for all i, j is an element of{1,..., n}. The cpsd-rank of a cpsd matrix is the smallest d >= 1 for which such a representation is possible. In this work we initiate the study of the cpsd-rank which we motivate in two ways. First, the cpsd-rank is a natural non-commutative analogue of the completely positi...
-
作者：Pu, Wenqiang; Liu, Ya-Feng; Yan, Junkun; Liu, Hongwei; Luo, Zhi-Quan
作者单位：Xidian University; Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS; The Chinese University of Hong Kong, Shenzhen; Shenzhen Research Institute of Big Data
摘要：An important step in a multi-sensor surveillance system is to estimate sensor biases from their noisy asynchronous measurements. This estimation problem is computationally challenging due to the highly nonlinear transformation between the global and local coordinate systems as well as the measurement asynchrony from different sensors. In this paper, we propose a novel nonlinear least squares formulation for the problem by assuming the existence of a reference target moving with an (unknown) co...
