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

An Oblivious ellipsoid algorithm for Solving a System of (In)Feasible Linear Inequalities

MATHEMATICS OF OPERATIONS RESEARCH 2024年第1期49卷 1-651, C2页

作者： Lamperski, Jourdain Freund, Robert M. Todd, Michael J. Univ Pittsburgh Ind Engn Pittsburgh PA 15213 USA MIT Sloan Sch Management Cambridge MA 02139 USA Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14853 USA

The ellipsoid algorithm is a fundamental algorithm for computing a solution to the system of m linear inequalities in n variables (P) : A(T)x = 0. This paper develops an oblivious ellipsoid algorithm (OEA) that either... 详细信息

The ellipsoid algorithm is a fundamental algorithm for computing a solution to the system of m linear inequalities in n variables (P) : A(T)x <= u when its set of solutions has positive volume. However, when (P) is infeasible, the ellipsoid algorithm has no mechanism for proving that (P) is infeasible. This is in contrast to the other two fundamental algorithms for tackling (P), namely, the simplex and interior-point methods, each of which can be easily implemented in a way that either produces a solution of (P) or proves that (P) is infeasible by producing a solution to the alternative system (Alt) : A lambda = 0, u(T)lambda < 0, lambda >= 0. This paper develops an oblivious ellipsoid algorithm (OEA) that either produces a solution of (P) or produces a solution of (Alt). Depending on the dimensions and other condition measures, the computational complexity of the basic OEA may be worse than, the same as, or better than that of the standard ellipsoid algorithm. We also present two modified versions of OEA, whose computational complexity is superior to that of OEA when n MUCH LESS-THAN m. This is achieved in the first modified version by proving infeasibility without producing a solution of (Alt), and in the second version by using more memory.

关键词： ellipsoid algorithm certificates condition measures computational complexity linear inequalities

来源：评论

学校读者我要写书评

暂无评论

A probabilistic ellipsoid algorithm for linear optimization problems with uncertain LMI constraints

引用

AUTOMATICA 2015年 52卷 248-254页

作者： Ataei, Armin Wang, Qian Boston Univ Dept Elect & Comp Engn Boston MA 02215 USA Penn State Univ Dept Mech & Nucl Engn University Pk PA 16802 USA

In this paper, a probabilistic algorithm based on the deep cut ellipsoid method is proposed to solve a linear optimization problem subject to an uncertain linear matrix inequality (LMI). First, a deep cut ellipsoid algorithm is introduced to address probabilistic feasibility of the uncertain LMI. Objective cuts are then defined to search for the optimal solution. The final probabilistic ellipsoid algorithm is a combination of feasibility cuts and objective cuts. It is shown that in a finite number of iterations, the ellipsoid algorithm either returns a suboptimal probabilistically feasible solution with a high confidence level or finds the problem infeasible. Furthermore, the bounds of the suboptimal value are provided with probabilistic guarantees. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Linear matrix inequalities Randomized algorithms Uncertain systems ellipsoid algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimized ellipsoid algorithm for LMI feasibility problems

引用

INTERNATIONAL JOURNAL OF CONTROL AUTOMATION AND SYSTEMS 2014年第4期12卷 915-917页

作者： Im, Ki Hong Baang, Dane Samsung Elect Co Suwon Gyeonggi Do South Korea Korea Atom Energy Res Inst Taejon South Korea

ellipsoid algorithm with deepest-cut method is presented for LMI(Linear Matrix Inequality) feasibility problems. The proposed algorithm removes more than half of the previous step's ellipsoid to obtain faster convergence than the original ellipsoid method. The cutting-direction is also optimized to maximize the volume reduction ratio at each step.

关键词： Deep-cut ellipsoid algorithm LMI optimization

来源：评论

学校读者我要写书评

暂无评论

Achieving target equilibria in network routing games without knowing the latency functions

引用

GAMES AND ECONOMIC BEHAVIOR 2019年第0期118卷 533-569页

作者： Bhaskar, Umang Ligett, Katrina Schulman, Leonard J. Swamy, Chaitanya Tata Inst Fundamental Res Sch Technol & Comp Sci Mumbai Maharashtra India CALTECH Dept Comp & Math Sci Pasadena CA 91125 USA Hebrew Univ Jerusalem Benin Sch Comp Sci & Engn Jerusalem Israel Univ Waterloo Dept Combinator & Optimizat Waterloo ON Canada Univ Calif Berkeley Simons Inst Theory Comp Berkeley CA USA

The analysis of network routing games typically assumes precise, detailed information about the latency functions. Such information may, however, be unavailable or difficult to obtain. Moreover, one is often primarily interested in enforcing a desired target flow as an equilibrium. We ask whether one can achieve target flows as equilibria without knowing the underlying latency functions. We give a crisp positive answer to this question. We show that one can efficiently compute edge tolls that induce a given target multicommodity flow in a nonatomic routing game using a polynomial number of queries to an oracle that takes tolls as input and outputs the resulting equilibrium flow. This result is obtained via a novel application of the ellipsoid method, and extends to various other settings. We obtain improved query-complexity bounds for series-parallel networks, and single-commodity routing games with linear latency functions. Our techniques provide new insights into network routing games. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Routing games Network flows Tolls Stackelberg routing Query complexity ellipsoid algorithm

来源：评论

学校读者我要写书评

暂无评论

Robust Portfolio Selection Based on Optimization Methods

Robust Portfolio Selection Based on Optimization Methods

引用

37th Chinese Control Conference (CCC)

作者： Jin Chu-xin Chen Wan-yi Yu Shu-jing Nankai Univ Coll Comp & Control Engn Tianjin 300350 Peoples R China Qingdao Campus Naval Aeronaut Univ Qingdao 266041 Shandong Peoples R China

ISBN: (纸本)9789881563958

Linear matrix inequalities (LMI) are used to solve robust portfolio problems and many other control problems. ellipsoid algorithm and interior-point method are used to solve EAU. In this paper, we consider a robust portfolio model based on Markowitz theory that minimizes the risk at a certain level of return. We turn the model into the LMI with constraints and use ellipsoid algorithm and interior-point method to solve it. A numerical simulation in stock portfolio is given to prove the validity of the method. Because the rate of return is change over time, in order to make the result robust, we use exponentially weighted moving-average (EWMA) method to compute the covariance matrices. Due to the highly reliable result, the model can provide a reference for investors to make decision on portfolio.

关键词： portfolio selection robustness tracking error LMI ellipsoid algorithm interior-point method EWMA

来源：评论

学校读者我要写书评

暂无评论

Robust Portfolio Selection Based on Optimization Methods

Robust Portfolio Selection Based on Optimization Methods

引用

第37届中国控制会议

作者： JIN Chu-xin CHEN Wan-yi YU Shu-jing College of Computer and Control Engineering Nankai University Qingdao Campus of Naval Aeronautical University

Linear matrix inequalities（LMI） are used to solve robust portfolio problems and many other control problems. ellipsoid algorithm and interior-point method are used to solve LMI. In this paper, we consider a robust portfolio model based on Markowitz theory that minimizes the risk at a certain level of return. We turn the model into the LMI with constraints and use ellipsoid algorithm and interior-point method to solve it. A numerical simulation in stock portfolio is given to prove the validity of the method. Because the rate of return is change over time, in order to make the result robust, we use exponentially weighted moving-average（EWMA） method to compute the covariance matrices. Due to the highly reliable result, the model can provide a reference for investors to make decision on portfolio.

关键词： portfolio selection robustness tracking error LMI ellipsoid algorithm interior-point method EWMA

来源：评论

学校读者我要写书评

暂无评论

Recursive Set-Membership Parameter Estimation Using Fractional Model

引用

CIRCUITS SYSTEMS AND SIGNAL PROCESSING 2015年第12期34卷 3757-3788页

作者： Amairi, M. Univ Gabes Natl Engn Sch Gabes ENIG Res Unit Modeling Anal & Control Syst MACS UR 06 Gabes 6029 Tunisia

This paper deals with time-domain set-membership parameter estimation using fractional model in case of unknown-but-bounded equation error with a priori known noise bounds. In such bounded-error context, the main goal is to characterize the set of all feasible parameters compatible with the model, the measured data and some prior error bounds. The characterization is done using the outer bounding ellipsoid strategy adapted for fractional system parameters estimation. To ensure good convergence of the used algorithms, several procedures for the selection of the more suitable excitation signal and for the equation-error bound computation are proposed and discussed. When the system is commensurate, an iterative algorithm is proposed to deal with commensurate order estimation. The performances of the proposed schemes are illustrated by a numerical example via Monte Carlo simulations and through a real application of the proposed set-membership identification method on an electronic system.

关键词： Bounded error ellipsoid algorithm Fractional calculus Parameter estimation Set-membership

来源：评论

学校读者我要写书评

暂无评论

Linear Precoding Design for Mutual Information Maximization in Generalized Spatial Modulation With Finite Alphabet Inputs

引用

IEEE COMMUNICATIONS LETTERS 2015年第8期19卷 1323-1326页

作者： Jin, Seung-Ri Choi, Won-Chul Park, Jung-Hyun Park, Dong-Jo Korea Adv Inst Sci & Technol Dept Elect Engn Taejon 305701 South Korea Samsung Elect Co Ltd Suwon 443742 South Korea

In this letter, we develop a new precoding scheme that improves the performance of mutual information for generalized spatial modulation (GSM). First, the closed-form expression of the mutual information of the GSM with finite alphabet inputs is derived in order to update the precoder with regard to the mutual information. The joint precoding design problem to maximize the mutual information of the GSM is difficult to solve directly since it is a non-convex coupled problem. In order to solve this problem, we transform the GSM system into a virtual multiple-input multiple-output (MIMO) system, and then an extended ellipsoid algorithm is applied. Each precoder of the GSM can be solved using the common precoder of the virtual MIMO. The numerical results demonstrate that the proposed precoding scheme significantly enhances the performance in terms of the mutual information.

关键词： Generalized spatial modulation (GSM) finite alphabet inputs mutual information precoding ellipsoid algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient Localization Methods for Passivity Enforcement of Linear Dynamical Models

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2014年第9期33卷 1328-1341页

作者： Mahmood, Zohaib Grivet-Talocia, Stefano Chinea, Alessandro Calafiore, Giuseppe C. Daniel, Luca MIT Dept Elect Engn & Comp Sci Cambridge MA 02139 USA Politecn Torino Dept Elect I-10129 Turin Italy IdemWorks Srl I-10129 Turin Italy Politecn Torino Dept Control & Comp Engn I-10129 Turin Italy

This paper describes a novel approach for passivity enforcement of compact dynamical models of electrical interconnects. The proposed approach is based on a parameterization of general state-space scattering models with fixed poles. We formulate the passivity constraints as a unitary boundedness condition on the H-infinity norm of the system transfer function. When this condition is not verified, we use it as an explicit constraint within an iterative perturbation loop of the system state-space matrices. Since the resulting optimization framework is convex but non-smooth, we solve it via localization based algorithms, such as the ellipsoid and the cutting plane methods. The proposed technique solves two critical bottleneck issues of the existing approaches for passivity enforcement of linear macromodels. Compared to quasi-optimal schemes based on singular value or Hamiltonian eigenvalue perturbation, we are able to guarantee convergence to the optimal solution. Compared to convex formulations based on direct Bounded Real Lemma constraints, we are able to reduce both memory and time requirements by orders of magnitude. We demonstrate the effectiveness of our approach on a number of cases for which existing algorithms either fail or exhibit very slow convergence.

关键词： Convex optimization cutting plane method ellipsoid algorithm localization methods passive macromodeling

来源：评论

学校读者我要写书评

暂无评论

Improved ellipsoid algorithm for LMI Feasibility Problems

引用

INTERNATIONAL JOURNAL OF CONTROL AUTOMATION AND SYSTEMS 2009年第6期7卷 1015-1019页

作者： Baang, Dane Samsung Elect Suwon 443742 Gyeonggi Do South Korea

An improved ellipsoid algorithm for solving general LMI feasibility problems is proposed. The proposed algorithm uses a deep-cut approach and introduces an affine transformation-based design to obtain the minimal-volume ellipsoid. It is shown that the proposed method improves the convergence rate of the ellipsoid algorithm dramatically. Faster convergence rate of the proposed algorithm is mathematically proved and then tested by simulation.

关键词： Deep-cut method ellipsoid algorithm linear matrix inequalities linear programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：