-
作者：Dolgopolik, M. V.
作者单位：Saint Petersburg State University
摘要：In this article, we present new general results on existence of augmented Lagrange multipliers. We define a penalty function associated with an augmented Lagrangian, and prove that, under a certain growth assumption on the augmenting function, an augmented Lagrange multiplier exists if and only if this penalty function is exact. We also develop a new general approach to the study of augmented Lagrange multipliers called the localization principle. The localization principle allows one to study...
-
作者：Eaton, Julia; Grundel, Sara; Gurbuzbalaban, Mert; Overton, Michael L.
作者单位：University of Washington; University of Washington Tacoma; Max Planck Society; Rutgers University System; Rutgers University New Brunswick; New York University
摘要：The root radius of a polynomial is the maximum of the moduli of its roots (zeros). We consider the following optimization problem: minimize the root radius over monic polynomials of degree n, with either real or complex coefficients, subject to k linearly independent affine constraints on the coefficients. We show that there always exists an optimal polynomial with at most inactive roots, that is, roots whose moduli are strictly less than the optimal root radius. We illustrate our results usin...
-
作者：Goberna, Miguel A.; Kanzi, Nader
作者单位：Universitat d'Alacant; Payame Noor University
摘要：The purpose of this paper is to characterize the weak efficient solutions, the efficient solutions, and the isolated efficient solutions of a given vector optimization problem with finitely many convex objective functions and infinitely many convex constraints. To do this, we introduce new and already known data qualifications (conditions involving the constraints and/or the objectives) in order to get optimality conditions which are expressed in terms of either Karusk-Kuhn-Tucker multipliers ...
-
作者：Custic, Ante; Sokol, Vladyslav; Punnen, Abraham P.; Bhattacharya, Binay
作者单位：Simon Fraser University; Simon Fraser University
摘要：In this paper we study the bilinear assignment problem (BAP) with size parameters m and n, . BAP is a generalization of the well known quadratic assignment problem and the three dimensional assignment problem and hence NP-hard. We show that BAP cannot be approximated within a constant factor unless P = NP even if the associated quadratic cost matrix Q is diagonal. Further, we show that BAP remains NP-hard if , for some fixed r, but is solvable in polynomial time if . When the rank of Q is fixe...
-
作者：Imbach, Remi; Mathis, Pascal; Schreck, Pascal
作者单位：Universite de Lorraine; Universites de Strasbourg Etablissements Associes; Universite de Strasbourg; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute for Engineering & Systems Sciences (INSIS)
摘要：The goal of Point Distance Solving Problems is to find 2D or 3D placements of points knowing distances between some pairs of points. The common guideline is to solve them by a numerical iterative method (e.g. Newton-Raphson method). A sole solution is obtained whereas many exist. However the number of solutions can be exponential and methods should provide solutions close to a sketch drawn by the user. Geometric reasoning can help to simplify the underlying system of equations by changing a fe...
-
作者：Boland, Natashia; Dey, Santanu S.; Kalinowski, Thomas; Molinaro, Marco; Rigterink, Fabian
作者单位：University System of Georgia; Georgia Institute of Technology; University of Newcastle; Pontificia Universidade Catolica do Rio de Janeiro
摘要：We investigate how well the graph of a bilinear function can be approximated by its McCormick relaxation. In particular, we are interested in the smallest number c such that the difference between the concave upper bounding and convex lower bounding functions obtained from the McCormick relaxation approach is at most c times the difference between the concave and convex envelopes. Answering a question of Luedtke, Namazifar and Linderoth, we show that this factor c cannot be bounded by a consta...
-
作者：Curtis, Frank E.; Robinson, Daniel P.; Samadi, Mohammadreza
作者单位：Lehigh University; Johns Hopkins University
摘要：We propose a trust region algorithm for solving nonconvex smooth optimization problems. For any , the algorithm requires at most iterations, function evaluations, and derivative evaluations to drive the norm of the gradient of the objective function below any . This improves upon the bound known to hold for some other trust region algorithms and matches the bound for the recently proposed Adaptive Regularisation framework using Cubics, also known as the arc algorithm. Our algorithm, entitled t...
-
作者：Sikora, Jamie; Varvitsiotis, Antonios
作者单位：National University of Singapore; Nanyang Technological University; Nanyang Technological University
摘要：In this work we study the sets of two-party correlations generated from a Bell scenario involving two spatially separated systems with respect to various physical models. We show that the sets of classical, quantum, no-signaling and unrestricted correlations can be expressed as projections of affine sections of appropriate convex cones. As a by-product, we identify a spectrahedral outer approximation to the set of quantum correlations which is contained in the first level of the Navascu,s, Pir...
-
作者：Ye, Jane J.; Zhou, Jinchuan
作者单位：University of Victoria; Shandong University of Technology
摘要：The proximal, regular and limiting normal cones to the second-order cone complementarity set play important roles in studying mathematical programs with second-order cone complementarity constraints, second-order cone programs, and the second-order cone complementarity problems. It is needed in the first-order optimality conditions for mathematical programs with second-order cone complementarity constraint, the second-order subdifferential criteria in characterizing the full stability for seco...
-
作者：Kurpisz, Adam; Leppanen, Samuli; Mastrolilli, Monaldo
作者单位：Universita della Svizzera Italiana
摘要：In this paper we study the complexity of the Min-sum single machine scheduling problem under algorithms from the Sum-of-Squares/Lasserre hierarchy. We prove the first lower bound for this model by showing that the integrality gap is unbounded at level even for a variant of the problem that is solvable in time by the Moore-Hodgson algorithm, namely Min-number of late jobs. We consider a natural formulation that incorporates the objective function as a constraint and prove the result by partiall...
