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

A computational study of the homogeneous algorithm for large-scale convex optimization

COMPUTATIONAL optimization AND APPLICATIONS 1998年第3期10卷 243-269页

作者： Andersen, ED Ye, YY Odense Univ Dept Management DK-5230 Odense M Denmark Univ Iowa Dept Management Sci Iowa City IA 52242 USA

Recently the authors have proposed a homogeneous and self-dual algorithm for solving the monotone complementarity problem (MCP) [5]. The algorithm is a single phase interior-point type method;nevertheless, it yields either an approximate optimal solution or detects a possible infeasibility of the problem. In this paper we specialize the algorithm to the solution of general smooth convex optimization problems, which also possess nonlinear inequality constraints and free variables. We discuss an implementation of the algorithm for large-scale sparse convex optimization. Moreover, we present computational results for solving quadratically constrained quadratic programming and geometric programming problems, where some of the problems contain more than 100,000 constraints and variables. The results indicate that the proposed algorithm is also practically efficient.

关键词： monotone complementarity problem homogeneous and self-dual model interior-point algorithms large-scale convex optimization

来源：评论

学校读者我要写书评

暂无评论

Nonparametric Finite Mixture Models with Possible Shape Constraints: A Cubic Newton Approach

引用

SIAM JOURNAL ON MATHEMATICS OF DATA SCIENCE 2025年第1期7卷 163-188页

作者： Wang, Haoyue Ibrahim, Shibal Mazumder, Rahul MIT Operat Res Ctr Cambridge MA 02142 USA MIT Dept Elect Engn & Comp Sci Cambridge MA 02142 USA MIT Operat Res Ctr Sloan Sch Management Cambridge MA 02142 USA MIT Ctr Stat Cambridge MA 02142 USA

We explore computational aspects of maximum likelihood estimation of the mixture proportions in a nonparametric finite mixture model---a convex optimization problem with old roots in statistics. Motivated by problems in shape constrained inference, we also consider structured variants of this problem with additional convex polyhedral constraints. We propose a new cubic regularized Newton method for this problem and present novel worst-case and local computational guarantees for our algorithm. We extend earlier work by Nesterov and Polyak to the case of a self-concordant objective with polyhedral constraints, such as the ones considered herein. We propose a Frank--Wolfe method to solve the cubic regularized Newton subproblem and derive efficient solutions for the linear optimization oracles that may be of independent interest. In the particular case of Gaussian mixtures without shape constraints, we derive bounds on how well the finite mixture problem approximates the infinite-dimensional Kiefer-Wolfowitz maximum likelihood estimator. Experiments on synthetic and real datasets suggest that our proposed algorithms exhibit improved runtimes and scalability features over prior benchmarks.

关键词： density estimation with shape constraints finite mixture models Bernstein polynomials self- concordant functions cubic Newton method large-scale convex optimization

来源：评论

学校读者我要写书评

暂无评论

Proximal Splitting Algorithms for convex optimization: A Tour of Recent Advances, with New Twists

引用

SIAM REVIEW 2023年第2期65卷 375-435页

作者： Condat, Laurent Kitahara, Daichi Contreras, Andres Hirabayashi, Akira King Abdullah Univ Sci & Technol KAUST Visual Comp Ctr Thuwal 239556900 Saudi Arabia Osaka Univ Div Elect Elect & Infocommun Engn Suita Japan UC Temuco Fac Engn Dept Math & Phys Sci Temuco La Araucania Chile Ritsumeikan Univ Coll Informat Sci & Engn Kusatsu 5258577 Japan

convex nonsmooth optimization problems, whose solutions live in very high dimensional spaces, have become ubiquitous. To solve them, the class of first-order algorithms known as proximal splitting algorithms is particularly adequate: they consist of simple operations, handling the terms in the objective function separately. In this overview, we demystify a selection of recent proximal splitting algorithms: we present them within a unified framework, which consists in applying splitting methods for monotone inclusions in primal-dual product spaces, with well-chosen metrics. Along the way, we easily derive new variants of the algorithms and revisit existing convergence results, extending the parameter ranges in several cases. In particular, we emphasize that when the smooth term in the objective function is quadratic, e.g., for least-squares problems, convergence is guaranteed with larger values of the relaxation parameter than previously known. Such larger values are usually beneficial for the convergence speed in practice.

关键词： large-scale convex optimization nonsmooth optimization splitting proximal algorithm primal-dual algorithm

来源：评论

学校读者我要写书评

暂无评论

A PRECONDITIONING FRAMEWORK FOR SEQUENCES OF DIAGONALLY MODIFIED LINEAR SYSTEMS ARISING IN optimization

引用

SIAM JOURNAL ON NUMERICAL ANALYSIS 2012年第6期50卷 3280-3302页

作者： Bellavia, Stefania De Simone, Valentina Di Serafino, Daniela Morini, Benedetta Univ Florence Dipartimento Energet S Stecco I-50134 Florence Italy Seconda Univ Napoli Dipartimento Matemat I-81100 Caserta Italy CNR Ist Calcolo & Reti Alte Prestazioni I-80131 Naples Italy

We propose a framework for building preconditioners for sequences of linear systems of the form (A + Delta(k))x(k) = b(k), where A is symmetric positive semidefinite and Delta(k) is diagonal positive semidefinite. Such sequences arise in several optimization methods, e.g., in affine-scaling methods for bound-constrained convex quadratic programming and bound-constrained linear least squares, as well as in trust-region and overestimation methods for convex unconstrained optimization problems and nonlinear least squares. For all the matrices of a sequence, the preconditioners are obtained by updating any preconditioner for A available in the LDLT form. The preconditioners in the framework satisfy the natural requirement of being effective on slowly varying sequences;furthermore, under an additional property they are also able to cluster eigenvalues of the preconditioned matrix when some entries of Delta(k) are sufficiently large. We present two low-cost preconditioners sharing the above-mentioned properties and evaluate them on sequences of linear systems generated by the reflective Newton method applied to bound-constrained convex quadratic programming problems and on sequences arising in solving nonlinear least-squares problems with the regularized Euclidean residual method. The results of the numerical experiments show the effectiveness of these preconditioners.

关键词： sequences of linear systems preconditioning incomplete LDLT factorization large-scale convex optimization

来源：评论

学校读者我要写书评

暂无评论

Certifiably Optimal Outlier-Robust Geometric Perception: Semidefinite Relaxations and Scalable Global optimization

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2023年第3期45卷 2816-2834页

作者： Yang, Heng Carlone, Luca MIT Lab Informat & Decis Syst LIDS Cambridge MA 02139 USA

We propose the first general and scalable framework to design certifiable algorithms for robust geometric perception in the presence of outliers. Our first contribution is to show that estimation using common robust costs, such as truncated least squares (TLS), maximum consensus, Geman-McClure, Tukey's biweight, among others, can be reformulated as polynomial optimization problems (POPs). By focusing on the TLS cost, our second contribution is to exploit sparsity in the POP and propose a sparse semidefinite programming(SDP) relaxation that is much smaller than the standard Lasserre's hierarchy while preserving empirical exactness, i.e., the SDP recovers the optimizer of the nonconvex POP with an optimality certificate. Our third contribution is to solve the SDP relaxations at an unprecedented scale and accuracy by presenting STRIDE, a solver that blends global descent on the convex SDP with fast local search on the nonconvex POP. Our fourth contribution is an evaluation of the proposed framework on six geometric perception problems including single and multiple rotation averaging, point cloud and mesh registration, absolute pose estimation, and category-level object pose and shape estimation. Our experiments demonstrate that (i) our sparse SDP relaxation is empirically exact with up to 60%-90% outliers across applications;(ii) while still being far from real-time, STRIDE is up to 100 times faster than existing SDP solvers on medium-scale problems, and is the only solver that can solve large-scale SDPs with hundreds of thousands of constraints to high accuracy;(iii) STRIDE safeguards existing fast heuristics for robust estimation (e.g., RANSAC or Graduated Non-convexity), i.e., it certifies global optimality if the heuristic estimates are optimal, or detects and allows escaping local optima when the heuristic estimates are suboptimal.

关键词： Estimation optimization Programming Costs Robot sensing systems Pose estimation Standards Certifiable algorithms outlier-robust estimation robust fitting robust estimation polynomial optimization semidefinite programming global optimization moment sums-of-squares relaxation large-scale convex optimization

来源：评论

学校读者我要写书评

暂无评论

Portfolio optimization with entropic value-at-risk

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2019年第1期279卷 225-241页

作者： Ahmadi-Javid, Amir Fallah-Tafti, Malihe Amirkabir Univ Technol Dept Ind Engn & Management Syst Tehran Iran

The entropic value-at-risk (EVaR) is a new coherent risk measure, which is an upper bound for both the value-at-risk (VaR) and conditional value-at-risk (CVaR). One of the important properties of the EVaR is that it is strongly monotone over its domain and strictly monotone over a broad sub-domain including all continuous distributions, whereas well-known monotone risk measures such as the VaR and CVaR lack this property. A key feature of a risk measure, besides its financial properties, is its applicability in large-scale sample-based portfolio optimization. If the negative return of an investment portfolio is a differentiable convex function for any sampling observation, the portfolio optimization with the EVaR results in a differentiable convex program whose number of variables and constraints is independent of the sample size, which is not the case for the VaR and CVaR even if the portfolio rate linearly depends on the decision variables. This enables us to design an efficient algorithm using differentiable convex optimization. Our extensive numerical study indicates the high efficiency of the algorithm in large scales, when compared with the existing convex optimization software packages. The computational efficiency of the EVaR and CVaR approaches are generally similar, but the EVaR approach outperforms the other as the sample size increases. Moreover, the comparison of the portfolios obtained for a real case by the EVaR and CVaR approaches shows that the EVaR-based portfolios can have better best, mean, and worst return rates as well as Sharpe ratios. (C) 2019 Published by Elsevier B.V.

关键词： Risk analysis Portfolio optimization Coherent risk measures Stochastic programming large-scale convex optimization

来源：评论

学校读者我要写书评

暂无评论

GRAPH-STRUCTURED TENSOR optimization FOR NONLINEAR DENSITY CONTROL AND MEAN FIELD GAMES

引用

SIAM JOURNAL ON CONTROL AND optimization 2024年第4期62卷 2176-2202页

作者： Ringh, Axel Haasler, Isabel Chen, Yongxin Karlsson, Johan Chalmers Univ Technol Dept Math Sci Gothenburg Sweden Univ Gothenburg Gothenburg Sweden Ecole Polytech Fed Lausanne Signal Signal Proc Lab LTS 4 Lausanne Switzerland Georgia Inst Technol Sch Aerosp Engn Atlanta GA 30332 USA KTH Royal Inst Technol Dept Math Div Optimizat & Syst Theory Stockholm Sweden

In this work we develop a numerical method for solving a type of convex graph- structured tensor optimization problem. This type of problem, which can be seen as a generalization of multimarginal optimal transport problems with graph-structured costs, appears in many applications. Examples are unbalanced optimal transport and multispecies potential mean field games, where the latter is a class of nonlinear density control problems. The method we develop is based on coordinate ascent in a Lagrangian dual, and under mild assumptions we prove that the algorithm converges globally. Moreover, under a set of stricter assumptions, the algorithm converges R-linearly. To perform the coordinate ascent steps one has to compute projections of the tensor, and doing so by brute force is in general not computationally feasible. Nevertheless, for certain graph structures it is possible to derive efficient methods for computing these projections, and here we specifically consider the graph structure that occurs in multispecies potential mean field games. We also illustrate the methodology on a numerical example from this problem class.

关键词： Tensor optimization large-scale convex optimization optimal transport Sinkhorn algorithm unbalanced optimal transport potential mean field games

来源：评论

学校读者我要写书评

暂无评论

Image decomposition-based sparse extreme pixel-level feature detection model with application to medical images

引用

IISE TRANSACTIONS ON HEALTHCARE SYSTEMS ENGINEERING 2021年第4期11卷 338-354页

作者： Lahoti, Geet Chen, Jialei Yue, Xiaowei Yan, Hao Ranjan, Chitta Qian, Zhen Zhang, Chuck Wang, Ben Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA Georgia Inst Technol Georgia Tech Mfg Inst Atlanta GA 30332 USA Virginia Tech Grad Dept Ind & Syst Engn Blacksburg VA USA Arizona State Univ Sch Comp Informat & Decis Syst Engn Tempe AZ USA ProcessMiner Atlanta GA USA Tencent Amer Med Lab Palo Alto CA USA Georgia Inst Technol Georgia Tech Mfg Inst H Milton Stewart Sch Ind & Syst Engn Atlanta GA USA Georgia Inst Technol Sch Mat Sci & Engn Atlanta GA USA

Pixel-level feature detection from images is an essential but challenging task encountered in domains such as detecting defects in manufacturing systems and detecting tumors in medical imaging. Often, the real image contains multiple feature types. The types with higher pixel intensities are termed as positive (extreme) features and the ones with lower pixel intensities as negative (extreme) features. For example, when planning a medical treatment, it is important to identify, (a) calcification (a pathological feature which can result in a post-surgical complications) as positive features, and (b) soft tissues (organ morphology, knowledge of which can support pre-surgical planning) as negative features, from a preoperative computed tomography image of the human heart. However, this is not an easy task because (a) conventional segmentation techniques require manual intervention and post-processing, and (b) existing automatic approaches do not distinguish positive features from negative. In this work, we propose a novel, automatic image decomposition-based sparse extreme pixel-level feature detection model to decompose an image into mean and extreme features. To estimate model parameters, a high-dimensional least squares regression with regularization and constraints is utilized. An efficient algorithm based on the alternating direction method of multipliers and the proximal gradient method is developed to solve the large-scale optimization problem. The effectiveness of the proposed model is demonstrated using synthetic tests and a real-world case study, where the model exhibits superior performance over existing methods.

关键词： Image segmentation feature detection medical image analysis high-dimensional regression large-scale convex optimization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：