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

A Cone Constrained convex program:Structure and Algorithms

Journal of the Operations Research Society of China 2013年第1期1卷 37-53页

作者： Liqun Qi Yi Xu Ya-Xiang Yuan Xinzhen Zhang Department of Applied Mathematics The Hong Kong Polytechnic UniversityHung HomKowloonHong KongChina State Key Laboratory of Scientific/Engineering Computing Institute of Computational Mathematics and Scientific/Engineering ComputingAMSSChinese Academy of SciencesZhong Guan Cun Donglu 55Beijing100190P.R.China Department of Mathematics School of ScienceTianjin UniversityTianjin300072China

In this paper,we consider the positive semi-definite space tensor cone constrained convex program,its structure and *** study defining functions,defining sequences and polyhedral outer approximations for this positive semidefinite space tensor cone,give an error bound for the polyhedral outer approximation approach,and thus establish convergence of three polyhedral outer approximation algorithms for solving this *** then study some other approaches for solving this structured convex *** include the conic linear programming approach,the nonsmooth convex program approach and the bi-level program *** numerical examples are presented.

关键词： convex program Space tensor Positive semi-definiteness Cone Algorithms

来源：评论

学校读者我要写书评

暂无评论

A Perfect Price Discrimination Market Model with Production, and a Rational convex program for It

引用

MATHEMATICS OF OPERATIONS RESEARCH 2011年第4期36卷 762-782页

作者： Goel, Gagan Vazirani, Vijay V. Google Res New York NY 10011 USA Georgia Inst Technol Coll Comp Atlanta GA 30332 USA

Recent results showing PPAD-completeness of the problem of computing an equilibrium for Fisher's market model under additively separable, piecewise-linear, concave (PLC) utilities have dealt a serious blow to the program of obtaining efficient algorithms for computing equilibria in "traditional" market models, and has prompted a search for alternative models that are realistic as well as amenable to efficient computation. In this paper, we show that introducing perfect price discrimination into the Fisher model with PLC utilities renders its equilibrium polynomial time computable. Moreover, its set of equilibria are captured by a convex program that generalizes the classical Eisenberg-Gale program, and always admits a rational solution. We also give a combinatorial, polynomial time algorithm for computing an equilibrium. Next, we introduce production into our model, and again give a rational convex program that captures its equilibria. We use this program to obtain surprisingly simple proofs of both welfare theorems for this model. Finally, we also give an application of our price discrimination market model to online display advertising marketplaces.

关键词： market equilibrium Fisher's market model piecewise-linear concave utilities perfect price discrimination production convex program combinatorial algorithm

来源：评论

学校读者我要写书评

暂无评论

Tree-sparse convex programs

引用

MATHEMATICAL METHODS OF OPERATIONS RESEARCH 2003年第3期56卷 347-376页

作者： Steinbach, MC Informat Techn Berlin Konrad Zuse Zentrum D-14195 Berlin Germany

Dynamic stochastic programs are prototypical for optimization problems with an inherent tree structure inducing characteristic sparsity patterns in the KKT systems of interior methods. We propose an integrated modeling and solution approach for such tree-sparse programs. Three closely related natural formulations are theoretically analyzed from a control-theoretic perspective and compared to each other. Associated KKT system solution algorithms with linear complexity are developed and comparisons to other interior approaches and related problem formulations are discussed.

关键词： convex program tree discrete-time optimal control dynamic stochastic program sparse factorization

来源：评论

学校读者我要写书评

暂无评论

On the relationship between the integer and continuous solutions of convex programs

引用

OPERATIONS RESEARCH LETTERS 2001年第2期29卷 87-92页

作者： Sun, XL Li, D Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China Shanghai Univ Dept Math Shanghai 200436 Peoples R China

A bound is obtained in this note for the distance between the integer and real solutions to convex quadratic programs. This bound is a function of the condition number of the Hessian matrix. We further extend this proximity result to convex programs and mixed-integer convex programs. We also show that this bound is achievable in certain situations and the distance between the integer and continuous minimizers may tend to infinity. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： nonlinear integer program convex program quadratic program proximity analysis

来源：评论

学校读者我要写书评

暂无评论

Just relax: convex programming methods for identifying sparse signals in noise

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2006年第3期52卷 1030-1051页

作者： Tropp, JA Univ Texas Inst Computat Engn & Sci Austin TX 78712 USA

This paper studies a difficult and fundamental problem that arises throughout electrical engineering, applied mathematics, and statistics. Suppose that one forms a short linear combination of elementary signals drawn from a large, fixed collection. Given an observation of the linear combination that has been contaminated with additive noise, the goal is to identify which elementary signals participated and to approximate their coefficients. Although many algorithms have been proposed, there is little theory which guarantees that these algorithms can accurately and efficiently solve the problem. This paper studies a method called convex relaxation, which attempts to recover the ideal sparse signal by solving a convex program. This approach is powerful because the optimization can be completed in polynomial time with standard scientific software. The paper provides general conditions which ensure that convex relaxation succeeds. As evidence of the broad impact of these results, the paper describes how convex relaxation can be used for several concrete signal recovery problems. It also describes applications to channel coding, linear regression, and numerical analysis.

关键词： algorithms approximation methods basis pursuit convex program linear regression optimization methods orthogonal matching pursuit sparse representations

来源：评论

学校读者我要写书评

暂无评论

On superlinear convergence of infeasible interior-point algorithms for linearly constrained convex programs

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 1997年第3期8卷 245-262页

作者： Monteiro, RDC Zhou, FJ School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta

This note derives bounds on the length of the primal-dual affine scaling directions associated with a linearly constrained convex program satisfying the following conditions: 1) the problem has a solution satisfying strict complementarity, 2) the Hessian of the objective function satisfies a certain invariance property. We illustrate the usefulness of these bounds by establishing the superlinear convergence of the algorithm presented in Wright and Ralph [22] for solving the optimality conditions associated with a linearly constrained convex program satisfying the above conditions.

关键词： infeasible-interior-point algorithm affine scaling convex program superlinear convergence

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

On the existence and convergence of the central path for convex programming and some duality results

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 1998年第1期10卷 51-77页

作者： Monteiro, RDC Zhou, FJ Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA

This paper gives several equivalent conditions which guarantee the existence of the weighted central paths for a given convex programming problem satisfying some mild conditions. When the objective and constraint functions of the problem are analytic, we also characterize the limiting behavior of these paths as they approach the set of optimal solutions. A duality relationship between a certain pair of logarithmic barrier problems is also discussed.

关键词： convex program central path duality Wolfe dual Lagrangean dual

来源：评论

学校读者我要写书评

暂无评论

Enhanced Fritz John conditions for convex programming

引用

SIAM JOURNAL ON OPTIMIZATION 2006年第3期16卷 766-797页

作者： Bertsekas, DP Ozdaglar, AE Tseng, P MIT Dept Elect Engn & Comp Sci Cambridge MA 02139 USA Univ Washington Dept Math Seattle WA 98195 USA

We consider convex constrained optimization problems, and we enhance the classical Fritz John optimality conditions to assert the existence of multipliers with special sensitivity properties. In particular, we prove the existence of Fritz John multipliers that are informative in the sense that they identify constraints whose relaxation, at rates proportional to the multipliers, strictly improves the primal optimal value. Moreover, we show that if the set of geometric multipliers is nonempty, then the minimum-norm vector of this set is informative and defines the optimal rate of cost improvement per unit constraint violation. Our assumptions are very general and, in particular, allow for the presence of a duality gap and the nonexistence of optimal solutions. In particular, for the case where there is a duality gap, we establish enhanced Fritz John conditions involving the dual optimal value and dual optimal solutions.

关键词： convex program Fritz John multiplier geometric multiplier duality sensitivity analysis

来源：评论

学校读者我要写书评

暂无评论

A new neural network for solving nonlinear convex programs with linear constraints

引用

NEUROCOMPUTING 2011年第17期74卷 3079-3083页

作者： Yang, Yongqing Gao, Yun Jiangnan Univ Sch Sci Minist Educ Key Lab Adv Proc Control Light Ind Wuxi 214122 Peoples R China

In this paper, a new neural network was presented for solving nonlinear convex programs with linear constrains. Under the condition that the objective function is convex, the proposed neural network is shown to be stable in the sense of Lyapunov and globally converges to the optimal solution of the original problem. Several numerical examples show the effectiveness of the proposed neural network. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Convergence Stability Neural network convex program

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：