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

Generalization Bound and Learning Methods for Data-Driven Projections in linear programming

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Sakaue, Shinsaku Oki, Taihei The University of Tokyo Tokyo Japan

How to solve high-dimensional linear programs (LPs) efficiently is a fundamental question. Recently, there has been a surge of interest in reducing LP sizes using random projections, which can accelerate solving LPs independently of improving LP solvers. This paper explores a new direction of data-driven projections, which use projection matrices learned from data instead of random projection matrices. Given training data of n-dimensional LPs, we learn an n × k projection matrix with n > k. When addressing a future LP instance, we reduce its dimensionality from n to k via the learned projection matrix, solve the resulting LP to obtain a k-dimensional solution, and apply the learned matrix to it to recover an n-dimensional solution. On the theoretical side, a natural question is: how much data is sufficient to ensure the quality of recovered solutions? We address this question based on the framework of data-driven algorithm design, which connects the amount of data sufficient for establishing generalization bounds to the pseudo-dimension of performance metrics. We obtain an Õ(nk2) upper bound on the pseudo-dimension, where Õ compresses logarithmic factors. We also provide an Ω(nk) lower bound, implying our result is tight up to an Õ(k) factor. On the practical side, we explore two simple methods for learning projection matrices: PCA- and gradient-based methods. While the former is relatively efficient, the latter can sometimes achieve better solution quality. Experiments demonstrate that learning projection matrices from data is indeed beneficial: it leads to significantly higher solution quality than the existing random projection while greatly reducing the time for solving LPs. Copyright © 2023, The Authors. All rights reserved.

关键词： linear programming

Data-driven optimal control via linear programming: boundedness guarantees

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Falconi, Lucia Martinelli, Andrea Lygeros, John The Department of Information Engineering University of Padova Via Gradenigo 6/B Padova35131 Italy The Automatic Control Laboratory ETH Zurich Physikstrasse 3 Zurich8092 Switzerland

The linear programming (LP) approach is, together with value iteration and policy iteration, one of the three fundamental methods to solve optimal control problems in a dynamic programming setting. Despite its simple formulation, versatility, and predisposition to be employed in model-free settings, the LP approach has not enjoyed the same popularity as the other methods. The reason is the often poor scalability of the exact LP approach and the difficulty to obtain bounded solutions for a reasonable amount of constraints. We mitigate these issues here, by investigating fundamental geometric features of the LP and developing sufficient conditions to guarantee finite solutions with minimal constraints. In the model-free context, we show that boundedness can be guaranteed by a suitable choice of dataset and objective function. © 2023, CC BY.

关键词： linear programming

Absolute value linear programming

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Hladík, Milan Hartman, David Department of Applied Mathematics Faculty of Mathematics and Physics Charles University Malostranské nám. 25 Prague 111800 Czech Republic Computer Science Institute of Charles University Faculty of Mathematics and Physics Charles University Malostranské nám. 25 Prague 111800 Czech Republic Institute of Computer Science The Czech Academy of Sciences Czech Academy of Sciences Pod Vodárenskou věží 271/2 Prague 818207 Czech Republic

We deal with linear programming problems involving absolute values in their formulations, so that they are no more expressible as standard linear programs. The presence of absolute values causes the problems to be nonconvex and nonsmooth, so hard to solve. In this paper, we study fundamental properties on the topology and the geometric shape of the solution set, and also conditions for convexity, connectedness, boundedness and integrality of the vertices. Further, we address various complexity issues, showing that many basic questions are NP-hard to solve. We show that the feasible set is a (nonconvex) polyhedral set and, more importantly, every nonconvex polyhedral set can be described by means of absolute value constraints. We also provide a necessary and sufficient condition when a KKT point of a nonconvex quadratic programming reformulation solves the original *** Codes 90C26, 90C05, 90C30, 90C10 Copyright © 2023, The Authors. All rights reserved.

关键词： linear programming

Multi-Step Optimal Tracking Control of Unknown Nonzero-Sum Games based on Least Squares and linear programming: An Application to a Fully-Automated, Dual-Hormone Artificial Pancreas

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Tanzanakis, Alexandros Lygeros, John Department of Information Technology and Electrical Engineering ETH Zurich Switzerland

We consider the problem of optimal tracking control of unknown discrete-time nonlinear nonzero-sum games. The related state-of-art literature is mostly focused on Policy Iteration algorithms and multiple neural network approximation, which may lead to practical implementation challenges and high computational burden. To overcome these problems, we propose a novel Q-function-based multi-step Value Iteration algorithm, which provides the potential to accelerate convergence speed and improve the quality of solutions, with an easy-to-realize initialization condition. A critic-only least squares implementation approach is then employed, which alleviates the computational complexity of commonly used multiple neural network-based methods. Afterwards, by introducing the coupled Bellman operator, a novel linear programming approach is derived, based on which Nash equilibria can be approximately computed by solving a set of tractable finite-dimensional optimization problems. We evaluate the tracking control capabilities of the proposed algorithms to the problem of fully-automated dual-hormone (i.e., insulin and glucagon) glucose control in Type 1 Diabetes Mellitus. The U.S. FDA-accepted DMMS.R simulator from the Epsilon Group is used to conduct extensive in-silico clinical studies on virtual patients under a variety of completely unannounced meal and exercise scenarios. Simulation results demonstrate the high reliability and exceptional performance of the proposed multi-step algorithmic framework to critical complex systems. Copyright © 2023, The Authors. All rights reserved.

关键词： linear programming

Quantum speedups for linear programming via interior point methods

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Apers, Simon Gribling, Sander Université Paris Cité CNRS IRIF Paris France Tilburg University Tilburg Netherlands

We describe a quantum algorithm based on an interior point method for solving a linear program with n inequality constraints on d variables. The algorithm explicitly returns a feasible solution that is Ε-close to optimal, and runs in time √n · poly(d, log(n), log(1/Ε)) which is sublinear for tall linear programs (i.e., n d). Our algorithm speeds up the Newton step in the state-of-the-art interior point method of Lee and Sidford [FOCS'14]. This requires us to efficiently approximate the Hessian and gradient of the barrier function, and these are our main contributions. To approximate the Hessian, we describe a quantum algorithm for the spectral approximation of AT A for a tall matrix A ∈ n×d. The algorithm uses leverage score sampling in combination with Grover search, and returns a δ-approximation by making O(√nd/δ) row queries to A. This generalizes an earlier quantum speedup for graph sparsification by Apers and de Wolf [FOCS'20]. To approximate the gradient, we use a recent quantum algorithm for multivariate mean estimation by Cornelissen, Hamoudi and Jerbi [STOC'22]. While a naive implementation introduces a dependence on the condition number of the Hessian, we avoid this by pre-conditioning our random variable using our quantum algorithm for spectral approximation. © 2023, CC BY.

关键词： linear programming

An Infeasible Interior-Point Arc-search Method with Nesterov’s Restarting Strategy for linear programming Problems

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Iida, Einosuke Yamashita, Makoto Department of Mathematical and Computing Science Tokyo Institute of Technology Japan

An arc-search interior-point method is a type of interior-point methods that approximates the central path by an ellipsoidal arc, and it can often reduce the number of iterations. In this work, to further reduce the number of iterations and computation time for solving linear programming problems, we propose two arc-search interior-point methods using Nesterov’s restarting strategy that is well-known method to accelerate the gradient method with a momentum term. The first one generates a sequence of iterations in the neighborhood, and we prove that the convergence of the generated sequence to an optimal solution and the computation complexity is polynomial time. The second one incorporates the concept of the Mehrotra type interior-point method to improve numerical performance. The numerical experiments demonstrate that the second one reduced the number of iterations and computational time. In particular, the average number of iterations was reduced compared to existing interior-point methods due to the momentum *** Codes 90C51(Primary) 65K05, 90C05(Secondary) Copyright © 2023, The Authors. All rights reserved.

关键词： linear programming

Fuzzy Number linear programming Technique for Design of Rectangular Canals

学校读者我要写书评

暂无评论

JOURNAL OF IRRIGATION AND DRAINAGE ENGINEERING 2022年第8期148卷

作者： Rezazadeh Baghal, Siamak Khodashenas, Saeed Reza Ferdowsi Univ Mashhad Dept Water Engn POB 918617-3734 Mashhad Razavi Khorasan Iran Ferdowsi Univ Mashhad Dept Water Engn POB 917966-6549 Mashhad Razavi Khorasan Iran

Despite many deterministic approaches for the optimal design of a canal already proposed, a methodology capable of considering the risk value when there is uncertainty in flow estimation is still lacking. In real engineering problems, we confront linear programming models in which all included uncertain parameters are fuzzy numbers. In the task of canal design, this assumption is because it involves uncertain parameters (load and resistance) estimated by short historical data and limited knowledge about the environment, respectively. This limitation hinders the usage of probabilistic linear programming approaches because the probability of satisfying a constraint should be known with certainty. This paper provides a new method for solving fuzzy number linear programming problems using the concept of fuzzy risk and Yager's fuzzy ranking function. The result is used for proposing a novel optimization formula that can aid in rectangular canal design. The application of our insightful new methodology is presented in a stormwater canal design example. The findings presented in this paper will appeal to decision-makers and practicing engineers.

关键词： Fuzzy number linear programming Rectangular canal design Risk Uncertainty

***: A GPU Implementation of Restarted Primal-Dual Hybrid Gradient for linear programming in Julia

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Lu, Haihao Yang, Jinwen The University of Chicago Booth School of Business United States The University of Chicago Department of Statistics United States

In this paper, we provide an affirmative answer to the long-standing question: Are GPUs useful in solving linear programming? We present ***, a GPU implementation of restarted primal-dual hybrid gradient (PDHG) for solving linear programming (LP). We show that this prototype implementation in Julia has comparable numerical performance on standard LP benchmark sets to Gurobi, a highly optimized implementation of the simplex and interior-point methods. This demonstrates the power of using GPUs in linear programming, which, for the first time, showcases that GPUs and first-order methods can lead to performance comparable to state-of-the-art commercial optimization LP solvers on standard benchmark sets. Copyright © 2023, The Authors. All rights reserved.

关键词： linear programming

Estimating Noise Floor in Sentinel-1 Images With linear programming and Least Squares

学校读者我要写书评

暂无评论

IEEE TRANSACTIONS ON GEOSCIENCE AND REMOTE SENSING 2022年 60卷

作者： Lee, Peter Q. Xu, Linlin Clausi, David A. Univ Waterloo Dept Syst Design Engn Waterloo ON N2L 3G1 Canada Univ Waterloo Dept Geog & Environm Management Waterloo ON N2L 3G1 Canada

Sentinel-1 is a synthetic aperture radar platform that provides free and open-source images of the Earth. A product type of Sentinel-1 is ground range detected (GRD), which records intensity while discarding phase information from the radar backscatter. Especially in cross-polarized GRD images, there are noticeable intensity changes throughout the image that are caused by amplifying the noise floor of the signal, which varies due to the nonuniform radiation pattern of the satellite's antenna. While Sentinel-1 has instrument processing facility (IPF) software to estimate the noise floor, even in the newer versions (3.1 or above) of the IPF software there are still instances where the estimates provided do not fit the actual noise floor in the image, which is particularly noticeable in transitions between adjacent subswaths. In this work, we propose a method that reduces the impact of the varying noise-floor throughout the image. The method models the intensity of the noise floor to be a power function of the radiation pattern power. The method divides the swath into several sections depending on the location of the local minimum and maximum of the radiation pattern power with respect to the range. The parameter estimation is portrayed as a geometric programming problem that is transformed into a linear programming problem by logarithmic transformation. Affine offsets are computed for each subswath by a weighted least squares approach. Vast improvement is found on extra-wide (EW) and interferometric wide (IW) Sentinel-1 modes over cross-polarized images. Code implementation is available at https://***/PeterQLee/sentinel1_denoise_rs.

关键词： Antenna radiation patterns Backscatter Noise measurement Extraterrestrial measurements Azimuth Antenna measurements Synthetic aperture radar Additive noise denoising linear programming noise floor Sentinel-1 synthetic aperture radar (SAR)