斯坦福与加州大学洛杉矶分校教授合作：《凸优化》详尽指南

需积分: 3 104 浏览量更新于2024-07-19 收藏 4.33MB PDF 举报

"《凸优化》是一本由Stephen Boyd和Lieven Vandenberghe合著的专业书籍，主要针对凸优化问题提供全面深入的介绍。凸优化在众多领域，如工程、计算机科学、数学、统计学、金融和经济学等，具有广泛的应用。本书首先从凸集和凸函数的基本概念出发，引导读者理解这一核心领域的基础。书中详尽地探讨了各种类型的凸优化问题，包括无约束最小化和有约束最小化问题，以及重要的对偶性和逼近技术。作者强调了识别问题为凸优化问题后选择最有效解法的重要性。为了帮助读者实践，书中提供了丰富的实例分析和习题，以便于学生、研究者和实际应用者进行学习和应用。该书特别关注数值方法，如内点法，这是一种高效的求解策略，尤其适用于处理复杂约束下的优化问题。作者还介绍了统计估计技巧，展示了如何将这些技术融入凸优化框架中，以解决实际中的挑战。出版商Cambridge University Press确保了这本书的全球发行，其网址为www.cambridge.org/9780521833783，读者可以通过这个平台获取更多信息。版权方面，本书受法律保护，未经许可复制仅限于法定例外和集体许可协议规定的范围。《凸优化》首次出版于2004年，反映了作者们多年的研究成果和教学经验，是一本兼具理论深度与实践指导价值的重要参考文献。对于那些希望深入了解和应用凸优化理论的人来说，这本书无疑是不可或缺的资源。"

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 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 R

from a set of candidate choices. The variable x

represents the choice made; the constraints f

(x) ≤ b

represent ﬁrm requirements

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)asrepresentingthe

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 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 ﬁ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 constraints can represent prior information or

required limits 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 the model, or a statistical measure of the unlikeliness or

implausibility of the parameter values. The optimization problem (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 widely 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 decision 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 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.Intheseem-

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 traditional 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 algorithm that com-

putes a solution of the problem (to some given accuracy), given a particular problem

from the class, i.e.,aninstance 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.(Aproblemissparse 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 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ﬃcult 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 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 eﬀective

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 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 a

x − b

minimize f

(x)=Ax −b



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 least-squares problems

The solution of a least-squares problem (1.4) can be reduced 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

剩余731页未读，继续阅读

morrismodel

粉丝: 1
资源: 3

斯坦福与加州大学洛杉矶分校教授合作：《凸优化》详尽指南

convex optimization.zip

Convex optimization 英文原版，可复制文字版

convex optimization-solution.docx

Convex Optimization

convex optimization中、英文双版

华为云：云服务器ECS实战部署.docx

【光学】基于matlab OAM涡旋光束(拉盖尔-高斯光束)【Matlab仿真 7508期】.zip

【无线定位】基于matlab改进的TOA求解信号最优的基站定位优化问题【Matlab仿真 8797期】.zip

Terraform：Terraform与Google Cloud集成实战.docx

【姿态估计】基于matlab扩展卡尔曼滤波器DEKF和9轴IMU姿态估计【Matlab仿真 8017期】.zip

最新资源