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

Optimality criteria without constraint qualifications for linear semidefinite problems

Journal of Mathematical Sciences 2012年第2期182卷 126-143页

作者： Kostyukova, O.I. Tchemisova, T.V. Institute of Mathematics National Academy of Sciences of Belarus Minsk Belarus Mathematical Department University of Aveiro Aveiro Portugal

We consider two closely related optimization problems: a problem of convex semi-infinite programming with multidimensional index set and a linear problem of semi-definite programming. In the study of these problems we apply the approach suggested in our recent paper [14] and based on the notions of immobile indices and their immobility orders. For the linear semi-definite problem, we define the subspace of immobile indices and formulate the first-order optimality conditions in terms of a basic matrix of this subspace. These conditions are explicit, do not use constraint qualifications, and have the form of a criterion. An algorithm determining a basis of the subspace of immobile indices in a finite number of steps is suggested. The optimality conditions obtained are compared with other known optimality conditions. © 2012 Springer Science+Business Media, Inc.

关键词： semidefinite programming CONVEX programming MODULES (Algebra) ALGORITHMS TOPOLOGICAL spaces MATHEMATICAL formulas PROBLEM solving SET theory

来源：评论

学校读者我要写书评

暂无评论

On the Optimal Synchronization of Oscillator Networks via Sparse Interconnection Graphs

On the Optimal Synchronization of Oscillator Networks via Sp...

引用

American Control Conference (ACC)

作者： Fardad, Makan Lin, Fu Jovanovic, Mihailo R. Syracuse Univ Dept Elect Engn & Comp Sci Syracuse NY 13244 USA Univ Minnesota Dept Elect & Comp Engn Minneapolis MN 55455 USA

ISBN: (纸本)9781457710964;9781457710957

We study the optimal design of a conductance network as a means for synchronizing a given set of oscillators. By considering the conductance that connects two oscillators as the measure of the amount of communication between them, we formulate an optimal control problem that addresses the trade-off between synchronization performance and communication. Additionally, we promote the sparsity of the network by penalizing the number of interconnection links. For identical oscillators, we establish convexity and show that the design problem can be formulated as a semidefinite program. For non-identical oscillators, that can be considered as perturbations around a central (average) oscillator, we show that it is meaningful to design an optimal conductance network by assuming that all oscillators are identical to the central oscillator. Finally, for special classes of oscillator networks we derive explicit formulas for the optimal conductance values.

关键词： Convex relaxation optimization oscillator synchronization reweighted l(1) minimization semidefinite programming sparse communication architecture

来源：评论

学校读者我要写书评

暂无评论

Strong duality and minimal representations for cone optimization

Strong duality and minimal representations for cone optimiza...

引用

Workshop on Non linear Optimization, Variational Inequalities and Equilibrium Problems

作者： Tuncel, Levent Wolkowicz, Henry Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada

The elegant theoretical results for strong duality and strict complementarity for linear programming, LP, lie behind the success of current algorithms. In addition, preprocessing is an essential step for efficiency in both simplex type and interior-point methods. However, the theory and preprocessing techniques can fail for cone programming over nonpolyhedral cones. We take a fresh look at known and new results for duality, optimality, constraint qualifications, CQ, and strict complementarity, for linear cone optimization problems in finite dimensions. One theme is the notion of minimal representation of the cone and the constraints. This provides a framework for preprocessing cone optimization problems in order to avoid both the theoretical and numerical difficulties that arise due to the (near) loss of the strong CQ, strict feasibility. We include results and examples on the surprising theoretical connection between duality gaps in the original primal-dual pair and lack of strict complementarity in their homogeneous counterpart. Our emphasis is on results that deal with semidefinite programming, SDP.

关键词： Cone optimization Duality Preprocessing Constraint qualification Duality gap semidefinite programming Strict complementarity Nice cones Devious cones Facially dual complete cones

来源：评论

学校读者我要写书评

暂无评论

Linear vs. semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds 12

Linear vs. Semidefinite Extended Formulations: Exponential S...

引用

44th ACM Annual Symposium on Theory of Computing (STOC)

作者： Fiorini, Samuel Massar, Serge Pokutta, Sebastian Tiwary, Hans Raj de Wolf, Ronald Univ Libre Bruxelles Brussels Belgium Friedrich Alexander Univ Erlangen Germany CWI Amsterdam Netherlands Univ Amsterdam Amsterdam Netherlands

ISBN: (纸本)9781450312455

We solve a 20-year old problem posed by Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the cut polytope and the stable set polytope. These results were discovered through a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.

关键词： Combinatorial optimization linear programming communication complexity semidefinite programming quantum communication complexity

来源：评论

学校读者我要写书评

暂无评论

Multiple Kernel Learning Clustering with an Application to Malware

Multiple Kernel Learning Clustering with an Application to M...

引用

12th IEEE International Conference on Data Mining (ICDM)

作者： Anderson, Blake Storlie, Curtis Lane, Terran Los Alamos Natl Lab Los Alamos NM 87545 USA Univ New Mexico Albuquerque NM 87131 USA Google Inc Mountain View CA 94041 USA

ISBN: (纸本)9781467346498;9780769549057

With the increasing prevalence of richer, more complex data sources, learning with multiple views is becoming more widespread. Multiple kernel learning (MKL) has been developed to address this problem, but in general, the solutions provided by traditional MKL are restricted to a classification objective function. In this work, we develop a novel multiple kernel learning algorithm that is based on a spectral clustering objective function which is able to find an optimal kernel weight vector for the clustering problem. We go on to show how this optimization problem can be cast as a semidefinite program and efficiently solved using off-the-shelf interior point methods.

关键词： Multiple Kernel Learning Spectral Clustering semidefinite programming Malware

来源：评论

学校读者我要写书评

暂无评论

Stochastic nuclear outages semidefinite relaxations

引用

COMPUTATIONAL MANAGEMENT SCIENCE 2012年第3期9卷 363-379页

作者： Gorge, Agnes Lisser, Abdel Zorgati, Riadh Univ Paris Sud Orsay LRI F-91405 Orsay France OSIRIS EDF R&D F-92141 Clamart France

This paper deals with stochastic scheduling of nuclear power plant outages. Focusing on the main constraints of the problem, we propose a stochastic formulation with a discrete distribution for random variables, that leads to a mixed 0/1 quadratically constrained quadratic program. Then we investigate semidefinite relaxations for solving this hard problem. Numerical results on several instances of the problem show the efficiency of this approach, i.e., the gap between the optimal solution and the continuous relaxation is on average equal to 53.35% whereas the semidefinite relaxation yields an average gap of 2.76 %. A feasible solution is then obtained with a randomized rounding procedure.

关键词： Stochastic optimization Chance constrained programming semidefinite programming Relaxation Randomized rounding Nuclear outages

来源：评论

学校读者我要写书评

暂无评论

Optimal power allocation of pilot symbols for LS channel estimation in OFDMA uplink

Optimal power allocation of pilot symbols for LS channel est...

引用

IEEE International Conference on Circuits and Systems (ICCAS)

作者： Dai, Sheng Chen, Fangjiong Chen, Xiaodong Xiong, Shangkun South China Univ Technol Sch Elect & Informat Engn Guangzhou Guangdong Peoples R China Guangzhou Res Inst China Telecom Dept Mobile Commun Guangzhou Peoples R China

ISBN: (纸本)9781467331197

In the uplink transmission of Orthogonal Frequency Division Multiple Access (OFDMA) systems, the subcarriers are assigned to uplink users by the system scheduler. Since each user only applies a portion of the subcarriers and the users experience different multipath channels, conventional channel estimation approach using uniformly placed pilot tones and uniform power allocation is not applicable. In this paper, we assume the places of the pilot tones have been decided by the scheduler and consider optimal power allocation of the pilot symbols, so as to minimize the mean square error (MSE) of channel estimation. The problem is formulated as a classical semidefinite programming (SDP) problem, and hence it can be solved with polynomial complexity.

关键词： LTE uplink pilot symbols power allocation semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

Establishing Connectivity in Proximity Networks

Establishing Connectivity in Proximity Networks

引用

American Control Conference (ACC)

作者： Dai, Ran Maximoff, Joshua Mesbahi, Mehran Univ Washington Dept Aeronaut & Astronaut Seattle WA 98195 USA

ISBN: (纸本)9781457710964;9781457710957

We examine the problem of designing the optimal paths to establish connectivity in a network of intially scattered dynamic agents, specifically minimizing the squared integral of the total control effort. The network edges are modeled by proximity relationships between endpoint agents, leading to a dynamic, state-dependent network topology. We formulate an optimal control problem with specified initial states, linear dynamics, and a connectivity constraint on the final induced topology. Our approach utilizes the Hamiltonian and resultant Euler-Lagrange equations to restructure the optimal control formulation as a parameter optimization problem based on final agent states. We provide both a heuristic approach and an iterative semidefinite programming relaxation to efficiently approximate a solution of the resulting combinatorial optimization problem. Simulation results are provided (for double integrator agent dynamics) to demonstrate feasibility for both approaches, and the results are compared with those obtained from exhaustive global search and random sampling.

关键词： Network Topology Design Proximity Network Convex Optimization Cooperative Control semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

Optimal networks for quantum metrology: semidefinite programs and product rules

引用

NEW JOURNAL OF PHYSICS 2012年第12期14卷 125008-125008页

作者： Chiribella, Giulio Tsinghua Univ Inst Interdisciplinary Informat Sci Ctr Quantum Informat Beijing 100084 Peoples R China

We investigate the optimal estimation of a quantum process that can possibly consist of multiple time steps. The estimation is implemented by a quantum network that interacts with the process by sending an input and processing the output at each time step. We formulate the search for the optimal network as a semidefinite program and use duality theory to give an alternative expression for the maximum payoff achieved by estimation. Combining this formulation with a technique devised by Mittal and Szegedy we prove a general product rule for the joint estimation of independent processes, stating that the optimal joint estimation can be achieved by estimating each process independently, whenever the figure of merit is of a product form. We illustrate the result in several examples and exhibit counterexamples showing that the optimal joint network may not be the product of the optimal individual networks if the processes are not independent or if the figure of merit is not of the product form. In particular, we show that entanglement can reduce by a factor K the variance in the estimation of the sum of K independent phase shifts.

关键词： QUANTUM efficiency (Physics) ESTIMATION theory semidefinite programming PRODUCT formulas (Operator theory) INPUT-output analysis

来源：评论

学校读者我要写书评

暂无评论

Robust Beamforming for OFDM Modulated Two-Way MIMO Relay Network

Robust Beamforming for OFDM Modulated Two-Way MIMO Relay Net...

引用

作者： Zhou, Jianwei Texas A&M University

This thesis studies a two-way relay network (TWRN), which consists of two single antenna source nodes and a multi-antenna relay node. The source nodes exchange information via the assistance of the relay node in the middle. The relay scheme in this TWRN is amplify-and-forward (AF) based analog network coding (ANC). A robust beamforming matrix optimization algorithm is presented here with the objective to minimize the transmit power at the relay node under given signal to interference and noise ratio (SINR) requirements of source nodes. This problem is first formulated as a non-convex optimization problem, and it is next relaxed to a semi-definite programming (SDP) problem by utilizing the S-procedure and rank-one relaxation. This robust beamforming optimization algorithm is further validated in a MATLAB-based orthogonal frequency-division multiplexing (OFDM) MIMO two-way relay simulation system. To better investigate the performance of this beamforming algorithm in practical systems, synchronization issues such as standard timing offset (STO) and carrier frequency offset (CFO) are considered in simulation. The transmission channel is modeled as a frequency selective fading channel, and the source nodes utilize training symbols to perform minimum mean-square error (MMSE) channel estimation. BER curves under perfect and imperfect synchronization are presented to show the performance of TWRN with ANC. It is shown that the outage probability of robust beamforming algorithm is tightly related to the SINR requirements at the source nodes, and the outage probability increases significantly when the SINR requirements are high.

关键词： Analog network coding orthogonal frequency-division multiplexing robust beamforming semidefinite programming two-way relay network Thesis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：