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

Warmstarting the homogeneous and self-dual interior point method for linear and conic quadratic problems

MATHEMATICAL programming COMPUTATION 2013年第1期5卷 1-25页

作者： Skajaa, Anders Andersen, Erling D. Ye, Yinyu Tech Univ Denmark Dept Informat & Math Modelling 2800 Kgs Lyngby Denmark MOSEK ApS DK-2100 Copenhagen Denmark Stanford Univ Dept Management Sci & Engn Stanford CA 94305 USA

We present two strategies for warmstarting primal-dual interior point methods for the homogeneous self-dual model when applied to mixed linear and quadratic conic optimization problems. Common to both strategies is their use of only the final (optimal) iterate of the initial problem and their negligible computational cost. This is a major advantage when compared to previously suggested strategies that require a pool of iterates from the solution process of the initial problem. Consequently our strategies are better suited for users who use optimization algorithms as black-box routines which usually only output the final solution. Our two strategies differ in that one assumes knowledge only of the final primal solution while the other assumes the availability of both primal and dual solutions. We analyze the strategies and deduce conditions under which they result in improved theoretical worst-case complexity. We present extensive computational results showing work reductions when warmstarting compared to coldstarting in the range 30-75% depending on the problem class and magnitude of the problem perturbation. The computational experiments thus substantiate that the warmstarting strategies are useful in practice.

关键词： Warmstart Interior point method Homogeneous model conic programming

来源：评论

学校读者我要写书评

暂无评论

On Verified Numerical Computations in Convex programming

引用

JAPAN JOURNAL OF INDUSTRIAL AND APPLIED MATHEMATICS 2009年第2-3期26卷 337-363页

作者： Jansson, Christian Hamburg Univ Technol Inst Reliable Comp D-21071 Hamburg Germany

This survey contains recent developments for computing verified results of convex constrained optimization problems, with emphasis on applications. Especially, we consider the computation of verified error bounds for non-smooth convex conic optimization in the framework of functional analysis, for linear programming, and for semidefinite programming. A discussion of important problem transformations to special types of convex problems and convex relaxations is included. The latter are important for handling and for reliability issues in global robust and combinatorial optimization. Some remarks on numerical experiences, including also large-scale and ill-posed problems, and software for verified computations concludes this survey.

关键词： linear programming semidefinite programming conic programming convex programming combinatorial optimization rounding errors ill-posed problems interval arithmetic branch-bound-and-cut

来源：评论

学校读者我要写书评

暂无评论

COSMO: A conic Operator Splitting Method for Convex conic Problems

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2021年第3期190卷 779-810页

作者： Garstka, Michael Cannon, Mark Goulart, Paul Univ Oxford Parks Rd Oxford OX1 3PJ England

This paper describes the conic operator splitting method (COSMO) solver, an operator splitting algorithm and associated software package for convex optimisation problems with quadratic objective function and conic constraints. At each step, the algorithm alternates between solving a quasi-definite linear system with a constant coefficient matrix and a projection onto convex sets. The low per-iteration computational cost makes the method particularly efficient for large problems, e.g. semidefinite programs that arise in portfolio optimisation, graph theory, and robust control. Moreover, the solver uses chordal decomposition techniques and a new clique merging algorithm to effectively exploit sparsity in large, structured semidefinite programs. Numerical comparisons with other state-of-the-art solvers for a variety of benchmark problems show the effectiveness of our approach. Our Julia implementation is open source, designed to be extended and customised by the user, and is integrated into the Julia optimisation ecosystem.

关键词： conic programming ADMM Chordal decomposition Clique merging

来源：评论

学校读者我要写书评

暂无评论

Limit analysis, rammed earth material and Casagrande test

引用

COMPTES RENDUS MECANIQUE 2018年第2期346卷 98-109页

作者： El-Nabouch, Ranime Pastor, Joseph Quoc-Bao Bui Ple, Olivier Univ Savoie Mt Blanc CNRS LOCIE F-73000 Chambery France Ton Duc Thang Univ Fac Civil Engn Ho Chi Minh City Vietnam

The present paper is concerned with the simulation of the Casagrande test carried out on a rammed earth material for wall-type structures in the framework of Limit Analysis (LA). In a preliminary study, the material is considered as a homogeneous Coulomb material, and existing LA static and kinematic codes are used for the simulation of the test. In each loading case, static and kinematic bounds coincide;the corresponding exact solution is a two-rigid-block mechanism together with a quasi-constant stress vector and a velocity jump also constant along the interface, for the three loading cases. In a second study, to take into account the influence of compressive loadings related to the porosity of the material, an elliptic criterion (denoted Cohesive Cam-Clay, CCC) is defined based on recent homogenization results about the hollow sphere model for porous Coulomb materials. Finally, original finite element formulations of the static and mixed kinematic methods for the CCC material are developed and applied to the Casagrande test. The results are the same than above, except that this time the velocity jump depends on the compressive loading, which is more realistic but not satisfying fully the experimental observations. Therefore, the possible extensions of this work towards non-standard direct methods are analyzed in the conclusion section. (C) 2017 Academie des sciences. Published by Elsevier Masson SAS.

关键词： Limit analysis Lower and upper bound methods Cohesive Cam-Clay material Micromechanics identification Casagrande geotechnical test conic programming

来源：评论

学校读者我要写书评

暂无评论

On the exactness of a simple relaxation for the extended Celis-Dennis-Tapia subproblem

引用

OPTIMIZATION 2023年第12期72卷 3137-3162页

作者： Armijo, Nicolas F. Gomez, Walter Concha, Juan P. Univ Sao Paulo Inst Matemat & Estat Sao Paulo Brazil Univ La Frontera Dept Ingn Matemat Temuco Chile Univ Austral Chile Ctr Docencia Ciencias Basicas Ingn Valdivia Chile

In this work, we study the so-called extended Celis-Dennis-Tapia subproblem that are classical trust region subproblems with an additional quadratic constraint. For this class of problems, we propose a family of relaxations, and study some of its key properties, for instance, convexity issues, exactness of the relaxation, sufficient condition for exactness. The relaxation proposed is obtained adapting to our case a methodology recently developed for trust region problems with an additional conic constraint. We also find sufficient conditions for exactness of the proposed relaxation and discuss the relations between them. Finally, some numerical experiments are presented for testing the proposed relaxation and the sufficient conditions for its tightness.

关键词： Trust regions problems relaxation of non-convex problems conic programming

来源：评论

学校读者我要写书评

暂无评论

conic formulations of graph homomorphisms

引用

JOURNAL OF ALGEBRAIC COMBINATORICS 2016年第4期43卷 877-913页

作者： Roberson, David E. Nanyang Technol Univ Singapore 639798 Singapore Ctr Quantum Technol Singapore Singapore

Given graphs X and Y, we define two conic feasibility programs which we show have a solution over the completely positive cone if and only if there exists a homomorphism from X to Y. By varying the cone, we obtain similar characterizations of quantum/entanglement-assisted homomorphisms and three previously studied relaxations of these relations. Motivated by this, we investigate the properties of these "conic homomorphisms" for general (suitable) cones. We also consider two generalized versions of the Lovasz theta function, and how they interact with these conic homomorphisms. We prove analogs of several results on classical graph homomorphisms as well as some monotonicity theorems. We also show that one of the generalized theta functions is multiplicative on lexicographic and disjunctive graph products.

关键词： Graph theory conic programming Homomorphisms Quantum information

来源：评论

学校读者我要写书评

暂无评论

Dimension reduction and coefficient estimation in multivariate linear regression

引用

JOURNAL OF THE ROYAL STATISTICAL SOCIETY SERIES B-STATISTICAL METHODOLOGY 2007年第3期69卷 329-346页

作者： Yuan, Ming Ekici, Ali Lu, Zhaosong Monteiro, Renato Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA Carnegie Mellon Univ Pittsburgh PA 15213 USA

We introduce a general formulation for dimension reduction and coefficient estimation in the multivariate linear model. We argue that many of the existing methods that are commonly used in practice can be formulated in this framework and have various restrictions. We continue to propose a new method that is more flexible and more generally applicable. The method proposed can be formulated as a novel penalized least squares estimate. The penalty that we employ is the coefficient matrix's Ky Fan norm. Such a penalty encourages the sparsity among singular values and at the same time gives shrinkage coefficient estimates and thus conducts dimension reduction and coefficient estimation simultaneously in the multivariate linear model. We also propose a generalized cross-validation type of criterion for the selection of the tuning parameter in the penalized least squares. Simulations and an application in financial econometrics demonstrate competitive performance of the new method. An extension to the non-parametric factor model is also discussed.

关键词： conic programming dimension reduction group variable selection Ky Fan norm penalized likelihood

来源：评论

学校读者我要写书评

暂无评论

A Polynomial-Time Solution Scheme for Quadratic Stochastic Programs

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2013年第2期158卷 576-589页

作者： Rocha, Paula Kuhn, Daniel Univ London Imperial Coll Sci Technol & Med Dept Comp London SW7 2AZ England

We consider quadratic stochastic programs with random recourse-a class of problems which is perceived to be computationally demanding. Instead of using mainstream scenario tree-based techniques, we reduce computational complexity by restricting the space of recourse decisions to those linear and quadratic in the observations, thereby obtaining an upper bound on the original problem. To estimate the loss of accuracy of this approach, we further derive a lower bound by dualizing the original problem and solving it in linear and quadratic recourse decisions. By employing robust optimization techniques, we show that both bounding problems may be approximated by tractable conic programs.

关键词： Decision rule approximation Robust optimization Quadratic stochastic programming conic programming

来源：评论

学校读者我要写书评

暂无评论

Information Geometry and Interior-Point Algorithms in Semidefinite Programs and Symmetric Cone Programs

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2013年第3期157卷 749-780页

作者： Kakihara, Satoshi Ohara, Atsumi Tsuchiya, Takashi Natl Grad Inst Policy Studies Minato Ku Tokyo 1068677 Japan Univ Fukui Grad Sch Engn Fukui 9108507 Japan

We develop an information geometric approach to conic programming. Information geometry is a differential geometric framework specifically tailored to deal with convexity, naturally arising in information science including statistics, machine learning and signal processing etc. First we introduce an information geometric framework of conic programming. Then we focus on semidefinite and symmetric cone programs. Recently, we demonstrated that the number of iterations of Mizuno-Todd-Ye predictor-corrector primal-dual interior-point methods is (asymptotically) expressed with an integral over the central trajectory called "the curvature integral". The number of iterations of the algorithm is approximated surprisingly well with the integral even for fairly large linear/semidefinite programs with thousands of variables. Here we prove that "the curvature integral" admits a rigorous differential geometric expression based on information geometry. We also obtain an interesting information geometric global theorem on the central trajectory for linear programs. Together with the numerical evidence in the aforementioned work, we claim that "the number of iterations of the interior-point algorithm is expressed as a differential geometric quantity.".

关键词： Interior-point methods Iteration complexities Curvature integral Semidefinite programs Symmetric cone programs conic programming Information geometry

来源：评论

学校读者我要写书评

暂无评论

A second-order cone programming based robust data envelopment analysis model for the new-energy vehicle industry

引用

ANNALS OF OPERATIONS RESEARCH 2020年第1期292卷 321-339页

作者： Lu, Chao Tao, Jie An, Qiuxian Lai, Xiaodong Shanghai Univ Sch Management 99 Shangda Rd Shanghai 200444 Peoples R China Univ Shanghai Sci & Technol Business Sch 516 Jungong Rd Shanghai 200093 Peoples R China North China Elect Power Univ Sch Business 2 Beinong Rd Beijing 100086 Peoples R China South China Normal Univ Sch Econ & Management Guangzhou 510631 Peoples R China

The validity of performance evaluation is determined by, and therefore greatly influenced by, the accuracy of data set. To address such imprecise and negative data problems widely spread in the real world, this paper proposes a second-order cone based robust data envelopment analysis (SOCPR-DEA) model, which is more robust to data variety. Further, this new computational tractable model is applied to analyze 13 new-energy vehicle (NEV) manufacturers from China. The findings support that the SOCPR-DEA model could well mitigate the deficiency caused by data variety, and the evidence from Chinese NEV industry shows that a focus strategy is more likely to enhance a firm's efficiency especially at its emerging stage, and the efficiency is more sensitive with production cost than other factors such as research and development, sales income, earnings per share, and predicted income. In addition, this paper also gives some industrial implications and policy suggestions based on these interesting findings.

关键词： New-energy vehicle industry Efficiency Robust data envelopment analysis model Data variety conic programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：