检索结果-内蒙古大学图书馆

A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms

引用

MATHEMATICAL PROGRAMMING 2008年第1期115卷 105-149页

作者： Monteiro, Renato D. C. Tsuchiya, Takashi Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA Inst Stat Math Minato Ku Tokyo 1068569 Japan

The main goals of this paper are to: i) relate two iteration-complexity bounds derived for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) algorithm for linear programming (LP), and;ii) study the geometrical structure of the LP central path. The first iteration-complexity bound for the MTY P-C algorithm considered in this paper is expressed in terms of the integral of a certain curvature function over the traversed portion of the central path. The second iteration-complexity bound, derived recently by the authors using the notion of crossover events introduced by Vavasis and Ye, is expressed in terms of a scale-invariant condition number associated with m x n constraint matrix of the LP. In this paper, we establish a relationship between these bounds by showing that the first one can be majorized by the second one. We also establish a geometric result about the central path which gives a rigorous justification based on the curvature of the central path of a claim made by Vavasis and Ye, in view of the behavior of their layered least squares path following LP method, that the central path consists of O(n(2)) long but straight continuous parts while the remaining curved part is relatively "short".

关键词： interior-point algorithms primal-dual algorithms path-following central path layered least squares steps condition number polynomial complexity crossover events scale-invariance predictor-corrector affine scaling strongly polynomial linear programming curvature

来源：评论

学校读者我要写书评

暂无评论

EXACT REGULARIZATION OF CONVEX PROGRAMS

引用

SIAM JOURNAL ON OPTIMIZATION 2008年第4期18卷 1326-1350页

作者： Friedlander, Michael P. Tseng, Paul Univ British Columbia Dept Comp Sci Vancouver BC V6T 1Z4 Canada Univ Washington Dept Math Seattle WA 98195 USA

The regularization of a convex program is exact if all solutions of the regularized problem are also solutions of the original problem for all values of the regularization parameter below some positive threshold. For a general convex program, we show that the regularization is exact if and only if a certain selection problem has a Lagrange multiplier. Moreover, the regularization parameter threshold is inversely related to the Lagrange multiplier. We use this result to generalize an exact regularization result of Ferris and Mangasarian [Appl. Math. Optim., 23 (1991), pp. 266-273] involving a linearized selection problem. We also use it to derive necessary and sufficient conditions for exact penalization, similar to those obtained by Bertsekas [Math. Programming, 9 (1975), pp. 87-99] and by Bertsekas, Nedic, and Ozdaglar [Convex Analysis and Optimization, Athena Scientific, Belmont, MA, 2003]. When the regularization is not exact, we derive error bounds on the distance from the regularized solution to the original solution set. We also show that existence of a "weak sharp minimum" is in some sense close to being necessary for exact regularization. We illustrate the main result with numerical experiments on the l(1) regularization of benchmark (degenerate) linear programs and semidefinite/second-order cone programs. The experiments demonstrate the usefulness of l(1) regularization in finding sparse solutions.

关键词： convex program conic program linear program regularization exact penalization Lagrange multiplier degeneracy sparse solutions interior-point algorithms

来源：评论

学校读者我要写书评

暂无评论

Several Jordan-algebraic aspects of optimization

引用

OPTIMIZATION 2008年第3期57卷 379-393页

作者： Faybusovich, L. Univ Notre Dame Dept Math Notre Dame IN 46556 USA

We describe some concepts from the theory of Euclidean Jordan algebras and their use in optimization theory. This includes: primal-dual algorithms, optimality conditions, convexity of spectral functions, proof of some... 详细信息

关键词： Jordan algebras optimization interior-point algorithms

来源：评论

学校读者我要写书评

暂无评论

Newton-KKT interior-point methods for indefinite quadratic programming

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2007年第1期36卷 5-41页

作者： Absil, P.-A. Tits, Andre L. Univ Maryland Dept Elect & Comp Engn College Pk MD 20742 USA Univ Maryland Syst Res Inst College Pk MD 20742 USA Univ Catholique Louvain Dept Ingn Math B-1348 Louvain Belgium

Two interior-point algorithms are proposed and analyzed, for the (local) Solution of (possibly) indefinite quadratic programming problems. They are of the Newton-KKT variety in that (Much like in the case of primal-dual algorithms for linear programming) search directions for the "primal" variables and the Karush-Kuhn-Tucker (KKT) multiplier estimates are components of the Newton (or quasi-Newton) direction for the Solution of the equalities in the first-order KKT conditions of optimality or a perturbed version of these conditions. Our algorithms are adapted from previously proposed algorithms for convex quadratic programming and general nonlinear programming. First, inspired by recent work by P. Tseng based on a "primal" affine-scaling algorithm (a la Dikin) [J. of Global Optimization, 30 (2004), no. 2, 285-300]. we consider a simple Newton-KKT affine-scaling algorithm. Then, a "barrier" version of the same algorithm is considered, which reduces to the affine-scaling version when the barrier parameter is set to zero at every iteration, rather than to the prescribed value. Global and local quadratic convergence are proved under nondegeneracy assumptions for both algorithms. Numerical results on randomly generated problems Suggest that the proposed algorithms may be of great practical interest.

关键词： interior-point algorithms primal-dual algorithms indefinite quadratic programming Newton-KKT

来源：评论

学校读者我要写书评

暂无评论

Improved complexity results on solving real-number linear feasibility problems

引用

MATHEMATICAL PROGRAMMING 2006年第2期106卷 339-363页

作者： Ye, YY Stanford Univ Dept Management Sci & Engn Stanford CA 94305 USA

We present complexity results on solving real-number standard linear programs LP(A, b, c), where the constraint matrix A is an element of R-m x n, the right-hand-side vector b is an element of R-m and the objective coefficient vector c is an element of R-n are real. In particular, we present a two-layered interior-point method and show that LP(A, b, 0), i.e., the linear feasibility problem Ax = b and x >= 0, can be solved in in O(n(2.5)c(A)) interior-point method iterations. Here 0 is the vector of all zeros and c(A) is the condition measure of matrix A defined in [25]. This complexity iteration bound is reduced by a factor n from that for general LP(A, b, c) in [ 25]. We also prove that the iteration bound will be further reduced to O(n(1.5)c(A)) for LP(A, 0, 0), i.e., for the homogeneous linear feasibility problem. These results are surprising since the classical view has been that linear feasibility would be as hard as linear programming.

关键词： POLYNOMIAL-TIME ALGORITHM interior-point algorithms PATH VARIANT variants Complexity Chpher(0) Zero Element Cloning Vectors Lipoprotein(a) Linear linear programming iterative methods Polynomial time

来源：评论

学校读者我要写书评

暂无评论

On some interior-point algorithms for nonconvex quadratic optimization

引用

MATHEMATICAL PROGRAMMING 2002年第2期93卷 217-225页

作者： Tseng, P Ye, YY Univ Washington Dept Math Seattle WA 98195 USA Univ Iowa Dept Management Sci Iowa City IA 52242 USA

Recently, interior-point algorithms have been applied to nonlinear and nonconvex optimization. Most of these algorithms are either primal-dual path-following or affine-scaling in nature, and some of them are conjectured to converge to a local minimum. We give several examples to show that this may be untrue and we suggest some strategies for overcoming this difficulty.

关键词： nonconvex quadratic optimization local minimum interior-point algorithms trust region branch-and-cut

来源：评论

学校读者我要写书评

暂无评论

A new iteration-complexity bound for the MTY predictor-corrector algorithm

引用

SIAM JOURNAL ON OPTIMIZATION 2005年第2期15卷 319-347页

作者： Monteiro, RDC Tsuchiya, T Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA Inst Stat Math Minato Ku Tokyo 1068569 Japan

In this paper we present a new iteration-complexity bound for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) primal-dual interior-point algorithm for linear programming. The analysis of the paper is based on the important notion of crossover events introduced by Vavasis and Ye. For a standard form linear program min{c(T)x : Ax = b, x >= 0} with decision variable x is an element of R(n), we show that the MTY P-C algorithm, started from a well-centered interior-feasible solution with duality gap n mu(0), finds an interior-feasible solution with duality gap less than n eta in O(T(mu(0)/eta) + n(3.5) log((chi) over bar (A)*)) iterations, where T(t) = min{n(2) log(log t), log t} for all t > 0 and (chi) over bar (A)* is a scaling invariant condition number associated with the matrix A. More specifically, (chi) over bar (A)* is the infimum of all the conditions numbers (chi) over bar (AD), where D varies over the set of positive diagonal matrices. Under the setting of the Turing machine model, our analysis yields an O(n(3.5) L(A) + min{n(2) log L, L}) iteration-complexity bound for the MTY P-C algorithm to find a primal-dual optimal solution, where LA and L are the input sizes of the matrix A and the data (A, b, c), respectively. This contrasts well with the classical iteration- complexity bound for the MTY P-C algorithm, which depends linearly on L instead of log L.

来源：评论

学校读者我要写书评

暂无评论

Multi-target linear-quadratic control problem and second-order cone programming

引用

SYSTEMS & CONTROL LETTERS 2004年第1期52卷 17-23页

作者： Faybusovich, L Mouktonglang, T Univ Notre Dame Dept Math Notre Dame IN 46556 USA

It's shown that a multi-target linear-quadratic control problem can be reduced to the classical tracking problem where the target is a convex combination of the original ones. Finding coefficients in this convex combination is reduced to solving a second-order cone programming problem which can be easily solved using modern interior point algorithms. (C) 2003 Elsevier B.V. All rights reserved.

关键词： linear-quadratic control interior-point algorithms minimax approach

来源：评论

学校读者我要写书评

暂无评论

Some P-properties for linear transformations on Euclidean Jordan algebras

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2004年第1-3期393卷 203-232页

作者： Gowda, MS Sznajder, R Tao, J Univ Maryland Dept Math & Stat Baltimore MD 21250 USA Bowie State Univ Dept Math Bowie MD 20715 USA

A real square matrix is said to be a P-matrix if all its principal minors are positive. It is well known that this property is equivalent to: the nonsign-reversal property based on the componentwise product of vectors, the order P-property based on the minimum and maximum of vectors, uniqueness property in the standard linear complementarity problem, (Lipschitzian) homeomorphism property of the normal map corresponding to the nonnegative orthant. In this article, we extend these notions to a linear transformation defined on a Euclidean Jordan algebra. We study some interconnections between these extended concepts and specialize them to the space S-n of all n x n real symmetric matrices with the semidefinite cone S-+(n) and to the space R-n with the Lorentz cone. (C) 2004 Elsevier Inc. All rights reserved.

关键词： interior-point algorithms COMPLEMENTARITY-PROBLEMS SYMMETRIC CONES SEMIDEFINITE MONOTONICITY LYAPUNOV

来源：评论

学校读者我要写书评

暂无评论

Solving continuous min-max problems by an iterative entropic regularization method

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2004年第3期121卷 597-612页

作者： Sheu, RL Lin, JY Natl Cheng Kung Univ Dept Math Tainan 70101 Taiwan

We propose a method of outer approximations, with each approximate problem smoothed using entropic regularization, to solve continuous min-max problems. By using a well-known uniform error estimate for entropic regularization, convergence of the overall method is shown while allowing each smoothed problem to be solved inexactly. In the case of convex objective function and linear constraints, an interior-point algorithm is proposed to solve the smoothed problem inexactly. Numerical examples are presented to illustrate the behavior of the proposed method.

关键词： min-max problems entropic regularization interior-point algorithms semi-infinite programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：