We make a unified analysis of interior proximal methods of solving convex second-order cone programming problems. These methods use a proximal distance with respect to second-order cones which can be produced with an ...
详细信息
We make a unified analysis of interior proximal methods of solving convex second-order cone programming problems. These methods use a proximal distance with respect to second-order cones which can be produced with an appropriate closed proper univariate function in three ways. Under some mild conditions, the sequence generated is bounded with each limit point being a solution, and global rates of convergence estimates are obtained in terms of objective values. A class of regularized proximal distances is also constructed which can guarantee the global convergence of the sequence to an optimal solution. These results are illustrated with some examples. In addition, we also study the central paths associated with these distance-like functions, and for the linear SOCP we discuss their relations with the sequence generated by the interior proximal methods. From this, we obtain improved convergence results for the sequence for the interior proximal methods using a proximal distance continuous at the boundary of second-order cones. (C) 2010 Elsevier Ltd. All rights reserved.
interior-pointmethods not only are the most effective methods in practice but also have polynomial-time complexity. In this paper we present a primal-dual interior-point algorithm for second-order cone programming pr...
详细信息
作者:
Nguyen, T. D.Welsch, R.UIUC
Newmark Civil Engn Lab 3103 Urbana IL 61801 USA MIT
Alfred P Sloan Sch Management Cambridge MA 02139 USA MIT
Ctr Computat Res Econ & Management Sci Cambridge MA 02139 USA
Robust linear regression is one of the most popular problems in the robust statistics community. It is often conducted via least trimmed squares, which minimizes the sum of the k smallest squared residuals. Least trim...
详细信息
Robust linear regression is one of the most popular problems in the robust statistics community. It is often conducted via least trimmed squares, which minimizes the sum of the k smallest squared residuals. Least trimmed squares has desirable properties and forms the basis on which several recent robust methods are built, but is very computationally expensive due to its combinatorial nature. It is proven that the least trimmed squares problem is equivalent to a concave minimization problem under a simple linear constraint set. The "maximum trimmed squares", an "almost complementary" problem which maximizes the sum of the q smallest squared residuals, in direct pursuit of the set of outliers rather than the set of clean points, is introduced. Maximum trimmed squares (MTS) can be formulated as a semi-definite programming problem, which can be solved efficiently in polynomial time using interiorpointmethods. In addition, under reasonable assumptions, the maximum trimmed squares problem is guaranteed to identify outliers, no mater how extreme they are. (C) 2009 Elsevier B.V. All rights reserved.
In this paper we study primal-dual interiorpointmethods (IPMs) based on a new class of kernel functions which were designed by M. El Ghami, J.B.M Melissen and C. Roos for linear optimization, we extend the functions...
详细信息
It has recently been shown (Burer, Math Program 120: 479-495, 2009) that a large class of NP-hard nonconvex quadratic programs (NQPs) can be modeled as so-called completely positive programs, i.e., the minimization of...
详细信息
It has recently been shown (Burer, Math Program 120: 479-495, 2009) that a large class of NP-hard nonconvex quadratic programs (NQPs) can be modeled as so-called completely positive programs, i.e., the minimization of a linear function over the convex cone of completely positive matrices subject to linear constraints. Such convex programs are NP-hard in general. A basic tractable relaxation is gotten by approximating the completely positive matrices with doubly nonnegative matrices, i.e., matrices which are both nonnegative and positive semidefinite, resulting in a doubly nonnegative program (DNP). Optimizing a DNP, while polynomial, is expensive in practice for interior-pointmethods. In this paper, we propose a practically efficient decomposition technique, which approximately solves the DNPs while simultaneously producing lower bounds on the original NQP. We illustrate the effectiveness of our approach for solving the basic relaxation of box-constrained NQPs (BoxQPs) and the quadratic assignment problem. For one quadratic assignment instance, a best-known lower bound is obtained. We also incorporate the lower bounds within a branch-and-bound scheme for solving BoxQPs and the quadratic multiple knapsack problem. In particular, to the best of our knowledge, the resulting algorithm for globally solving BoxQPs is the most efficient to date.
In this paper, an efficient primal-dual interiorpoint algorithm for large-update methods is introduced by means of a new kernel function. We analysis the complexity of the algorithm and conclude that its iteration bou...
详细信息
This paper presents a new method for solving a linear discrete-time finite horizon optimal control problem (FHOCP) with quadratic cost and linear constraints on the states and inputs. Such a FHOCP needs to be solved o...
详细信息
interior-pointmethods not only are the most effective methods in practice but also have polynomial-time complexity. In this paper we present a primal-dual interior-point algorithm for second-order cone programming pr...
详细信息
ISBN:
(纸本)9781424477050
interior-pointmethods not only are the most effective methods in practice but also have polynomial-time complexity. In this paper we present a primal-dual interior-point algorithm for second-order cone programming problems based on a simple kernel function. We derive the iteration bounds O(nlogε/n) and O(√nlogε/n) for large- and small-update methods, respectively, which are as good as those in the linearprogramming.
We consider four problems connected by the common thread of geometry. The first three arise in applications that apriori do not involve geometry but this turns out to be the right language for visualizing and analyzin...
We consider four problems connected by the common thread of geometry. The first three arise in applications that apriori do not involve geometry but this turns out to be the right language for visualizing and analyzing them. In the fourth, we generalize some well known results in geometry to the topological plane. The techniques we use come from probability and topology.@pqdt@break@First, we consider two algorithms that work well in practice but the theoretical mechanism behind whose success is not very well understood.@pqdt@break@Greedy routing is a routing mechanism that is commonly used in wireless sensor networks. While routing on the Internet uses standard established protocols, routing in ad-hoc networks with little structure (like sensor networks) is more difficult. Practitioners have devised algorithms that work well in practice, however there were no known theoretical guarantees. We provide the first such result in this area by showing that greedy routing can be made to work on Planar triangulations.@pqdt@break@linearprogramming is a technique for optimizing a linear function subject to linear constraints. Simplex Algorithms are a family of algorithms that have proven quite successful in solving linear Programs in practice. However, examples of linear Programs on which these algorithms are very inefficient have been obtained by researchers. In order to explain this discrepancy between theory and practice, many authors have shown that Simplex Algorithms are efficient in expectation on randomized linear Programs. We strengthen these results by proving a partial concentration bound for the SHADOW V ERTEX Simplex Algorithm.@pqdt@break@Next, we point out a limitation in an algorithm that is commonly used by practitioners and suggest a way of overcoming this.@pqdt@break@Recommendation Systems are algorithms that are used to recommend goods (books, movies etc.) to users based on the similarities between their past preferences and those of other users. Low Rank A
interior-pointmethods not only are the most effective methods in practice but also have polynomial-time complexity. In this paper we present a primal-dual interiorpoint algorithm for second-order cone programming pro...
详细信息
interior-pointmethods not only are the most effective methods in practice but also have polynomial-time complexity. In this paper we present a primal-dual interiorpoint algorithm for second-order cone programming problems based on a simple kernel function. We derive the iteration bounds O(nlog n/ε) and O(nlog n/ε) for large- and small-update methods, respectively, which are as good as those in the linearprogramming.
暂无评论