通信系统中的非凸优化（普林斯顿大学）.pdf_深度学习方法非凸优化

功率控制

半定规划

需积分: 50 151 浏览量更新于2023-03-16 评论 7 收藏 423KB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

Nonconvex Optimization for

Communication Systems

Mung Chiang

Electrical Engineering Department

Princeton University, Princeton, NJ 08544, USA

chiangm@princeton.edu

Summary. Convex optimization has provided both a powerful tool and an intrigu-

ing mentality to the analysis and design of communication systems over the last

few years. A main challenge today is on nonconvex p roblems in these app lication.

This paper presents an overview of some of the important nonconvex optimization

problems in point-to-point and networked communication systems. Three typical ap-

plications are covered: Internet congestion control through nonconcave network util-

ity maximization, wireless network power control through geometric and sigmoidal

programming, and DS L spectrum management through distributed nonconvex op-

timization. A variety of nonconvex optimization techniques are showcased: from

standard dual relaxation to sum-of-squares programming through successive SDP

relaxation, signomial programming through successive GP relaxation, and leveraging

the speciﬁc structures in problems for eﬃcient and distributed heuristics.

Key words: Nonconvex optimization, Geometric programming, Semideﬁ-

nite progr amming, Sum of squares, Duality, Network utility maximization,

TCP/IP, Wireless network, Power control.

1 Introduction

There has been two major “waves” in the history o f optimization theory: the

ﬁrst started with linear programming and simplex method in late 1940s, and

the second with convex optimization and interior point method in late 1980s.

Each has been followed by a transforming period of appreciation-application

cycle: as more people appreciate the use of LP/convex optimization, more

look for their fo rmulations in various applications; then more work on its the-

ory, eﬃcient algorithms and softwares; the more powerful the tools become;

then more p e ople appreciate its usag e . Communication sys tems beneﬁt sig-

niﬁcantly from bo th waves, including multicommodity ﬂow solutions (e.g.,

Bellman Ford algorithm) from LP, and basic network utility maximization

and robust transceiver design from convex optimization.

2 Chiang: Nonconvex Optimization for Communication Systems

Much of the c urrent research frontier is about the potential of the third

wave, on nonconvex optimization. If one word is used to diﬀerentiate be-

tween easy and hard problems, convexity is probably the “watershed”. But if

a longer description length is allowed, much useful conclusions can be drawn

even for nonco nvex optimization. Indeed, convexity is a very disturbing wa-

tershed, since it is not a topological invariant under change of variable (e.g.,

see geometric programming) or higher-dimension embedding (e.g., see sum of

squares method). A variety of approaches have been prop osed, from nonlinear

transformation to turn an apparently nonconvex problem into a convex prob-

lem, to characterization of attraction regions and systematica lly jumping out

of a local optimum, from successive convex approximation to dualization, from

leveraging the speciﬁc structures of the problems (e.g., Diﬀerence of Convex

functions, concave minimization, low rank nonconvexity) to developing more

eﬃcient branch-and-bound procedures.

Researchers in communications and networking have been examining non-

convex optimization using domain-speciﬁc structures in important problems

in the areas of wireless networking, Internet engineering, and communication

theory. Perhaps four typical topics best illustrate the variety of challenging

issues a rising from nonconvex optimization in communication systems:

• Nonconvex objective to be minimized. An example is cong e stion control

for inelastic applications.

• Nonconvex constraint set. An example is power control in low SIR regimes.

• Integer constraints. Two important examples are single path routing and

multiuser detection.

• Constraint sets that are convex but require an exponential number of

inequalities to explicitly describe. An example is optimal scheduling.

This chapter overviews the latest results in recent publications about the

ﬁrst two topics, with a particular focus on showing the connections between

the engineering intuitions about important problems in communication sys-

tems and the state-of-the-art algorithms in nonconvex optimization theory.

2 Internet Congestion Control

2.1 Introduction

Basic network utility maximization

Since the publication of the seminal paper [24] by Kelly, Maulloo, and Tan in

1998, the framework of Network Utility Maximizatio n (NUM) has found many

applications in network rate allocation algorithms and Internet congestion

control protocols (e.g., surveyed in [32, 47]). It has also lead to a systematic

understanding the entire network protocol sta ck in the unifying framewo rk

(e.g., surveyed in [1 1, 31]). By allowing nonlinear concave utility objective

Special Volume 3

functions, NUM substantially expands the scope of the cla ssical LP-based

Network Flow Problems.

Consider a communication network w ith L links, each with a ﬁxed capacity

of c

bps, and S sources (i.e., end users), each transmitting at a source rate

of x

bps. Each source s emits one ﬂow, using a ﬁxed set L(s) of links in its

path, and has a utility function U

). Each link l is shared by a set S(l)

of sour c e s. Networ k Utility Maximization (NUM), in its basic version, is the

following problem of maximizing the total utility of the networ k

over the source rates x, subject to linear ﬂow constraints

s:l∈L(s)

≤ c

for

all links l:

maximize

)

subject to

s∈S(l)

≤ c

, ∀l,

x  0

(1)

where the variables are x ∈ R

There are many nice properties of the basic NUM model due to several

simplifying assumptions of the utility functions and ﬂow constr aints, which

provide the mathematical tractability of problem (1) but also limit its ap-

plicability. In particular, the utility functions {U

} are often assumed to be

increasing and stric tly concave functions.

Assuming that U

) becomes concave for large enough x

is reasonable,

because the law of diminishing marginal utility eventually will be eﬀective.

However, U

may not be concave throughout its domain. In his s eminal paper

published a decade ago, Shenker [45] diﬀerentiated inelastic netwo rk traﬃc

from elastic traﬃc. Utility functions for elastic traﬃc were modeled as strictly

concave functions. While inelastic ﬂows with nonconcave utility functions rep-

resent important applications in practice, they have received little attention

and rate allocation among them have scarcely any mathematical foundation,

except three recent publications [28, 12, 15] (see also earlier work in [54, 29, 30]

related to the approach in [2 8])

In this section, we investigate the extension of the basic NUM to max-

imization of nonconcave utilities , as in the approach of [15]. We provide a

centr alized algorithm for oﬀ-line analysis and establishment of a performance

benchmark for nonconcave utility maximization when the utility function is a

polynomial or signomial. Based on the semialgebraic approach to polynomial

optimization, we employ convex sum-of-squares (SOS) relaxatio ns solved by

a sequence of semideﬁnite programs (SDP), to obtain increasingly tighter up-

per bounds on total achievable utility for polynomial utilities. Surprisingly, in

all our experiments, a very low order and often a minimal order relaxation

yields not just a bound on attainable network utility, but the globally maxi-

mized network utility. When the bound is exact, which can b e proved using

a suﬃcient test, we can also recover a globally optimal rate allocation.

4 Chiang: Nonconvex Optimization for Communication Systems

Canonical distributed algorithm

A reason that the the assumption o f utility function’s concavity is upheld in

almost all papers on NUM is that it leads to three highly desirable mathe-

matical properties of the basic NUM:

• It is a convex optimization problem, therefore the global minimum can be

computed (at least in centralized algorithms) in worst-case polynomial-

time co mplexity [5].

• Strong duality holds for (1) and its Lagrange dual problem. Zero duality

gap enables a dual approach to solve (1).

• Minimization of a separable objective function over linear constraints can

be conducted by distributed algorithms based on the dual approach.

Indeed, the basic NUM (1) is such a “nice” optimization problem that

its theoretical and computational properties have been well studied since the

1960s in the ﬁeld of monotropic programming, e.g., as summarized in [41].

For network rate allocation problems, a dual-base d distributed algorithm has

been widely studied (e.g., in [24, 32]), and is summarized below.

Zero duality gap for (1) states that the solving the Lagrange dual problem

is equivalent to solving the primal pro blem (1). The Lagrange dual problem

is readily derived. We ﬁrst form the Lagrangian of (1):

L(x, λ) =

) +





−

s∈S(l)





where λ

≥ 0 is the Lagrange multiplier (link congestion price) associated with

the linear ﬂow co nstraint on link l. Additivity of total utility and linearity

of ﬂow constraints lead to a Lagrangian dual decomposition into individual

source terms:

L(x, λ) =





) −





l∈L(s)









, λ

) +

where λ

l∈L(s)

. For each source s, L

, λ

) = U

) − λ

only

depends on loc al x

and the link prices λ

on those links used by source s.

The Lagrange dual function g(λ) is deﬁned as the maximized L (x, λ) over

x. This “ net utility” maximization obviously can be conducted distributively

by the each source, as long as the aggregate link price λ

l∈L(s)

available to so urce s, where source s maximizes a str ictly concave function

, λ

) over x

for a given λ

∗

(λ

) = argmax [U

) − λ

] , ∀s. (2)

Special Volume 5

The Lagrange dual problem is

minimize g(λ) = L(x

∗

(λ), λ)

subject to λ  0

(3)

where the optimization variable is λ. Any algorithms that ﬁnd a pair of pr imal-

dual variables (x, λ) that satisfy the KKT optimality condition would solve

(1) and its dual problem (23 ). One possibility is a distributed, iterative sub-

gradient method, which updates the dual variables λ to solve the dual problem

(23):

(t + 1 ) =





(t) − α(t)





−

s∈S(l)

(λ

(t))









, ∀l (4)

where t is the iteration number and α(t) > 0 are step sizes. Certain choices of

step siz e s, such as α(t) = α

/t, α

> 0, guarantee that the sequence of dual

var iables λ(t) will converge to the dual optimal λ

∗

as t → ∞. The primal

var iable x(λ(t)) will also converge to the primal optimal variable x

∗

. For a

primal problem that is a convex optimization, the convergence is towards the

global optimum.

The sequence of the pair of alg orithmic steps (2,4) forms a canonical dis-

tributed algorithm that globally solves network utility optimization problem

(1) and the dual (23) and computes the optimal rates x

∗

and link prices λ

∗

Nonconcave Network Utility Maximization

It is known that for many multimedia applications, user satisfaction may

assume non-concave sha pe as a function of the allocated rate. For example, the

utility for stre aming applications is be tter described by a sigmoidal function:

with a convex par t at low rate and a concave part at high rate, and a single

inﬂexion p oint x

(with U

′′

) = 0) separating the two parts. The concavity

assumption on U

is also related to the elasticity assumption on rate demands

by users. When demands for x

are not perfectly elastic, U

) may not be

concave.

Suppose we remove the critical assumption that {U

} are concave func-

tions, and allow them to be any nonlinear functions. The res ulting NUM

becomes nonconvex optimization and signiﬁcantly harder to be analyzed and

solved, even by centralized computational methods. In particular, a local op-

timum may not be a global optimum and the duality gap can be strictly

positive. The standard distributive algorithms tha t so lve the dual problem

may produce infeasible or suboptimal rate allocation.

Despite such diﬃculties, there have been two very recent publications on

distributed algorithm for nonconcave utility maximization. In [28], a “self-

regulation” heuristic is proposed to avoid the resulting oscillation in rate

allocation and shown to converges to an optimal rate allocation asymptot-

ically when the proportion of nonconcave utility sources vanishes. In [12], a

剩余47页未读，继续阅读

今年什么都要有

粉丝: 35
资源: 1

会员权益专享

通信系统中的非凸优化（普林斯顿大学） .pdf

评论0

会员权益专享

最新资源

通信系统中的非凸优化（普林斯顿大学） .pdf

评论0

mystic, 高约束非凸优化与不确定性.zip

凸优化在信号处理与通信中的应用Convex Optimization in Signal Processing and Communications

普林斯顿数学三剑客 pdf

普林斯顿数学指南 pdf

非凸正则化技术的国内外研究现状

普林斯顿数学三剑客pdf

普林斯顿数学指南 pdf 网盘

普林斯顿数学分析 pdf

普林斯顿数学指南pdf第一卷

普林斯顿概率论读本pdf

普林斯顿微积分读本pdf

普林斯顿数学指南第二卷pdf

普林斯顿数学指南 第二卷 pdf

电子信息工程考研大学排名

112.139.80:3124@HTTP$Leak of HTTP CHECKOPTION$5438$(普林斯顿大学）什么意思？

pdf robust optimization. princeton university press, 2009

高校社团活动信息管理系统的国内外研究现状2000字

普林斯顿数学指南word

the princeton companion to applied mathematics pdf

2024-2030全球及中国PCB接触式探头行业研究及十五五规划分析报告.docx

会员权益专享

最新资源

普林斯顿数学指南第二卷 pdf