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

AN INTERIOR-POINT METHOD FOR MINIMIZING THE MAXIMUM EIGENVALUE OF A LINEAR COMBINATION OF MATRICES

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 1993年第5期31卷 1360-1377页

作者： JARRE, F STANFORD UNIV DEPT OPERAT RESSTANFORDCA 94305

An algorithm for minimizing the largest eigenvalue of an affine combination of symmetric matrices is presented. The nonsmooth problem is transformed into an equivalent smooth constrained problem, which is solved by a predictor-corrector interior-point method taking full advantage of the differentiability and convexity. Some promising numerical results obtained from a preliminary implementation are included.

关键词： convex program EIGENVALUE IMPLEMENTATION

来源：评论

学校读者我要写书评

暂无评论

INPUT OPTIMIZATION .1. OPTIMAL REALIZATIONS OF MATHEMATICAL-MODELS

引用

MATHEMATICAL programMING 1985年第3期31卷 245-268页

作者： ZLOBEC, S 1.McGill University Montreal Canada

Mathematical models are considered as input-output systems. The input is data (technological coefficients, available energy, prices) and the output is the feasible set, the set of optimal solutions, and the optimal value. We study when output is a continuous function of input and identify optimal (minimal) realizations of mathematical models. These are states of the model having the property that every stable perturbation of input results in a locally worse (higher) value of the optimal value function. In input optimization we “optimize” mathematical model rather than a specific mathematical program.

关键词： 90C25 90C31 Key words Mathematical Model Optimal Input Data Perturbation Region of Stability Generalized Inverse of a Matrix Linear program convex program Inequalities

来源：评论

学校读者我要写书评

暂无评论

Globally minimizing the sum of a convex-concave fraction and a convex function based on wave-curve bounds

引用

JOURNAL OF GLOBAL OPTIMIZATION 2020年第2期77卷 301-318页

作者： Xia, Yong Wang, Longfei Wang, Xiaohui Beihang Univ Sch Math Sci Minist Educ LMIB Beijing 100191 Peoples R China Henan Univ Sch Math & Stat Kaifeng 475004 Peoples R China Beihang Univ Sch Astronaut Beijing 100191 Peoples R China

We consider the problem of minimizing the sum of a convex-concave function and a convex function over a convex set (SFC). It can be reformulated as a univariate minimization problem, where the objective function is evaluated by solving convex optimization. The optimal Lagrangian multipliers of the convex subproblems are used to construct sawtooth curve lower bounds, which play a key role in developing the branch-and-bound algorithm for globally solving (SFC). In this paper, we improve the existing sawtooth-curve bounds to new wave-curve bounds, which are used to develop a more efficient branch-and-bound algorithm. Moreover, we can show that the new algorithm finds an epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\epsilon $$\end{document}-approximate optimal solution in at most O mml:mfenced close=")" open="("1 epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O\left( \frac{1}{\epsilon }\right) $$\end{document} iterations. Numerical results demonstrate the efficiency of our algorithm.

关键词： Fractional programming Branch and bound convex program Lower bound

来源：评论

学校读者我要写书评

暂无评论

An Alternating Algorithm for Finding Linear Arrow-Debreu Market Equilibria

引用

THEORY OF COMPUTING SYSTEMS 2022年第1期66卷 38-55页

作者： Chen, Po-An Lu, Chi-Jen Lu, Yu-Sin Natl Yang Ming Chiao Tung Univ Inst Informat Management 1001 Univ Rd300 Hsinchu Taiwan Acad Sinica Inst Informat Sci 128 Acad RdSect 2 Taipei 11529 Taiwan Ind Technol Res Inst 195Sect 4Chung Hsing Rd Chutung Hsinchu County Taiwan

Motivated by the convergence result of mirror-descent algorithms to market equilibria in linear Fisher markets, it is natural for one to consider designing dynamics (specifically, iterative algorithms) for agents to arrive at linear Arrow-Debreu market equilibria. Jain (SIAM J. Comput. 37(1), 303-318,2007) reduced equilibrium computation in linear Arrow-Debreu markets to the equilibrium computation in bijective markets, where everyone is a seller of only one good and a buyer for a bundle of goods. In this paper, we design an algorithm for computing linear bijective market equilibrium, based on solving the rational convex program formulated by Devanur et al. The algorithm repeatedly alternates between a step of gradient-descent-like updates and a distributed step of optimization exploiting the property of such convex program. Convergence can be ensured by a new analysis different from the analysis for linear Fisher market equilibria.

关键词： Arrow-Debreu market equilibria convex program Alternating algorithm

来源：评论

学校读者我要写书评

暂无评论

Blind three dimensional deconvolution via convex optimization

引用

MULTIDIMENSIONAL SYSTEMS AND SIGNAL PROCESSING 2020年第3期31卷 1029-1049页

作者： Shojaei, Shayan Haddadi, Farzan Iran Univ Sci & Technol Sch Elect Engn Tehran Iran

In this paper we discuss recovering two signals from their convolution in 3 dimensions. One of the signals is assumed to lie in a known subspace and the other one is assumed to be sparse. Various applications such as super resolution, radar imaging, and direction of arrival estimation can be described in this framework. We introduce a method to estimate parameters of a signal in a low-dimensional subspace which is convolved with another signal comprised of some impulses in time domain. We transform the problem to a convex optimization in the form of a positive semi-definite program using lifting and the atomic norm. We demonstrate that unknown parameters can be recovered by lowpass observations. Numerical simulations show excellent performance of the proposed method.

关键词： Blind deconvolution Atomic norm convex program Lifting

来源：评论

学校读者我要写书评

暂无评论

An inexact proximal generalized alternating direction method of multipliers

引用

COMPUTATIONAL OPTIMIZATION AND APPLICATIONS 2020年第3期76卷 621-647页

作者： Adona, V. A. Goncalves, M. L. N. Melo, J. G. Univ Fed Goias IME Campus 2Caixa Postal 131 BR-74001970 Goiania Go Brazil

This paper proposes and analyzes an inexact variant of the proximal generalized alternating direction method of multipliers (ADMM) for solving separable linearly constrained convex optimization problems. In this variant, the first subproblem is approximately solved using a relative error condition whereas the second one is assumed to be easy to solve. In many ADMM applications, one of the subproblems has a closed-form solution;for instance, l1 regularized convex composite optimization problems. The proposed method possesses iteration-complexity bounds similar to its exact version. More specifically, it is shown that, for a given tolerance rho>0, an approximate solution of the Lagrangian system associated to the problem under consideration is obtained in at most O(1/rho 2) (resp. O(1/rho) in the ergodic case) iterations. Numerical experiments are presented to illustrate the performance of the proposed scheme.

关键词： Generalized alternating direction method of multipliers convex program Relative error criterion Pointwise iteration-complexity Ergodic iteration-complexity

来源：评论

学校读者我要写书评

暂无评论

LOCATING INTERNET GATEWAYS TO MINIMIZE NONLINEAR CONGESTION COSTS

引用

IEEE TRANSACTIONS ON COMMUNICATIONS 1994年第9期42卷 2740-2750页

作者： LIANG, SC YEE, JR Department of Electrical Engineering-Systems University of Southern California Los Angeles CA USA

In this paper, we investigate the impact of the locations of the gateways on the performance of the internet. We consider the problem of determining i) the routing assignments for the intranet and internet traffic and ii) the number of gateways and their locations to interconnect existing data networks to minimize a linear combination of the average internet and intranet packet delays subject to a cost constraint on the amount to be spent to establish the gateways. This joint routing and topological design problem is important in the design of internets and should be solved before networks are actually interconnected. This problem is formulated as a nonlinear combinatorial optimization problem. When the gateway locations are fixed, the resulting routing problem is not a convex programming problem. This is unexpected since the routing problem in datagram networks is usually formulated as a convex program, We develop an algorithm based upon Lagrangian relaxation to solve this problem. In the computational experiments, the algorithm was shown to be effective in interconnecting i) two WAN's and ii) two grid networks. The experiments also showed that the algorithm finds better feasible solutions than an exchange heuristic.

关键词： .routing problem datagram design problem data networks intranet Lagrangian relaxation existing networks interconnecting Locating Internet routing assignments internet traffic intemet gateway locations convex program

来源：评论

学校读者我要写书评

暂无评论

Iteration-complexity analysis of a generalized alternating direction method of multipliers

引用

JOURNAL OF GLOBAL OPTIMIZATION 2019年第2期73卷 331-348页

作者： Adona, V. A. Goncalves, M. L. N. Melo, J. G. Univ Fed Goias IME Campus 2Caixa Postal 131 BR-74001970 Goiania Go Brazil

This paper analyzes the iteration-complexity of a generalized alternating direction method of multipliers (G-ADMM) for solving separable linearly constrained convex optimization problems. This ADMM variant, first proposed by Bertsekas and Eckstein, introduces a relaxation parameter into the second ADMM subproblem in order to improve its computational performance. It is shown that, for a given tolerance epsilon>0, the G-ADMM with (0,2) provides, in at most O(1/epsilon 2) iterations, an approximate solution of the Lagrangian system associated to the optimization problem under consideration. It is further demonstrated that, in at most O(1/epsilon) iterations, an approximate solution of the Lagrangian system can be obtained by means of an ergodic sequence associated to a sequence generated by the G-ADMM with (0,2]. Our approach consists of interpreting the G-ADMM as an instance of a hybrid proximal extragradient framework with some special properties. Some preliminary numerical experiments are reported in order to confirm that the use of >1 can lead to a better numerical performance than =1 (which corresponds to the standard ADMM).

关键词： Generalized alternating direction method of multipliers Hybrid extragradient method convex program Pointwise iteration-complexity Ergodic iteration-complexity

来源：评论

学校读者我要写书评

暂无评论

A PTAS for a class of binary non-linear programs with low-rank functions

引用

OPERATIONS RESEARCH LETTERS 2021年第5期49卷 633-638页

作者： Trung Thanh Nguyen Elbassioni, Khaled Phenikaa Univ Fac Comp Sci ORLab Hanoi 12116 Vietnam Khalifa Univ Sci & Technol Abu Dhabi U Arab Emirates

Binary non-linear programs belong to the class of combinatorial problems which are computationally hard even to approximate. This paper aims to explore some conditions on the problem structure, under which the resulting problem can be well approximated. Particularly, we consider a setting when both objective function and constraint are low-rank functions, which depend only on a few linear combinations of the input variables, and provide polynomial time approximation schemes. Our result generalizes and unifies some existing results in the literature. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Binary non-linear program convex program Low-rank function Polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Robust Nonnegative Sparse Recovery and the Nullspace Property of 0/1 Measurements

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2018年第2期64卷 689-703页

作者： Kueng, Richard Jung, Peter Free Univ Berlin Dahlem Ctr Complex Quantum Syst D-14195 Berlin Germany Tech Univ Berlin Commun & Informat Theory Grp D-10587 Berlin Germany

We investigate recovery of nonnegative vectors from non-adaptive compressive measurements in the presence of noise of unknown power. In the absence of noise, existing results in the literature identify properties of the measurement that assure uniqueness in the non-negative orthant. By linking such uniqueness results to nullspace properties, we deduce uniform and robust compressed sensing guarantees for nonnegative least squares. No l(1)-regularization is required. As an important proof of principle, we establish that m x n random i.i.d. 0/1-valued Bernoulli matrices obey the required conditions with overwhelming probability provided that m = O(s log(n/s)). We achieve this by establishing the robust nullspace property for random 0/1-matrices-a novel result in its own right. Our analysis is motivated by applications in wireless network activity detection.

关键词： Compressed sensing convex program sparse representation nonnegative binary matrix Bernoulli nullspace property basis pursuit activitity detection

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：