We show that the optimal complexity of Nesterov's smooth first-order optimization algorithm is preserved when the gradient is computed only up to a small, uniformly bounded error. In applications of this method to...
详细信息
We show that the optimal complexity of Nesterov's smooth first-order optimization algorithm is preserved when the gradient is computed only up to a small, uniformly bounded error. In applications of this method to semidefinite programs, this means in some instances computing only a few leading eigenvalues of the current iterate instead of a full matrix exponential, which significantly reduces the method's computational cost. This also allows sparse problems to be solved efficiently using sparse maximum eigenvalue packages.
We propose a distributed algorithm for solving Euclidean metric realization problems arising from large 3-D graphs, using only noisy distance information and without any prior knowledge of the positions of any of the ...
详细信息
We propose a distributed algorithm for solving Euclidean metric realization problems arising from large 3-D graphs, using only noisy distance information and without any prior knowledge of the positions of any of the vertices. In our distributed algorithm, the graph is first subdivided into smaller subgraphs using intelligent clustering methods. Then a semide finite programming relaxation and gradient search method are used to localize each subgraph. Finally, a stitching algorithm is used to find a. ne maps between adjacent clusters, and the positions of all points in a global coordinate system are then derived. In particular, we apply our method to the problem of finding the 3-D molecular configurations of proteins based on a limited number of given pairwise distances between atoms. The protein molecules, all with known molecular configurations, are taken from the Protein Data Bank. Our algorithm is able to reconstruct reliably and efficiently the configurations of large protein molecules from a limited number of pairwise distances corrupted by noise, without incorporating domain knowledge such as the minimum separation distance constraints derived from van der Waals interactions.
Sum of squares (SOS) decompositions for nonnegative polynomials are usually computed numerically, using convex optimization solvers. Although the underlying floating point methods in principle allow for numerical appr...
详细信息
Sum of squares (SOS) decompositions for nonnegative polynomials are usually computed numerically, using convex optimization solvers. Although the underlying floating point methods in principle allow for numerical approximations of arbitrary precision, the computed solutions will never be exact. In many applications such as geometric theorem proving, it is of interest to obtain solutions that can be exactly verified. In this paper, we present a numeric-symbolic method that exploits the efficiency of numerical techniques to obtain an approximate solution, which is then used as a starting point for the computation of an exact rational result. We show that under a strict feasibility assumption, an approximate solution of the semidefinite program is sufficient to obtain a rational decomposition, and quantify the relation between the numerical error versus the rounding tolerance needed. Furthermore, we present an implementation of our method for the computer algebra system Macaulay 2. (C) 2008 Elsevier B.V. All rights reserved.
We investigate the semidefinite programming based sums of squares (SOS) decomposition method, designed for global optimization of polynomials, in the context of the (Maximum) Satisfiability problem. To be specific, we...
详细信息
We investigate the semidefinite programming based sums of squares (SOS) decomposition method, designed for global optimization of polynomials, in the context of the (Maximum) Satisfiability problem. To be specific, we examine the potential of this theory for providing tests for unsatisfiability and providing MAX-SAT upper bounds. We compare the SOS approach with existing upper bound and rounding techniques for the MAX-2-SAT case of Goemans and Williamson [Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42(6) (1995) 1115-1145] and Feige and Goemans [Approximating the value of two prover proof systems, with applications to MAX2SAT and MAXDICUT, in: Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995, pp. 182-189] and the MAX-3-SAT case of Karloff and Zwick [A 7/8-approximation algorithm for MAX 3SAT? in: Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, Miami Beach, FL, USA, IEEE Press, New York, 1997], which are based on semidefinite programming as well. We prove that for each of these algorithms there is an SOS-based counterpart which provides upper bounds at least as tight, but observably tighter in particular cases. Also, we propose a new randomized rounding technique based on the optimal solution of the SOS semidefinite Program (SDP) which we experimentally compare with the appropriate existing rounding techniques. Further we investigate the implications to the decision variant SAT and compare experimental results with those yielded from the higher lifting approach of Anjos [On semidefinite programming relaxations for the satisfiability problem, Math. Methods Oper. Res. 60(3) (2004) 349-367;An improved semidefinite programming relaxation for the satisfiability problem, Math. programming 102(3) (2005) 589-608;semidefinite optimization approaches for satisfiability and maximum-satisfiability problems, J. Satisfiability
We present a new approach to estimate the risk-neutral probability density function (pdf) of the future prices of an underlying asset from the prices of options written on the asset. The estimation is carried out in t...
详细信息
We present a new approach to estimate the risk-neutral probability density function (pdf) of the future prices of an underlying asset from the prices of options written on the asset. The estimation is carried out in the space of cubic spline functions, yielding appropriate smoothness. The resulting optimization problem, used to invert the data and determine the corresponding density function, is a convex quadratic or semidefinite programming problem, depending on the formulation. Both of these problems can be efficiently solved by numerical optimization software. In the quadratic programming formulation the positivity of the risk-neutral pdf is heuristically handled by posing linear inequality constraints at the spline nodes. In the other approach, this property of the risk-neutral pdf is rigorously ensured by using a semidefinite programming characterization of nonnegativity for polynomial functions. We tested our approach using data simulated from Black-Scholes option prices and using market data for options on the S&P 500 Index. The numerical results we present show the effectiveness of our methodology for estimating the risk-neutral probability density function. (c) 2007 Elsevier B.V. All rights reserved.
作者：
Alon, NogaBerger, EliTel Aviv Univ
Raymond & Beverly Sackler Fac Exact Sci Sch Math IL-69978 Tel Aviv Israel Tel Aviv Univ
Raymond & Beverly Sackler Fac Exact Sci Sch Comp Sci IL-69978 Tel Aviv Israel Univ Haifa
Dept Math IL-31905 Haifa Israel
The Grothendieck constant of a graph G = (V, E) is the least constant K such that for every matrix A : V x V -> R, max(f:V -> S vertical bar v vertical bar-1) Sigma({u, v}epsilon E) A(u, v) . {-1, +1}) Sigma({...
详细信息
The Grothendieck constant of a graph G = (V, E) is the least constant K such that for every matrix A : V x V -> R, max(f:V -> S vertical bar v vertical bar-1) Sigma({u, v}epsilon E) A(u, v) . < f(u), f(v)> <= K max(epsilon:V -> {-1, +1}) Sigma({u,) (v}epsilon E) A(u, v) . epsilon(u)epsilon(v) The investigation of this parameter, introduced in [N. Alon, K. Makarychev, Y. Makarychev, A. Naor, Quadratic forms on graphs, in: Proc. of the 37th ACM STOC, ACM Press, Baltimore, 2005, pp. 486-493 (Also: Invent. Math. 163 (2006) 499-522)], is motivated by the algorithmic problem of maximizing the quadratic form Sigma({u, v}epsilon E) A(u, v)epsilon(u)epsilon(v) overall epsilon : V -> {-1, 1}, which arises in the study of correlation clustering and in the investigation of the spin glass model. In the present note we show that for the random graph G(n, p) the value of this parameter is, almost surely, Theta(log(np)). This settles a problem raised in [N. Alon, K. Makarychev, Y. Makarychev, A. Naor, Quadratic forms on graphs, in: Proc. of the 37th ACM STOC, ACM Press, Baltimore, 2005, pp. 486-493 (Also: Invent. Math. 163 (2006) 499-522)]. We also obtain a similar estimate for regular graphs in which the absolute value of each nontrivial eigenvalue is small. (c) 2007 Elsevier B.V. All rights reserved.
In this paper we show how the symmetry present in many linear systems can be exploited to significantly reduce the computational effort required for controller synthesis. This approach may be applied when controller d...
详细信息
In this paper we show how the symmetry present in many linear systems can be exploited to significantly reduce the computational effort required for controller synthesis. This approach may be applied when controller design specifications are expressible via semidefinite programming. In particular, when the overall system description is invariant under unitary coordinate transformations of the state space matrices, synthesis semidefinite programs can be decomposed into a collection of smaller semidefinite programs. (C) 2008 Elsevier Ltd. All rights reserved.
semidefinite programs originating from the Kalman-Yakubovich-Popov lemma are convex optimization problems and there exist polynomial time algorithms that solve them. However, the number of variables is often very larg...
详细信息
semidefinite programs originating from the Kalman-Yakubovich-Popov lemma are convex optimization problems and there exist polynomial time algorithms that solve them. However, the number of variables is often very large making the computational time extremely long. Algorithms more efficient than general purpose solvers are thus needed. To this end structure exploiting algorithms have been proposed, based on the dual formulation. In this paper a cutting plane algorithm is proposed. In a comparison with a general purpose solver and a structure exploiting solver it is shown that the cutting plane based solver can handle optimization problems of much higher dimension. (C) 2007 Elsevier Ltd. All rights reserved.
in this paper, we introduce two new methods for solving binary quadratic problems. While spectral relaxation methods have been the workhorse subroutine for a wide variety of computer vision problems-segmentation, clus...
详细信息
in this paper, we introduce two new methods for solving binary quadratic problems. While spectral relaxation methods have been the workhorse subroutine for a wide variety of computer vision problems-segmentation, clustering, subgraph matching to name a few-it has recently been challenged by semidefinite programming (SDP) relaxations. In fact, it can be shown that SDP relaxations produce better lower bounds than spectral relaxations on binary problems with a quadratic objective function. On the other hand, the Computational complexity for SDP increases rapidly as the number of decision variables grows making them inapplicable to large scale problems. Our methods combine the merits of both spectral and SDP relaxations-better (lower) bounds than traditional spectral methods and considerably faster execution times than SDP. The first method is based on spectral subgradients and can be applied to large scale SDPs with binary decision variables and the second one is based on the trust region problem. Both algorithms have been applied to several large scale vision problems with good performance. (C) 2008 Elsevier Inc. All rights reserved.
We present a compact overview of the recent development in free material optimization (FMO), a branch of structural optimization. The goal of FMO is to design the ultimately best material (its mechanical properties an...
详细信息
We present a compact overview of the recent development in free material optimization (FMO), a branch of structural optimization. The goal of FMO is to design the ultimately best material (its mechanical properties and distribution in space) for a given purpose. We show that the current FMO models naturally lead to linear and non-linear semidefinite programming problems (SDP);their numerical tractability is then guaranteed by recently introduced SDP algorithms.
暂无评论