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

IEEE JOURNAL ON SELECTED AREAS IN INFORMATION THEORY 2023年 4卷 54-60页

作者： Srinivasa, Rakshith S. Kim, Seonho Lee, Kiryung Samsung Res Amer Mountain View CA 94043 USA Ohio State Univ Dept Elect & Comp Engn Columbus OH 43220 USA

In many practical applications including remote sensing, multi-task learning, and multi-spectrum imaging, data are described as a set of matrices sharing a common column space. We consider the joint estimation of such matrices from their noisy linear measurements. We study a convex estimator regularized by a pair of matrix norms. The measurement model corresponds to block-wise sensing and the reconstruction is possible only when the total energy is well distributed over blocks. The first norm, which is the maximum-block-Frobenius norm, favors such a solution. This condition is analogous to the notion of low-spikiness in matrix completion or column-wise sensing. The second norm, which is a tensor norm on a pair of suitable Banach spaces, induces low-rankness in the solution together with the first norm. We demonstrate that the joint estimation provides a significant gain over the individual recovery of each matrix when the number of matrices sharing a column space and the ambient dimension of the shared column space are large relative to the number of columns in each matrix. The convex estimator is cast as a semidefinite program and an efficient ADMM algorithm is derived. The empirical behavior of the convex estimator is illustrated using Monte Carlo simulations and recovery performance is compared to existing methods in the literature.

关键词： Sketching low rank matrices tensor norm convex program

来源：评论

学校读者我要写书评

暂无评论

An inexact version of the symmetric proximal ADMM for solving separable convex optimization

引用

NUMERICAL ALGORITHMS 2023年第1期94卷 1-28页

作者： Adona, Vando A. Goncalves, Max L. N. Univ Fed Goias IME Campus 2131 BR-74001970 Goiania GO Brazil

In this paper, we propose and analyze an inexact version of the symmetric proximal alternating direction method of multipliers (ADMM) for solving linearly constrained optimization problems. Basically, the method allows its first subproblem to be solved inexactly in such way that a relative approximate criterion is satisfied. In terms of root the iteration number k, we establish global O(1/ k) pointwise and O(1/k) ergodic convergence rates of the method for a domain of the acceleration parameters, which is consistent with the largest known one in the exact case. Since the symmetric proximal ADMM can be seen as a class of ADMM variants, the new algorithm as well as its convergence rates generalize, in particular, many others in the literature. Numerical experiments illustrating the practical advantages of the method are reported. To the best of our knowledge, this work is the first one to study an inexact version of the symmetric proximal ADMM.

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

来源：评论

学校读者我要写书评

暂无评论

A convex programMING APPROACH FOR DISCRETE-TIME MARKOV DECISION PROCESSES UNDER THE EXPECTED TOTAL REWARD CRITERION

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 2020年第4期58卷 2535-2566页

作者： Dufour, Francois Genadot, Alexandre Univ Bordeaux Inst Math Bordeaux Inst Polytech Bordeaux INRIA Bordeaux Sud OuestTeam CQFD Bordeaux France

In this work, we study discrete-time Markov decision processes (MDPs) under constraints with Borel state and action spaces and where all the performance functions have the same form of the expected total reward (ETR) criterion over the infinite time horizon. One of our objective is to propose a convex programming formulation for this type of MDP. It will be shown that the values of the constrained control problem and the associated convex program coincide. Moreover, if there exists an optimal solution to the convex program then there exists a stationary randomized policy which is optimal for the MDP. It will be also shown that in the framework of constrained control problems, the supremum of the ETRs over the set of randomized policies is equal to the supremum of the ETRs over the set of stationary randomized policies. We consider standard hypotheses such as the so-called continuity-compactness conditions and a Slater-type condition. Our assumptions are quite weak to deal with cases that have not yet been addressed in the literature. Examples are presented to illustrate our results.

关键词： Markov decision process expected total reward criterion occupation measure constraints convex program

来源：评论

学校读者我要写书评

暂无评论

A continuous dynamical splitting method for solving 'strongly plus weakly' convex programming problems

引用

OPTIMIZATION 2020年第6期69卷 1335-1359页

作者： Zhu, Ming Hu, Rong Fang, Ya-Ping Sichuan Univ Dept Math Chengdu Sichuan Peoples R China Chengdu Univ Informat Technol Dept Appl Math Chengdu Sichuan Peoples R China

The Douglas-Rachford splitting method is a classical and powerful method for minimizing the sum of two convex functions. In this paper, we introduce two dynamical systems based on this method for solving the minimum value problem of the sum of a strongly convex function and a weakly convex function. Under mild conditions, it is shown that the proposed dynamical systems are globally convergent to fixed point sets of the corresponding Douglas-Rachford operators, respectively, and are globally asymptotically stable if the corresponding fixed point sets are singleton. Furthermore, the globally exponential convergence of the proposed dynamical systems is established under some regularity conditions. A numerical example is reported to illustrate the effectiveness of the dynamical splitting method.

关键词： convex program dynamic system splitting method global convergence exponential convergence

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A Cone Constrained convex program:Structure and Algorithms

引用

Journal of the Operations Research Society of China 2013年第1期1卷 37-53页

作者： Liqun Qi Yi Xu Ya-Xiang Yuan Xinzhen Zhang Department of Applied Mathematics The Hong Kong Polytechnic UniversityHung HomKowloonHong KongChina State Key Laboratory of Scientific/Engineering Computing Institute of Computational Mathematics and Scientific/Engineering ComputingAMSSChinese Academy of SciencesZhong Guan Cun Donglu 55Beijing100190P.R.China Department of Mathematics School of ScienceTianjin UniversityTianjin300072China

In this paper,we consider the positive semi-definite space tensor cone constrained convex program,its structure and *** study defining functions,defining sequences and polyhedral outer approximations for this positive semidefinite space tensor cone,give an error bound for the polyhedral outer approximation approach,and thus establish convergence of three polyhedral outer approximation algorithms for solving this *** then study some other approaches for solving this structured convex *** include the conic linear programming approach,the nonsmooth convex program approach and the bi-level program *** numerical examples are presented.

关键词： convex program Space tensor Positive semi-definiteness Cone Algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：