没有合适的资源?快使用搜索试试~ 我知道了~
LECTURES ON MODERN CONVEX OPTIMIZATION
5星 · 超过95%的资源 需积分: 9 23 下载量 121 浏览量
2011-12-23
04:01:57
上传
评论
收藏 4.99MB PDF 举报
温馨提示
试读
526页
介绍现代凸优化理论,包含LP,SOC,SDP等等的模型建立,求解方法等,是最新学期的教案了
资源推荐
资源详情
资源评论
.
LECTURES
ON
MODERN CONVEX OPTIMIZATION
Aharon Ben-Tal
†
and Arkadi Nemirovski
∗
†
The William Davidson Faculty of Industrial Engineering & Management,
Technion – Israel Institute of Technology, abental@ie.technion.ac.il
http://ie.technion.ac.il/Home/Users/morbt0.html
∗
H. Milton Stewart School of Industrial & Systems Engineering,
Georgia Institute of Technology, nemirovs@isye.gatech.edu
http://www.isye.gatech.edu/faculty-staff/profile.php?entry=an63
Spring Semester 2012
2
Preface
Mathematical Programming deals with optimization programs of the form
minimize f(x)
subject to
g
i
(x) ≤ 0, i = 1, ..., m,
[x ⊂ R
n
]
(P)
and includes the following general areas:
1. Modelling: metho dologies for posing various applied problems as optimization programs;
2. Optimization Theory, focusing on existence, uniqueness and on characterization of optimal
solutions to optimization programs;
3. Optimization Methods: development and analysis of computational algorithms for various
classes of optimization programs;
4. Implementation, testing and application of modelling methodologies and computational
algorithms.
Essentially, Mathematical Programming was born in 1948, when George Dantzig has invented
Linear Programming – the class of optimization programs (P) with linear objective f (·) and
constraints g
i
(·). This breakthrough discovery included
• the methodological idea that a natural desire of a human being to look for the b est possible
decisions can be posed in the form of an optimization program (P) and thus subject to
mathematical and computational treatment;
• the theory of LP programs, primarily the LP duality (this is in part due to the great
mathematician John von Neumann);
• the first computational method for LP – the Simplex method, which over the years turned
out to be an extremely powerful computational tool.
As it often happens with first-rate discoveries (and to some extent is characteristic for such
discoveries), today the above ideas and constructions look quite traditional and simple. Well,
the same is with the wheel.
In 50 plus years since its birth, Mathematical Programming was rapidly progressing along
all outlined avenues, “in width” as well as “in depth”. We have no intention (and time) to
trace the history of the subject decade by decade; instead, let us outline the major achievements
in Optimization during the last 20 years or so, those which, we believe, allow to speak about
modern optimization as opposed to the “classical” one as it existed circa 1980. The reader should
be aware that the summary to follow is highly subjective and reflects the personal preferences
of the authors. Thus, in our opinion the major achievements in Mathematical Programming
during last 15-20 years can be outlined as follows:
♠ Realizing what are the generic optimization programs one can solve well (“efficiently solv-
able” programs) and when such a possibility is, mildly speaking, problematic (“computationally
intractable” programs). At this point, we do not intend to explain what does it mean exactly
that “a generic optimization program is efficiently solvable”; we will arrive at this issue further
in the course. However, we intend to answer the question (right now, not well posed!) “what
are generic optimization programs we can solve well”:
3
(!) As far as numerical processing of programs (P) is concerned, there exists a
“solvable case” – the one of convex optimization programs, where the objective f
and the constraints g
i
are convex functions.
Under minimal additional “computability assumptions” (which are satisfied in basi-
cally all applications), a convex optimization program is “computationally tractable”
– the computational effort required to solve the problem to a given accuracy “grows
moderately” with the dimensions of the problem and the required number of accuracy
digits.
In contrast to this, a general-type non-convex problems are too difficult for numerical
solution – the computational effort required to solve such a problem by the best
known so far numerical methods grows prohibitively fast with the dimensions of
the problem and the number of accuracy digits, and there are serious theoretical
reasons to guess that this is an intrinsic feature of non-convex problems rather than
a drawback of the existing optimization techniques.
Just to give an example, consider a pair of optimization problems. The first is
minimize −
n
i=1
x
i
subject to
x
2
i
− x
i
= 0, i = 1, ..., n;
x
i
x
j
= 0 ∀(i, j) ∈ Γ,
(A)
Γ being a given set of pairs (i, j) of indices i, j. This is a fundamental combinatorial problem of computing the
stability number of a graph; the corresponding “covering story” is as follows:
Assume that we are given n letters which can be sent through a telecommunication channel, say,
n = 256 usual bytes. When passing trough the channel, an input letter can be corrupted by errors;
as a result, two distinct input letters can produce the same output and thus not necessarily can be
distinguished at the receiving end. Let Γ be the set of “dangerous pairs of letters” – pairs (i, j) of
distinct letters i, j which can be converted by the channel into the same output. If we are interested
in error-free transmission, we should restrict the set S of letters we actually use to be independent
– such that no pair (i, j) with i, j ∈ S belongs to Γ. And in order to utilize best of all the capacity
of the channel, we are interested to use a maximal – with maximum possible number of letters –
indep endent sub-alphabet. It turns out that the minus optimal value in (A) is exactly the cardinality
of such a maximal independent sub-alphabet.
Our second problem is
minimize −2
k
i=1
m
j=1
c
ij
x
ij
+ x
00
subject to
λ
min
x
1
m
j=1
b
pj
x
1j
.
.
.
···
x
k
m
j=1
b
pj
x
kj
m
j=1
b
pj
x
1j
···
m
j=1
b
pj
x
kj
x
00
≥ 0,
p = 1, ..., N,
k
i=1
x
i
= 1,
(B)
where λ
min
(A) denotes the minimum eigenvalue of a symmetric matrix A. This problem is responsible for the
design of a truss (a mechanical construction comprised of linked with each other thin elastic bars, like an electric
mast, a bridge or the Eiffel Tower) capable to withstand best of all to k given loads.
When looking at the analytical forms of (A) and (B), it seems that the first problem is easier than the second:
the constraints in (A) are simple explicit quadratic equations, while the constraints in (B) involve much more
complicated functions of the design variables – the eigenvalues of certain matrices depending on the design vector.
The truth, however, is that the first problem is, in a sense, “as difficult as an optimization problem can be”, and
4
the worst-case computational effort to solve this problem within absolute inaccuracy 0.5 by all known optimization
metho ds is about 2
n
op erations; for n = 256 (just 256 design variables corresponding to the “alphabet of bytes”),
the quantity 2
n
≈ 10
77
, for all practical purposes, is the same as +∞. In contrast to this, the second problem is
quite “computationally tractable”. E.g., for k = 6 (6 loads of interest) and m = 100 (100 degrees of freedom of
the construction) the problem has about 600 variables (twice the one of the “byte” version of (A)); however, it
can be reliably solved within 6 accuracy digits in a couple of minutes. The dramatic difference in computational
effort required to solve (A) and (B) finally comes from the fact that (A) is a non-convex optimization problem,
while (B) is convex.
Note that realizing what is easy and what is difficult in Optimization is, aside of theoretical
importance, extremely important methodologically. Indeed, mathematical models of real world
situations in any case are incomplete and therefore are flexible to some extent. When you know in
advance what you can process efficiently, you p erhaps can use this flexibility to build a tractable
(in our context – a convex) model. The “traditional” Optimization did not pay much attention
to complexity and focused on easy-to-analyze purely asymptotical “rate of convergence” results.
From this viewpoint, the most desirable property of f and g
i
is smoothness (plus, perhaps,
certain “nondegeneracy” at the optimal solution), and not their convexity; choosing between
the above problems (A) and (B), a “traditional” optimizer would, perhaps, prefer the first of
them. We suspect that a non-negligible part of “applied failures” of Mathematical Programming
came from the traditional (we would say, heavily misleading) “order of preferences” in model-
building. Surprisingly, some advanced users (primarily in Control) have realized the crucial role
of convexity much earlier than some members of the Optimization community. Here is a real
story. About 7 years ago, we were working on certain Convex Optimization method, and one of
us sent an e-mail to people maintaining CUTE (a benchmark of test problems for constrained
continuous optimization) requesting for the list of convex programs from their collection. The
answer was: “We do not care which of our problems are convex, and this be a lesson for those
developing Convex Optimization techniques.” In their opinion, the question is stupid; in our
opinion, they are obsolete. Who is right, this we do not know...
♠ Discovery of interior-point polynomial time methods for “well-structured” generic convex
programs and throughout investigation of these programs.
By itself, the “efficient solvability” of generic convex programs is a theoretical rather than
a practical phenomenon. Indeed, assume that all we know about (P) is that the program is
convex, its objective is called f , the constraints are called g
j
and that we can compute f and g
i
,
along with their derivatives, at any given point at the cost of M arithmetic operations. In this
case the computational effort for finding an ϵ-solution turns out to be at least O(1)nM ln(
1
ϵ
).
Note that this is a lower complexity bound, and the best known so far upper bound is much
worse: O(1)n(n
3
+ M) ln(
1
ϵ
). Although the bounds grow “moderately” – polynomially – with
the design dimension n of the program and the required number ln(
1
ϵ
) of accuracy digits, from
the practical viewpoint the upper bound becomes prohibitively large already for n like 1000.
This is in striking contrast with Linear Programming, where one can solve routinely problems
with tens and hundreds of thousands of variables and constraints. The reasons for this huge
difference come from the fact that
When solving an LP program, our a priory knowledge is far beyond the fact that the
objective is called f , the constraints are called g
i
, that they are convex and we can
compute their values at derivatives at any given point. In LP, we know in advance
what is the analytical structure of f and g
i
, and we heavily exploit this knowledge
when processing the problem. In fact, all successful LP methods never never compute
the values and the derivatives of f and g
i
– they do something completely different.
5
One of the most important recent developments in Optimization is realizing the simple fact
that a jump from linear f and g
i
’s to “completely structureless” convex f and g
i
’s is too long: in-
between these two extremes, there are many interesting and important generic convex programs.
These “in-between” programs, although non-linear, still possess nice analytical structure, and
one can use this structure to develop dedicated optimization methods, the methods which turn
out to be incomparably more efficient than those exploiting solely the convexity of the program.
The aforementioned “dedicated methods” are Interior Point polynomial time algorithms,
and the most important “well-structured” generic convex optimization programs are those of
Linear, Conic Quadratic and Semidefinite Programming; the last two entities merely did not
exist as established research subjects just 15 years ago. In our opinion, the discovery of Interior
Point methods and of non-linear “well-structured” generic convex programs, along with the
subsequent progress in these novel research areas, is one of the most impressive achievements in
Mathematical Programming.
♠ We have outlined the most revolutionary, in our appreciation, changes in the theoretical
core of Mathematical Programming in the last 15-20 years. During this period, we have witnessed
perhaps less dramatic, but still quite important progress in the methodological and application-
related areas as well. The major novelty here is certain shift from the traditional for Operations
Research applications in Industrial Engineering (production planning, etc.) to applications in
“genuine” Engineering. We believe it is completely fair to say that the theory and methods
of Convex Optimization, especially those of Semidefinite Programming, have b ecome a kind
of new paradigm in Control and are becoming more and more frequently used in Mechanical
Engineering, Design of Structures, Medical Imaging, etc.
The aim of the course is to outline some of the novel research areas which have arisen in
Optimization during the past decade or so. We intend to focus solely on Convex Programming,
specifically, on
• Conic Programming, with emphasis on the most important particular cases – those of
Linear, Conic Quadratic and Semidefinite Programming (LP, CQP and SDP, respectively).
Here the focus will be on
– basic Duality Theory for conic programs;
– investigation of “expressive abilities” of CQP and SDP;
– overview of the theory of Interior Point polynomial time methods for LP, CQP and
SDP.
• “Efficient (polynomial time) solvability” of generic convex programs.
• “Low cost” optimization methods for extremely large-scale optimization programs.
Acknowledgements. The first four lectures of the five comprising the core of the course are
based upon the book
Ben-Tal, A., Nemirovski, A., Lectures on Modern Convex Optimization: Analysis, Algo-
rithms, Engineering Applications, MPS-SIAM Series on Optimization, SIAM, Philadelphia,
2001.
We are greatly indebted to our colleagues, primarily to Yuri Nesterov, Stephen Boyd, Claude
Lemarechal and Kees Roos, who over the years have influenced significantly our understanding
剩余525页未读,继续阅读
资源评论
- simoney2012-12-292012年9月的书,内容很新
bessxq
- 粉丝: 0
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功