理解和应用：凸优化及其数值解法

5星 · 超过95%的资源需积分: 10 66 浏览量更新于2024-07-20 收藏 5.63MB PDF 举报

"《凸优化》是一本由Stephen Boyd和Lieven Vandenberghe合著的专业书籍，详尽地介绍了凸优化这一主题，并演示了如何高效数值求解这类问题。本书首先介绍了凸集和凸函数的基本概念，然后阐述了各种类型的凸优化问题。接下来，讨论了对偶性和近似技术，以及统计估计方法。书中还探讨了无约束和有约束的最小化问题，以及内点法。重点在于识别凸优化问题并选择最合适的解决策略。书中有大量实例和作业练习，适合工程、计算机科学、数学、统计学、金融和经济学等领域的学生、研究人员和实践者阅读。" 凸优化是优化理论中的一个重要分支，它涉及到在满足一系列条件的情况下找到最佳解决方案的问题。凸优化的独特之处在于，其目标函数和约束条件都是凸的，这使得问题具有更良好的数学性质，例如局部最优解也是全局最优解，从而简化了解的搜索过程。本书首先从基础开始，详细讲解凸集的性质，如闭凸集、开凸集和半无限凸集等，以及凸函数的定义和性质，如单调性、次微分和凸组合。这些基本概念为后续的理论构建提供了坚实的基础。接着，作者讨论了不同类型的凸优化问题，包括线性规划、二次规划和锥优化等。这些问题在许多实际应用中有着广泛的应用，如网络流问题、信号处理和图像恢复等。通过这些例子，读者可以理解如何将实际问题转换为凸优化形式。书中进一步深入到对偶理论，这是凸优化的一个重要工具，它允许我们从不同角度看待问题，有时甚至可以简化原问题的求解。对偶问题的构造和强对偶性原理在此部分得到了充分的阐述。此外，书中还涵盖了近似技术，这对于处理大规模或非凸问题尤其有用。这些技术包括截断方法、随机化算法和光滑化技术，它们可以帮助我们在实际计算中逼近最优解。统计估计技术部分介绍了如何利用凸优化方法进行参数估计和模型选择，这对于数据科学和机器学习领域非常关键。这些方法可以用于最小二乘估计、最大似然估计以及正则化问题。在几何问题章节，作者探讨了凸体的几何特性，如维数理论、分离定理和极化不等式，这些都与凸优化的理论紧密相关。在无约束和有约束的最小化问题部分，作者详细介绍了梯度下降法、牛顿法以及内点法等求解策略。特别是内点法，这是一种现代优化算法，对于求解大型线性规划和锥优化问题特别有效。最后，书中包含了大量的习题和案例研究，旨在帮助读者巩固理论知识并将其应用于实践中。通过解决这些实际问题，读者可以掌握如何在工程、科研或商业环境中应用凸优化方法。《凸优化》是一本全面而深入的教科书，它不仅提供了丰富的理论知识，还提供了实用的求解策略，对于希望深入理解和应用凸优化的读者来说，是一份宝贵的资源。

2 1 Introduction

for all x, y ∈ R

and all α, β ∈ R with α + β = 1, α ≥ 0, β ≥ 0. Comparing (1.3)

and (1.2), we see that convexity is more general than linearity: inequality re pl aces

the more res tr i cti ve 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 R

from a set of candidate choices. The variable x

represents the choice made; the constraints f

(x) ≤ b

represent ﬁrm requir ements

or speciﬁcations that limit the possible choices, and the objective value f

(x) rep-

resents the cost of choosing x. (We can also think of −f

(x) as representing the

value, or utility, of choosing x.) A solution of the optimization problem (1.1) corre-

sponds to a choice that has minimum cost (or maximum utility), among all choices

that meet the ﬁrm requirements.

In portfolio optimization, for example, we seek the best way to invest some

capital in a set of n assets. The variable x

represents the investment in the ith

asset, so the vector x ∈ R

describes the overall portfolio allocati on 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), th e 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 retu r n. In this case,

the optimization problem (1.1) corresponds to choosing a portfolio allocation that

minimizes ri sk , among all possible allocations that meet the ﬁrm requirements.

Another example is device sizing in electronic design, which is the task of choos-

ing 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 va-

riety 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 speciﬁed 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 ﬁnd the device sizes that satisfy the

design requirements (on manufacturability, timing, and area) and are most power

eﬃcient.

In data ﬁtting, the task is to ﬁnd a model, from a family of potential models,

that best ﬁts some observed data and prior information. Here the variables are the

parameters in the model, and the cons tr aints can represent prior information or

required l imit s on the parameters (such as nonnegativity). The objective function

might be a measure of misﬁt or prediction error between the observed data and

the values predicted by t he model, or a statistical measure of the u nli keliness or

implausibility of the parameter values. The optimization probl em (1.1) is to ﬁnd

the model parameter values that are consistent with the prior information, and give

the smallest misﬁt 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 opti-

mization problem, or some variation such as a multicriterion optimization problem.

Indeed, mathematical optimization has become an important tool in many areas.

It is widel y used in engineering, in electronic design automation, automatic con-

trol systems, and optimal design problems arising in civil, chemical, mechanical,

and aerospace engineering. Optimization is used for problems arising in network

design and operation, ﬁnance, 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 deci si on maker, system designer, or system operator, who supervises the

process, checks the results, and modiﬁ es 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 asset s to achieve the opt imal

portfolio.

A r el atively 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 em-

bedded 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 tradition al automatic control

systems and embedded optimization is well under way; in others, it is just start-

ing. 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 algor ith m that com-

putes 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 eﬀort

has gone into developing algorithms for solving various classes of optimization prob-

lems, analyzing their properties, and developing good software implementations.

The eﬀectiveness of these algorithms, i.e., our ability to solve the optimization prob-

lem (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 constr aint

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 diﬃcult to solve.

Approaches to the general problem therefore involve some kind of compromise, such

as very long computation time, or the possibility of not ﬁnding 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 diﬃcul t to solve. For a few problem classes we have

4 1 Introduction

eﬀective algorithms that can reliably solve even large problems, with hundreds or

thousands of variables and constraints. Two imp or tant and well known examples,

described in §1.2 below (and in detail in chapter 4), are least-squares problems and

linear programs. It i s less well known that convex optimization is another exception

to the rule: Like least-squares or linear programming, there are very eﬀe ct ive

algorithms that can reliably and eﬃciently 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 c omple te technical

treatment of these problems will be given in chapter 4.)

1.2.1 Least-squares problems

A least-squares problem is an optimi zati on problem with no constraints (i.e., m =

0) and an objective which is a sum of s qu ar es of terms of the form a

x − b

minimize f

(x) = kAx − bk

i=1

x − b

)

(1.4)

Here A ∈ R

k×n

(with k ≥ n), a

are the rows of A, and the vector x ∈ R

is the

optimization variable.

Solving l eas t-s quares problems

The solution of a least-squares problem (1.4) can be reduce d to solving a set of

linear equations ,

A)x = A

so we have the analytical solution x = (A

−1

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 n

k, 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 coeﬃcient 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 n

k. A current desktop computer can solve a sparse least-squares problem

1.2 Least-squares and li near 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 extr eme ly large problems (say, with millions of variables), or for problems

with exacting real-time c omput in g requirements, solving a least-square s problem

can be a challenge. But in the vast majority of cases, we can say th at existing

methods are very eﬀective, and extremely reliable. Ind ee d, we can say that solving

least-squares problems (that are not on the boundary of what is currently achiev-

able) 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-squ are s problem is the basis for regression analysis, optimal control, and

many parameter estimation and data ﬁtting methods. It has a number of statistical

interpretations, e.g., as maximum likelihood estimation of a vector x, given linear

measurements corr u pt ed by Gaussian measurement errors.

Recognizing an optimization problem as a least-s q uar es problem is straightfor-

ward; we only need to verify that the objective is a quadratic function (and then

test whether th e associated quadratic form is positive semideﬁnite). While the

basic l east -s q uar es problem has a simple ﬁxed form, several standard techniques

are used to increase its ﬂexibility in applications.

In weighted least-squares, the weighted least-squares cost

i=1

x − b

)

where w

, . . . , w

are positive, is minimized. (This problem is readily cast and

solved as a standard least-squares problem.) Here the weights w

are chosen to

reﬂect diﬀering levels of concern about the sizes of the t er ms a

x − b

, or simply

to inﬂuence the solution. In a statistical setting, weighted least-squares arises

in estimation of a vector x, given linear measurements corru pt ed by errors with

unequal variances.

Another technique in least-squares is regularization, in which extra terms are

added to the cost function. In the simpl es t case, a positive multiple of the sum of

squares of the variables is added to the cost function:

i=1

x − b

)

+ ρ

i=1

where ρ > 0. (This pr obl em too can be formulated as a standard least-squares

problem.) The extra terms penalize large values of x, and result in a sensible

solution in cases when minimizing the ﬁrst sum only does not. The parameter ρ is

chosen by the user to give the right trade-oﬀ between making the original objective

function

i=1

x−b

)

small, while keeping

i=1

not too big. Regularization

comes up in statistical estimation when the vector x to be e st imate d is given a prior

distribution.

Weighted least-squares and regul ari zati on are covered in chapter 6; their sta-

tistical interpretations are given in chapter 7.

6 1 Introduction

1.2.2 Linear programming

Another important class of optimization problems is linear programming, in which

the objective and all const r aint functions are linear:

minimize c

subject to a

x ≤ b

, i = 1, . . . , m.

(1.5)

Here the vectors c, a

, . . . , a

∈ R

and scalars b

, . . . , b

∈ R are problem pa-

rameters that specify the object ive and constraint functions.

Solving l ine ar programs

There is no simple analytical formula for the solution of a linear program (as there

is for a least-squares problem), but there are a variety of very eﬀective methods for

solving them, including Dantzig’s simplex method, and the more recent interior-

point metho d s descr ibed later in this book. While we cann ot give the exact number

of arithmetic operations required to solve a linear program (as we can for least-

squares), we c an establish rigorous bounds on the number of operations required

to solve a linear program, to a given accuracy, using an interior-point method. The

complexity in practice is order n

m (assuming m ≥ n) but with a constant that is

less well characterized than for least-sq uar es . These algorithms are quite r e li able,

although perhaps not quite as re liab le as methods for least-squares. We can easily

solve problems with hundreds of variables and thousands of constraints on a small

desktop computer, in a matter of seconds. If the problem is sparse, or has some

other exploitable structure, we can often solve problems with tens or hundreds of

thousands of variables and constraints.

As with least-squares problems, it is still a challenge to solve extremely large

linear pr ograms, or to solve linear programs with ex actin g real-time computing re-

quirements. But, like least-squares, we can say that solv in g (most) linear programs

is a mature technology. Linear programming solvers can be (and are) embedded in

many tools and applications.

Using linear programming

Some applications lead directly to linear programs in the form (1.5), or one of

several other standard forms. In many other cases the original optimization prob-

lem does not have a standard linear program form, but can be tr ans for med to an

equivalent linear program (and then, of course, solved) using techniques covered in

detail in chapter 4.

As a simple example, consider the Chebyshev approximation problem:

minimize max

i=1,...,k

x − b

(1.6)

Here x ∈ R

is the variable, and a

, . . . , a

∈ R

, b

, . . . , b

∈ R are parameters

that specify t he problem instance. Note the resemblance to the least-squares prob-

lem (1.4). For both problems, the objective is a measure of the size of the terms

x − b

. In least-squares, we use the sum of squares of the terms as objective,

whereas in Chebyshev approximation, we u s e the maximum of the absolute values.

剩余729页未读，继续阅读

guuuuu

粉丝: 77
资源: 23

理解和应用：凸优化及其数值解法

Convex Optimization_Boyd_英文版_凸优化_王会宁译_中文版

convex optimization.zip

convex optimization

convex optimization课后题答案

convex optimization stephen boyd pdf

convex optimization pdf

convex optimization中文版

convex optimization for signal processing

convex optimization cambridge university答案

algorithms for convex optimization pdf

最新资源