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

Piecewise SOS-convex moment optimization and applications via exact semi-definite programs

EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION 2024年 12卷

作者： Huang, Q. Y. Jeyakumar, V. Li, G. Univ New South Wales Dept Appl Math Sydney NSW 2052 Australia

This paper presents exact semi-definite Program (SDP) reformulations for infinite-dimensional moment optimization problems involving a new class of piecewise Sum-of-Squares (SOS)-convex functions and projected spectrahedral support sets. These reformulations show that solving a single SDP finds the optimal value and an optimal probability measure of the original moment problem. This is done by establishing an SOS representation for the non-negativity of a piecewise SOS-convex function over a projected spectrahedron. Finally, as an application and a proof-of-concept illustration, the paper presents numerical results for the Newsvendor and revenue maximization problems with higher-order moments by solving their equivalent SDP reformulations. These reformulations promise a flexible and efficient approach to solving these models. The main novelty of the present work in relation to the recent research lies in finding the solution to moment problems, for the first time, with piecewise SOS-convex functions from their numerically tractable exact SDP reformulations.

关键词： Moment optimization Sum-of-squares convex polynomials Piecewise functions Generalized moment problems semi-definite programming

来源：评论

学校读者我要写书评

暂无评论

A distributional Farkas' lemma and moment optimization problems with no-gap dual semi-definite programs

引用

OPTIMIZATION LETTERS 2024年第5期18卷 1095-1110页

作者： Huang, Queenie Yingkun Jeyakumar, Vaithilingam Univ New South Wales Dept Appl Math Sydney 2052 Australia

We present a generalized Farkas' Lemma for an inequality system involving distributions. This lemma establishes an equivalence between an infinite-dimensional system of moment inequalities and a semi-definite system, assuming that the support for the distributions is a spectrahedron. To the best of our knowledge, it is the first extension of Farkas' Lemma to the distributional paradigm. Applying the new Lemma, we then establish no-gap duality results between a class of moment optimization problems and numerically tractable semi-definite programs.

关键词： Generalized Farkas' lemma semi-definite programming Duality Linear matrix inequalities Conic optimization Generalized moment problems

来源：评论

学校读者我要写书评

暂无评论

3D analytical and numerical upper-bound homogenization approaches to the in-plane strength domain of a running-bond masonry wall

引用

INTERNATIONAL JOURNAL FOR NUMERICAL AND ANALYTICAL METHODS IN GEOMECHANICS 2023年第10期47卷 1742-1771页

作者： Donval, Elodie Pham, Duc Toan Hassen, Ghazi de Buhan, Patrick Vigroux, Martin Ctr Sci & Tech Batiment CSTB Marne La Vallee France Univ Gustave Eiffel Ecole Ponts Lab Navier CNRS Marne La Vallee France Ctr Tech Mat Nat Construct Paris France Ctr Sci & Tech Batiment CSTB 84 Ave Jean Jaures F-77447 Champs Sur Marne 2 Marne La Vallee France

The present paper proposes a new homogenization method in order to determine the in-plane strength domain of a single-wythe, running-bond masonry wall. Two approaches, one analytical and one numerical, relying on the limit analysis/yield design framework, are introduced. The main novelty of these two approaches is that they allow to take into account a finite strength for the blocks and the mortar, as well as a non-zero thickness for the joints, without any specific assumption on the state of stress or strain of the structure. For that purpose, 3D virtual failure mechanisms are considered. A comprehensive parametric study is performed, showing that in many cases, the analytical approach is as precise as the numerical one for a much lower computational cost. Finally, the strength domains obtained by the proposed approaches are compared to the results of an extensive experimental study on reduced-scale masonry wallettes available in the literature, showing a good agreement in the compression-compression range.

关键词： homogenisation in-plane strength domain masonry semi-definite programming yield design

来源：评论

学校读者我要写书评

暂无评论

Bounding the Forward Classical Capacity of Bipartite Quantum Channels

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2023年第5期69卷 3034-3061页

作者： Ding, Dawei Khatri, Sumeet Quek, Yihui Shor, Peter W. Wang, Xin Wilde, Mark M. Alibaba Quantum Lab Alibaba Grp Bellevue WA 98004 USA Louisiana State Univ Hearne Inst Theoret Phys Dept Phys & Astron Baton Rouge LA 70803 USA Louisiana State Univ Ctr Computat & Technol Baton Rouge LA 70803 USA Free Univ Berlin Dahlem Ctr Complex Quantum Syst D-14195 Berlin Germany Stanford Univ Informat Syst Lab Stanford CA 94305 USA MIT Ctr Theoret Phys Cambridge MA 02139 USA MIT Dept Math Cambridge MA 02139 USA Inst Quantum Comp Baidu Res Beijing 100193 Peoples R China Stanford Univ Stanford Inst Theoret Phys Stanford CA 94305 USA

We introduce various measures of forward classical communication for bipartite quantum channels. Since a point-to-point channel is a special case of a bipartite channel, the measures reduce to measures of classical communication for point-to-point channels. As it turns out, these reduced measures have been reported in prior work of Wang et al. on bounding the classical capacity of a quantum channel. As applications, we show that the measures are upper bounds on the forward classical capacity of a bipartite channel. The reduced measures are upper bounds on the classical capacity of a point-to-point quantum channel assisted by a classical feedback channel. Some of the various measures can be computed by semi-definite programming.

关键词： Quantum channels Upper bound Task analysis Quantum computing Entropy Receivers Quantum entanglement Feedback-assisted capacity semi-definite programming Renyi relative entropies bipartite quantum channels

来源：评论

学校读者我要写书评

暂无评论

Using general triangle inequalities within quadratic convex reformulation method

引用

OPTIMIZATION METHODS & SOFTWARE 2023年第3期38卷 626-653页

作者： Lambert, Amelie Cnam CEDRIC 292 Rue St Martin FR-75141 Paris 03 France

We consider the exact solution of Problem (P) which consists in mini-mizing a quadratic function subject to quadratic constraints. We start with an explicit description of new general triangle inequalities that are derived from the ranges of the variables of (P). We show that they extend the triangle inequalities, introduced for the binary case, to variables that belong to a generic interval. We also prove that these inequalities cutfeasible solutions of McCormick envelopes, and we relate them to the literature. We then introduce (SDP), a strong semidefinite relaxation of (P), that we call "Shor's plus RLT plus Trian-gle', which includes both the McCormick envelopes and the general triangle inequalities. We further show how to compute a convex relaxation (P*) whose optimal value reaches the value of (SDP). In order to handle these inequalities in the solution of (SDP), we solve it by a heuristic that also serves as a separation algorithm. We then solve (P) to global optimality with a branch-and-bound based on (P*). Finally, we show that our method outperforms the compared solvers.

关键词： Quadratic convex relaxation valid inequalities global optimization semi-definite programming lagrangian duality sub-gradient algorithm quadratic programming

来源：评论

学校读者我要写书评

暂无评论

Random projections of linear and semidefinite problems with linear inequalities

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2023年第1期664卷 24-60页

作者： Poirion, Pierre -Louis Lourenco, Bruno F. Takeda, Akiko RIKEN Ctr Adv Intelligence Project Tokyo Japan Inst Stat Math Dept Stat Inference & Math Tokyo Japan Univ Tokyo Grad Sch Informat Sci & Technol Dept Creat Informat Tokyo Japan

The Johnson-Lindenstrauss Lemma states that there exist linear maps that project a set of points of a vector space into a space of much lower dimension such that the Euclidean distance between these points is approximately preserved. This lemma has been previously used to prove that we can randomly aggregate, using a random matrix whose entries are drawn from a zero-mean sub-Gaussian distribution, the equality constraints of an Linear Program (LP) while preserving approximately the value of the problem. In this paper we extend these results to the inequality case by introducing a random matrix with non-negative entries that allows to randomly aggregate inequality constraints of an LP while preserving approximately the value of the problem. By duality, the approach we propose allows to reduce both the number of constraints and the dimension of the problem while obtaining some theoretical guarantees on the optimal value. We will also show an extension of our results to certain semidefinite programming instances. (c) 2023 Elsevier Inc. All rights reserved.

关键词： Random projection Linear programming semi-definite programming

来源：评论

学校读者我要写书评

暂无评论

Distributed Microphone Array Localization Problem via SDP-SOCP Method

引用

IEEE-ACM TRANSACTIONS ON AUDIO SPEECH AND LANGUAGE PROCESSING 2023年 31卷 3579-3588页

作者： He, Qi Gao, Mingjie Yiu, Ka Fai Cedric Nordholm, Sven Hong Kong Polytech Univ Shenzhen Res Inst Shenzhen 518000 Peoples R China Guangzhou Univ Sch Econ & Stat Guangzhou 511370 Peoples R China Hong Kong Polytech Univ Dept Appl Math Hong Kong Peoples R China Curtin Univ Fac Sci & Engn Sch Elect Engn Comp & Math Sci EECMS Bentley WA 6102 Australia

In multimedia applications, it is common to employ acoustic sensors collectively to enhance signals and to locate sound sources. A direct problem can be formulated to locate sound sources from a set of known sensors. In order to form the acoustic sensor network, it is important to locate the sensor array locations first. However, unlike other networks in which direct time-of-arrival (TOA) measurements might be possible, acoustic distributed network can only obtain time-difference-of-arrival (TDOA) measures indirectly from various sound source anchors. While it is common to employ convex optimization techniques to localize sensor locations in a network with TOA information, it has not been studied properly when it comes to TDOAs. This article considers the microphone array localization problem in a distributed acoustic network with TDOA measurements. We formulate the inverse problem which applied the known source locations to identify the wireless array configuration and estimate the location for each array. The proposed method formulates a mixed semidefinite programming (SDP) and second-order cone programming (SOCP) relaxation model, and then the acoustic geometry is obtained by solving a linear optimal programming. Furthermore, the characteristics of the optimal solution are studied and exact relaxation conditions are given. Experimental results demonstrate that the proposed mixed model can successfully estimate the sensor locations in noisy and reverberant environments for 2-dimensional and 3-dimensional space, which outperforms other relaxation methods.

关键词： Sensors Mathematical models Location awareness Microphone arrays Position measurement Inverse problems Acoustics Convex relaxation distributed sensor array network localization second order cone programming semi-definite programming

来源：评论

学校读者我要写书评

暂无评论

Fast SDP Relaxation of the Optimal Power Flow Using the Line-Wise Model for Representing Meshed Transmission Networks

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2023年第4期38卷 3814-3827页

作者： Aldik, Abdel Rahman Venkatesh, Bala Ryerson Univ Dept Elect Comp & Biomed Engn Toronto ON M5B 1G3 Canada Ryerson Univ Ctr Urban Energy Toronto ON M5B 1G3 Canada

In this paper, we propose a novel semidefinite programming (SDP) relaxation of the Optimal Power Flow (OPF) problem. The proposed formulation utilizes the Line-Wise Model (LWM) to represent meshed transmission networks. This allows the constraints of the proposed formulation to mostly depend on diagonal elements of the voltages' Hermitian W matrix in contrast to the Bus Injection Model (BIM) where constraints heavily utilize its off-diagonal elements. Test cases with bus sizes of 3 to 9241 were considered and chordal sparsity was exploited for them. Obtained results show that the proposed SDP-LW OPF formulation manages to provide solutions of similar or better quality for most test cases that belong to the Typical and Congested (TYP and API) Operating conditions. Furthermore, the proposed SDP-LW OPF formulation manages to reduce the solver's computational time for most of large-scale test cases with reductions up to 80.298%. Results analysis shows that reductions in the solver's computational time upon using the proposed SDP-LW OPF formulation are affected by its ability to significantly reduce constraints with off-diagonal elements of the W matrix without drastically increasing constraints with diagonal elements of the W matrix. Furthermore, the percentage of large sized cliques is found to affect the obtained reductions through its influence over the number of needed linking constraints for relating the elements of the W matrices of decomposed cliques.

关键词： Convex relaxations optimal power flow semi-definite programming

来源：评论

学校读者我要写书评

暂无评论

Custom CMOS Ising Machine Based on Relaxed Burer-Monteiro-Zhang Heuristic

引用

IEEE TRANSACTIONS ON COMPUTERS 2023年第10期72卷 2835-2846页

作者： Shukla, Aditya Erementchouk, Mikhail Mazumder, Pinaki Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48104 USA

Determining the maximum cut of large graphs may require impractically long time, necessitating approximate algorithms and/or specialized computing platforms. A heuristic by Burer, Monteiro and Zhang for max-cut has not only been shown to be advantageous in many respects, but is also applicable to other NP-complete problems. From the perspective of accelerated computing, the heuristic's implementational challenge lies in its gradient-descent dynamics, which could be reduced to several sinusoidal kernel operations applied to each edge of the graph. We had previously established the theoretical underpinnings of a relaxed dynamical heuristic for max-cut similar to the one proposed by Burer et al. but suited for accelerated computing on custom analog CMOS. In this work, we present the first fully custom analog integrated circuit implementing the dynamics of our heuristic on 130-nm CMOS technology. In an era of increasing specificity of computing machines, our algorithm-circuit co-design, originally for max-cut, introduces a versatile approach applicable to a diverse set of practical large-scale NP-complete problems.

关键词： Application-specific integrated circuits burer-monteiro-zhang heuristics CMOS combinatorial optimization goemans-williamson's algorithm maximal cut NP-complete quadratic unconstrained binary optimization (QUBO) semi-definite programming

来源：评论

学校读者我要写书评

暂无评论

A Convex Optimization Approach for Source Localization using LBI Changing Rate of Phase Difference Only 32

A Convex Optimization Approach for Source Localization using...

引用

32nd European Signal Processing Conference (EUSIPCO)

作者： Nuhoglu, Mustafa Atahan Cirpan, Hakan Ali Istanbul Tech Univ Elect & Commun Engn Dept Istanbul Turkiye ASELSAN AS Radar Elect Warfare Syst Div Ankara Turkiye

ISBN: (纸本)9789464593617;9798331519773

We target the source localization problem using only changing rate of phase difference (CRPD) measurements collected by a moving platform with a long baseline interferometer. Source localization using CRPD measurements is a non-convex problem requiring advanced techniques to be resolved. In our paper, we first form a constrained-weighted least squares (CWLS) problem from the maximum-likelihood (ML) function. Then, we transform the CWLS problem into a semi-definite programming. By dropping the rank-one constraint, we achieve semi-definite relaxation, and the problem becomes convex, which interior-point algorithms can optimally solve. In the simulations, we compare the proposed method to the pseudo-linear approaches, ML solver, and Cramer-Rao lower bound (CRLB). We observe that the proposed method attains the CRLB at low noise levels and outperforms the pseudo-linear approaches while performing similarly to the ML solver.

关键词： source localization convex optimization semi-definite programming maximum likelihood phase difference

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：