| 失效链接处理 |
|
凸优化 PDF 下载
本站整理下载：
相关截图：
主要内容：
Chapter 1
Introduction
In this introduction we give an overview of mathematical optimization, focusing on
the special role of convex optimization. The concepts introduced informally here
will be covered in later chapters, with more care and technical detail.
1.1 Mathematical optimization
A mathematical optimization problem, or just optimization problem, has the form
minimize f0(x)
subject to fi(x) ≤ bi
, i = 1, . . . , m.
(1.1)
Here the vector x = (x1, . . . , xn) is the optimization variable of the problem, the
function f0 : Rn → R is the objective function, the functions fi : Rn → R, i = 1, . . . , m, are the (inequality) constraint functions, and the constants b1, . . . , bm
are the limits, or bounds, for the constraints. A vector x⋆
is called optimal, or a
solution of the problem (1.1), if it has the smallest objective value among all vectors
that satisfy the constraints: for any z with f1(z) ≤ b1, . . . , fm(z) ≤ bm, we have
f0(z) ≥ f0(x⋆
).
We generally consider families or classes of optimization problems, characterized
by particular forms of the objective and constraint functions. As an important
example, the optimization problem (1.1) is called a linear program if the objective
and constraint functions f0, . . . , fm are linear, i.e., satisfy
fi(αx + βy) = αfi(x) + βfi(y) (1.2)
for all x, y ∈ Rn
and all α, β ∈ R. If the optimization problem is not linear, it is
called a nonlinear program.
This book is about a class of optimization problems called convex optimization problems. A convex optimization problem is one in which the objective and
constraint functions are convex, which means they satisfy the inequality
fi(αx + βy) ≤ αfi(x) + βfi(y) (1.3)
2 1 Introduction
for all x, y ∈ Rn
and all α, β ∈ R with α + β = 1, α ≥ 0, β ≥ 0. Comparing (1.3)
and (1.2), we see that convexity is more general than linearity: inequality replaces
the more restrictive equality, and the inequality must hold only for certain values
of α and β. Since any linear program is therefore a convex optimization problem,
we can consider convex optimization to be a generalization of linear programming.
1.1.1 Applications
The optimization problem (1.1) is an abstraction of the problem of making the best
possible choice of a vector in Rn
from a set of candidate choices. The variable x
represents the choice made; the constraints fi(x) ≤ bi represent firm requirements
or specifications that limit the possible choices, and the objective value f0(x) represents the cost of choosing x. (We can also think of f0(x) as representing the
value, or utility, of choosing x.) A solution of the optimization problem (1.1) corresponds to a choice that has minimum cost (or maximum utility), among all choices
that meet the firm requirements.
In portfolio optimization, for example, we seek the best way to invest some
capital in a set of n assets. The variable xi represents the investment in the ith
asset, so the vector x ∈ Rn
describes the overall portfolio allocation across the set of
assets. The constraints might represent a limit on the budget (i.e., a limit on the
total amount to be invested), the requirement that investments are nonnegative
(assuming short positions are not allowed), and a minimum acceptable value of
expected return for the whole portfolio. The objective or cost function might be
a measure of the overall risk or variance of the portfolio return. In this case,
the optimization problem (1.1) corresponds to choosing a portfolio allocation that
minimizes risk, among all possible allocations that meet the firm requirements.
Another example is device sizing in electronic design, which is the task of choosing the width and length of each device in an electronic circuit. Here the variables
represent the widths and lengths of the devices. The constraints represent a variety of engineering requirements, such as limits on the device sizes imposed by
the manufacturing process, timing requirements that ensure that the circuit can
operate reliably at a specified speed, and a limit on the total area of the circuit. A
common objective in a device sizing problem is the total power consumed by the
circuit. The optimization problem (1.1) is to find the device sizes that satisfy the
design requirements (on manufacturability, timing, and area) and are most power
efficient.
In data fitting, the task is to find a model, from a family of potential models,
that best fits some observed data and prior information. Here the variables are the
parameters in the model, and the constraints can represent prior information or
required limits on the parameters (such as nonnegativity). The objective function
might be a measure of misfit or prediction error between the observed data and
the values predicted by the model, or a statistical measure of the unlikeliness or
implausibility of the parameter values. The optimization problem (1.1) is to find
the model parameter values that are consistent with the prior information, and give
the smallest misfit or prediction error with the observed data (or, in a statistical
1.1 Mathematical optimization 3
framework, are most likely).
An amazing variety of practical problems involving decision making (or system
design, analysis, and operation) can be cast in the form of a mathematical optimization problem, or some variation such as a multicriterion optimization problem.
Indeed, mathematical optimization has become an important tool in many areas.
It is widely used in engineering, in electronic design automation, automatic control systems, and optimal design problems arising in civil, chemical, mechanical,
and aerospace engineering. Optimization is used for problems arising in network
design and operation, finance, supply chain management, scheduling, and many
other areas. The list of applications is still steadily expanding.
For most of these applications, mathematical optimization is used as an aid to
a human decision maker, system designer, or system operator, who supervises the
process, checks the results, and modifies the problem (or the solution approach)
when necessary. This human decision maker also carries out any actions suggested
by the optimization problem, e.g., buying or selling assets to achieve the optimal
portfolio.
A relatively recent phenomenon opens the possibility of many other applications
for mathematical optimization. With the proliferation of computers embedded in
products, we have seen a rapid growth in embedded optimization. In these embedded applications, optimization is used to automatically make real-time choices,
and even carry out the associated actions, with no (or little) human intervention or
oversight. In some application areas, this blending of traditional automatic control
systems and embedded optimization is well under way; in others, it is just starting. Embedded real-time optimization raises some new challenges: in particular,
it requires solution methods that are extremely reliable, and solve problems in a
predictable amount of time (and memory).
1.1.2 Solving optimization problems
A solution method for a class of optimization problems is an algorithm that computes a solution of the problem (to some given accuracy), given a particular problem
from the class, i.e., an instance of the problem. Since the late 1940s, a large effort
has gone into developing algorithms for solving various classes of optimization problems, analyzing their properties, and developing good software implementations.
The effectiveness of these algorithms, i.e., our ability to solve the optimization problem (1.1), varies considerably, and depends on factors such as the particular forms
of the objective and constraint functions, how many variables and constraints there
are, and special structure, such as sparsity. (A problem is sparse if each constraint
function depends on only a small number of the variables).
Even when the objective and constraint functions are smooth (for example,
polynomials) the general optimization problem (1.1) is surprisingly difficult to solve.
Approaches to the general problem therefore involve some kind of compromise, such
as very long computation time, or the possibility of not finding the solution. Some
of these methods are discussed in §1.4.
There are, however, some important exceptions to the general rule that most
optimization problems are difficult to solve. For a few problem classes we have
4 1 Introduction
effective algorithms that can reliably solve even large problems, with hundreds or
thousands of variables and constraints. Two important and well known examples,
described in §1.2 below (and in detail in chapter 4), are least-squares problems and
linear programs. It is less well known that convex optimization is another exception
to the rule: Like least-squares or linear programming, there are very effective
algorithms that can reliably and efficiently solve even large convex problems.
1.2 Least-squares and linear programming
In this section we describe two very widely known and used special subclasses of
convex optimization: least-squares and linear programming. (A complete technical
treatment of these problems will be given in chapter 4.)
1.2.1 Least-squares problems
A least-squares problem is an optimization problem with no constraints (i.e., m =
0) and an objective which is a sum of squares of terms of the form aTi x bi:
minimize f0(x) = kAx § bk22 = Pki=1(aTi x bi)2. (1.4)
Here A ∈ Rk×n
(with k ≥ n), aTi
are the rows of A, and the vector x ∈ Rn
is the
optimization variable.
Solving least-squares problems
The solution of a least-squares problem (1.4) can be reduced to solving a set of
linear equations,
(AT A)x = AT
b,
so we have the analytical solution x = (AT A) 1AT b. For least-squares problems
we have good algorithms (and software implementations) for solving the problem to
high accuracy, with very high reliability. The least-squares problem can be solved
in a time approximately proportional to n2k, with a known constant. A current
desktop computer can solve a least-squares problem with hundreds of variables, and
thousands of terms, in a few seconds; more powerful computers, of course, can solve
larger problems, or the same size problems, faster. (Moreover, these solution times
will decrease exponentially in the future, according to Moore’s law.) Algorithms
and software for solving least-squares problems are reliable enough for embedded
optimization.
In many cases we can solve even larger least-squares problems, by exploiting
some special structure in the coefficient matrix A. Suppose, for example, that the
matrix A is sparse, which means that it has far fewer than kn nonzero entries. By
exploiting sparsity, we can usually solve the least-squares problem much faster than
order n2k. A current desktop computer can solve a sparse least-squares problem
1.2 Least-squares and linear programming 5
with tens of thousands of variables, and hundreds of thousands of terms, in around
a minute (although this depends on the particular sparsity pattern).
For extremely large problems (say, with millions of variables), or for problems
with exacting real-time computing requirements, solving a least-squares problem
can be a challenge. But in the vast majority of cases, we can say that existing
methods are very effective, and extremely reliable. Indeed, we can say that solving
least-squares problems (that are not on the boundary of what is currently achievable) is a (mature) technology, that can be reliably used by many people who do
not know, and do not need to know, the details.
Using least-squares
The least-squares problem is the basis for regression analysis, optimal control, and
many parameter estimation and data fitting methods. It has a number of statistical
interpretations, e.g., as maximum likelihood estimation of a vector x, given linear
measurements corrupted by Gaussian measurement errors.
Recognizing an optimization problem as a least-squares problem is straightforward; we only need to verify that the objective is a quadratic function (and then
test whether the associated quadratic form is positive semidefinite). While the
basic least-squares problem has a simple fixed form, several standard techniques
are used to increase its flexibility in applications.
In weighted least-squares, the weighted least-squares cost
Xki=1
wi(aTi x bi)2,
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
