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

Improvements to Quantum Interior Point Method for linear optimization

ACM TRANSACTIONS ON QUANTUM COMPUTING 2025年第1期6卷 1-24页

作者： Mohammadisiahroudi, Mohammadhossein Wu, Zeguan Augustino, Brandon Carr, Arielle Terlaky, Tamas Lehigh Univ Ind & Syst Engn Dept Bethlehem PA 18015 USA MIT Sloan Sch Management Cambridge MA USA Lehigh Univ Comp Sci & Engn Dept Bethlehem PA USA

Quantum linear system algorithms (QLSAs) have the potential to speed up Interior Point Methods (IPMs). However, a major bottleneck is the inexactness of quantum tomography to extract classical solutions from quantum states. In addition, QLSAs are sensitive to the condition number, and this sensitivity is exacerbated when the Newton systems arising in IPMs converge to a singular matrix. Recently, an Inexact Feasible Quantum IPM (IF-QIPM) has been developed that addresses the inexactness of QLSAs. However, this method requires a large number of gates and qubits to be implemented. Here, we propose a new IF-QIPM using the normal equation system, which requires fewer gates and qubits. To mitigate the sensitivity to the condition number and other input data-related parameters, we use preconditioning coupled with iterative refinement to obtain better complexity. Finally, we demonstrate the effectiveness of our approach on IBM Qiskit simulators.

关键词： Quantum linear system algorithm quantum interior point method linear optimization iterative refinement preconditioning

来源：评论

学校读者我要写书评

暂无评论

An efficient parametric kernel function of IPMs for linear optimization problems

引用

RESULTS IN CONTROL AND optimization 2025年 18卷

作者： Houas, Amrane Merahi, Fateh Univ Mohamed Khider Fac Exact Sci Nat & Life Sci Dept Math Lab Appl Math Biskra 07000 Algeria Mustapha Ben Boulaid Batna II Univ Fac Math & Comp Sci Dept Stat & Data Sci Batna Algeria

In this manuscript, we examine linear optimization problems formulated in the standard format. A novel kernel function is employed to devise a new interior-point algorithm for these problems. The proposed method reduces the number of iterations required for the Netlib test problems. The outcomes are subsequently derived using the self-dual embedding technique. The application of the kernel function facilitates the determination of search directions and the quantification of the distance between the current iteration and the mu-center of the algorithm. Incorporating specific lemmas tailored to this methodology is essential for establishing the optimal limit on iteration complexity. The methodology delineated in the work of K. Roos provides the framework for our investigation. Finally, numerical instances were examined to elucidate the theoretical findings and demonstrate the efficacy of the proposed innovative approach.

关键词： Interior point algorithm Kernel function linear optimization Large-update Iteration number Iteration complexity

来源：评论

学校读者我要写书评

暂无评论

A First Course in linear optimization

引用

丛书名： Computational Science & Engineering

2025年

作者： Amir Beck Nili Guttmann-Beck

Get 10% off by pre-ordering this book.This item has not yet published. Pre-order now and we will ship and process payment when the book becomes available.To pre-order contact Customer Service:800-447-SIAM (US &amp... 详细信息

ISBN: (数字)9781611978308

ISBN: (纸本)9781611978292

Get 10% off by pre-ordering this book.

This item has not yet published. Pre-order now and we will ship and process payment when the book becomes available.

To pre-order contact Customer Service:

800-447-SIAM (US & Canada)

215-382-9800 (outside US & Canada)

siambooks@***

Do not send credit card details via email.

Prices: List $66.60 / Member $46.62

Publishing May 2025

This self-contained textbook provides the foundations of linear optimization, covering topics in both continuous and discrete linear optimization. It gradually builds the connection between theory, algorithms, and applications so that readers gain a theoretical and algorithmic foundation, familiarity with a variety of applications, and the ability to apply the theory and algorithms to actual problems.

To deepen the reader's understanding, the authors provide

many applications from diverse areas of applied sciences, such as resource allocation, line fitting, graph coloring, the traveling salesman problem, game theory, and network flows;
more than 180 exercises, most of them with partial answers and about 70 with complete solutions; and
a continuous illustration of the theory through examples and exercises.

A First Course in linear optimization is intended to be read cover to cover and requires only a first course in linear algebra as a prerequisite. Its 13 chapters can be used as lecture notes for a first course in linear optimization.

关键词： linear optimization linear programming integer programming networks and flow problems simplex method duality game theory total unimodularity Gomory cuts branch and bound dynamic programming

来源：评论

学校读者我要写书评

暂无评论

An Enhanced Alternating Direction Method of Multipliers-Based Interior Point Method for linear and Conic optimization

引用

INFORMS JOURNAL ON COMPUTING 2025年第2期37卷 197-502, C2页

作者： Deng, Qi Feng, Qing Gao, Wenzhi Ge, Dongdong Jiang, Bo Jiang, Yuntian Liu, Jingsong Liu, Tianhao Xue, Chenyu Ye, Yinyu Zhang, Chuwen Shanghai Jiao Tong Univ Antai Coll Econ & Management Shanghai 200030 Peoples R China Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14853 USA Stanford Univ Inst Computat & Math Engn Palo Alto CA 94305 USA Shanghai Univ Finance & Econ Res Inst Interdisciplinary Sci Sch Informat Management & Engn Shanghai 200433 Peoples R China Shanghai Univ Finance & Econ Key Lab Interdisciplinary Res Computat & Econ Shanghai 200433 Peoples R China Shanghai Univ Finance & Econ Dishui Lake Adv Finance Inst Shanghai 200120 Peoples R China

The alternating-direction-method-of-multipliers-based (ADMM-based) interior point method, or ABIP method, is a hybrid algorithm that effectively combines interior point method (IPM) and first-order methods to achieve a performance boost in large-scale linear optimization. Different from traditional IPM that relies on computationally intensive Newton steps, the ABIP method applies ADMM to approximately solve the barrier penalized problem. However, similar to other first-order methods, this technique remains sensitive to condition number and inverse precision. In this paper, we provide an enhanced ABIP method with multiple improvements. First, we develop an ABIP method to solve the general linear conic optimization and establish the associated iteration complexity. Second, inspired by some existing methods, we develop different implementation strategies for the ABIP method, which substantially improve its performance in linear optimization. Finally, we conduct extensive numerical experiments in both synthetic and real-world data sets to demonstrate the empirical advantage of our developments. In particular, the enhanced ABIP method achieves a 5.8x reduction in the geometric mean of run time on 105 selected linear optimization instances from Netlib, and it exhibits advantages in certain structured problems, such as support vector machine and PageRank. However, the enhanced ABIP method still falls behind commercial solvers in many benchmarks, especially when high accuracy is desired. We posit that it can serve as a complementary tool alongside wellestablished solvers.

关键词： linear optimization conic optimization ADMM interior point method implementation improvement iteration complexity

来源：评论

学校读者我要写书评

暂无评论

linear optimization Models for Maj-3 and Maj-5 Exact Synthesis

引用

IEEE ACCESS 2022年 10卷 130518-130531页

作者： Ferraz, Evandro Catelani Da Silva, Alexandre Cesar Rodrigues Paulo State Univ UNESP Dept Elect Engn Ilha Solteira BR-15385000 Sao Paulo Brazil

Due to the physical restriction of current CMOS technology, the study of majority based nanotechnologies has been progressing steadily. In this paper, we present a new exact synthesis algorithm for majority-of-three and majority-of-five boolean functions. Key in our approach is the formulation of constraints that encodes majority logic problems into linear optimization models. The proposed algorithm is able to generate optimal results for both depth and size minimization, while also minimizing the number of inverters and literals in the output function. With this new approach, we can decrease the total production cost of a circuit in technologies where inverters and literals are expensive to build, without losing optimal results for depth and size minimization. To evaluate our method, a comparison was made with two exact synthesis algorithms that can generate optimal results when considering depth and size as cost criteria, for majority-of-three and majority-of-five boolean functions. Since our method considers two additional cost criteria, the goal is to generate functions that are also optimal in relation to depth and size, but with less inverters and literals. The obtained results have shown that the proposed algorithm was able to further optimize 64% of all 220,376 compared functions, while also achieving equal cost results for the remaining 36%.

关键词： Boolean functions linear optimization logic synthesis majority logic primitive functions

来源：评论

学校读者我要写书评

暂无评论

linear optimization with bipolar fuzzy relational equation constraints using the Aukasiewicz triangular norm

引用

SOFT COMPUTING 2014年第7期18卷 1399-1404页

作者： Li, Pingke Liu, Yuhan Tsinghua Univ Dept Ind Engn Beijing 100084 Peoples R China

This paper discusses the linear optimization problem constrained by a system of bipolar fuzzy relational equations with max- composition, where the involved triangular norm is the Aukasiewicz t-norm. Although it is in general NP-hard, such an optimization problem can be reformulated in polynomial time into a 0-1 integer linear optimization problem and then solved taking advantage of well developed techniques in integer optimization.

关键词： Fuzzy relational equations linear optimization Integer optimization

来源：评论

学校读者我要写书评

暂无评论

linear optimization with bipolar max-min constraints

引用

INFORMATION SCIENCES 2013年 234卷 3-15页

作者： Freson, S. De Baets, B. De Meyer, H. Univ Ghent Dept Appl Math & Comp Sci B-9000 Ghent Belgium Univ Ghent Dept Appl Math Biometr & Proc Control B-9000 Ghent Belgium

We consider a generalization of the linear optimization problem with fuzzy relational (in)equality constraints by allowing for bipolar max-min constraints, i.e. constraints in which not only the independent variables but also their negations occur. A necessary condition to have a non-empty feasible domain is given. The feasible domain, if not empty, is algebraically characterized. A simple procedure is described to generate all maximizers of the linear optimization problem considered and is applied to various illustrative example problems. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Bipolar constraints Equality constraints Fuzzy relational equations Inequality constraints linear optimization Max-min composition

来源：评论

学校读者我要写书评

暂无评论

linear optimization Modeling for Smart Specialization in Primary Sectors of a Developing Country

引用

IEEE TRANSACTIONS ON ENGINEERING MANAGEMENT 2024年 71卷 13890-13904页

作者： Fatemi, Mehdi Ghazinoory, Sepehr Nasri, Shohreh Pakzad, Mahdi Univ Tehran Coll Management Fac Technol & Ind Management Tehran *** Iran Univ Tarbiat Modares Fac Management & Econ Tehran 14115111 Iran Natl Res Inst Sci Policy Dept Sci & Res Policy Tehran *** Iran Natl Res Inst Sci Policy Dept Policy Evaluat & STI Monitoring Tehran *** Iran

Different regional innovation profiles have forced policymakers to engage in innovation policymaking at the subnational level. As a regional approach, smart specialization has recently received attention in various contexts, focusing on stimulating innovation according to each region's existing capabilities and prospects. Although this strategy benefits developing countries with vast cultural and geographical diversity, they have yet to adopt it. After reviewing regional innovation models to identify various variables affecting regional innovation, this article presents a linear optimization model for the division of work in industry, mining, and agriculture among the regions of a country and then implements it in Iran as a case study. Since the results of implementing the model match the findings of previous regional studies, the credibility of the mathematical optimization for smart specialization is verified.

关键词： Innovation policy Iran linear optimization regional innovation S3 smart specialization Innovation policy Iran linear optimization regional innovation S3 smart specialization

来源：评论

学校读者我要写书评

暂无评论

linear optimization problem constrained by fuzzy max-min relation equations

引用

INFORMATION SCIENCES 2013年 234卷 71-79页

作者： Chang, Cheung-Wen Shieh, Bih-Sheue Natl Univ Tainan Dept Appl Math Tainan 700 Taiwan

Fang and Li introduced the optimization model with a linear objective function and constrained by fuzzy max-min relation equations. They converted this problem into a 0-1 integer programming problem and solved it using the jump-tracking branch-and-bound method. Subsequently, Wu et al. improved this method by providing an upper bound on the optimal objective value and presented three rules for simplifying the computation of an optimal solution. This work presents new theoretical results concerning this optimization problem. They include an improved upper bound on the optimal objective value, improved rules for simplifying the problem and a rule for reducing the solution tree. Accordingly, an accelerated approach for finding the optimal objective value is presented, and represents an improvement on earlier approaches. Its potential applications are discussed. (C) 2011 Elsevier Inc. All rights reserved.

关键词： linear optimization Branch-and-bound method Fuzzy relations Fuzzy relation equations Max-min composition

来源：评论

学校读者我要写书评

暂无评论

linear optimization in C(Ω) and portfolio insurance

引用

optimization 2003年第2期52卷 221-239页

作者： Polyrakis, IA Natl Tech Univ Athens Dept Math Athens 15780 Greece

Suppose that X is a subspace of C(Omega) generated by n linearly independent positive elements of C(Omega). In this article we study the problem of minimization of a positive linear functional p of X in X, under a finite number of linear inequalities. This problem does not have always a solution and if a solution exists we cannot determine it. In this article we show that if X is contained in a finite dimensional minimal lattice-subspace Y of C(Omega) (or equivalently, if X is contained in a finite dimensional minimal subspace Y of C(Omega) with a positive basis) and m=dim Y, then the minimization problem has a solution and we determine the solutions by solving an equivalent linear programming problem in R-m. Finally note that this minimization problem has an important application in the portfolio insurance which was the motivation for the preparation of this article.

关键词： linear optimization lattice subspace projection basis portfolio insurance

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：