深度学习中的凸优化实战

需积分: 9 70 浏览量更新于2024-07-18 1 收藏 5.33MB PDF 举报

"《凸优化》是斯蒂芬·博伊德和利文·范登伯格合著的一本关于凸优化的专著，由剑桥大学出版社出版。该书详细探讨了在人工智能和机器学习领域中凸优化的重要性和应用。" 在人工智能和机器学习中，凸优化扮演着至关重要的角色。凸优化是数学优化的一个分支，其目标是找到在一个凸函数定义下的全局最小值。与一般的非凸优化问题相比，凸优化问题的解通常更容易求得，因为它们确保了局部最优解同时也是全局最优解，这极大地简化了优化过程，并为复杂问题提供了稳定且可靠的解决方案。博伊德和范登伯格的这本书详细阐述了凸优化的基本理论，包括凸集、凸函数的性质、凸优化问题的形式化描述以及解决这些优化问题的算法。书中涵盖了线性规划、二次规划、锥优化、几何编程等关键主题，并介绍了如梯度下降法、拟牛顿法等优化算法。此外，作者还讨论了在信号处理、控制系统、通信网络、统计学习和图像处理等领域的应用案例。凸优化在机器学习中的应用广泛，尤其是在训练神经网络、支持向量机、逻辑回归等模型时，通过凸优化可以有效地求解权重参数，以最小化预测误差。例如，在深度学习中，反向传播算法配合梯度下降就是一种常见的凸优化策略，用于调整网络的权重以最小化损失函数。书中还涉及了凸优化的对偶理论，这是理解和解决大型优化问题的一种有力工具。对偶问题可以提供关于原问题的洞察，并在某些情况下，通过求解对偶问题可以更高效地找到原问题的解。《凸优化》不仅为读者提供了凸优化的理论基础，还提供了实用的算法和实际应用示例，是学习和研究凸优化的理想教材。无论对于学术研究还是工业实践，它都是一份宝贵的资源。

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 us ed 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) = 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 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 curr ent

desktop computer can s olve 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 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 eﬀective, and extremely reliable. Indeed, 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-squares 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 corrupted by Gaussian measurement errors.

Recognizing an optimization problem as a least-squares problem is straightfor-

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

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

basic least-squares 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 terms 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 corrupted by errors with

unequal variances.

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

added to the cost function. In the simplest 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 problem 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 estimated is given a prior

distribution.

Weighted least-squares and regularization 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 constraint 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 objective and constraint functions.

Solving linear 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 methods described later in this book. While we cannot give the exact number

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

squares), we can 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-squares. These algorithms are quite reliable,

although perhaps not quite as reliable 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 programs, or to solve linear programs with exacting real-time computing re-

quirements. But, like least-squares, we can say that solving (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 transformed 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 the 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 use the maximum of the absolute values.

1.3 Convex optimization 7

One other important distinction is that the objective function in the Chebyshev

approximation problem (1.6) is not diﬀerentiable; the objective in the least-squares

problem (1.4) is quadratic, and therefore diﬀerentiable.

The Chebyshev approximation problem (1.6) can be solved by solving the linear

program

minimize t

subject to a

x − t ≤ b

, i = 1, . . . , k

−a

x − t ≤ −b

, i = 1, . . . , k,

(1.7)

with variables x ∈ R

and t ∈ R. (The details will be given in chapter 6.)

Since linear programs are readily s olved, the Chebyshev approximation pr oblem is

therefore readily solved.

Anyone with a working knowledge of linear programming would recognize the

Chebyshev approximation problem (1.6) as one that can be reduced to a linear

program. For those without this background, though, it might not be obvious that

the Chebyshev approximation problem (1.6), with its nondiﬀerentiable objective,

can be formulated and solved as a linear program.

While recognizing problems that can be reduced to linear programs is more

involved than recognizing a least-squares problem, it is a skill that is readily ac-

quired, since only a few standard tricks are used. The task can even be partially

automated; some software systems for specifying and solving optimization prob-

lems can automatically recognize (some) problems that can be reformulated as

linear programs.

1.3 Convex optimization

A convex optimization problem is one of the form

minimize f

(x)

subject to f

(x) ≤ b

, i = 1, . . . , m,

(1.8)

where the functions f

, . . . , f

: R

→ R are convex, i.e., satisfy

(αx + βy) ≤ αf

(x) + βf

(y)

for all x, y ∈ R

and all α, β ∈ R with α+ β = 1, α ≥ 0, β ≥ 0. The least-squares

problem (1.4) and linear programming problem (1.5) are both special cases of the

general convex optimization problem (1.8).

1.3.1 Solving convex optimization problems

There is in general no analytical formula for the solution of convex optimization

problems, but (as with linear programming problems) there are very eﬀective meth-

ods for s olving them. Interior-point methods work very well in practice, and in some

cases can be proved to solve the pr oblem to a speciﬁed accuracy with a number of

8 1 Introduction

operations that does not exceed a polynomial of the problem dimensions. (This is

covered in chapter 11.)

We will see that interior-point methods can solve the problem (1.8) in a num-

ber of steps or iterations that is almost always in the range between 10 and 100.

Ignoring any structure in the problem (such as sparsity), each step requires on the

order of

max{n

, n

m, F }

operations, where F is the cost of evaluating the ﬁrst and second derivatives of the

objective and constraint functions f

, . . . , f

Like methods for solving linear programs, these interior-point methods are quite

reliable. We can easily solve problems with hundreds of variables and thousands

of constraints on a current desktop computer, in at most a few tens of seconds. By

exploiting problem structure (such as sparsity), we can solve far larger problems,

with many thousands of variables and constraints.

We cannot yet claim that solving general convex optimization problems is a

mature technology, like solving least-squares or linear programming problems. Re-

search on interior-point methods for general nonlinear convex optimization is still

a very active research area, and no consensus has emerged yet as to what the best

method or methods are. But it is reasonable to expect that solving general con-

vex optimization problems will become a technology within a few years. And for

some subclasses of convex optimization problems, for example second-order cone

programming or geometric programming (studied in detail in chapter 4), it is fair

to say that interior-point methods are approaching a technology.

1.3.2 Using convex optimization

Using convex optimization is, at least conceptually, very much like using least-

squares or linear programming. If we can formulate a problem as a convex opti-

mization problem, then we can solve it eﬃciently, just as we can solve a least-squares

problem eﬃciently. With only a bit of exaggeration, we can say that, if you formu-

late a practical problem as a convex optimization problem, then you have solved

the original problem.

There are also some important diﬀerences. Recognizing a least-squares problem

is straightforward, but recognizing a convex function can be diﬃcult. In addition,

there are many more tricks for transforming convex problems than for transforming

linear programs. Recognizing convex optimization problems, or those that can

be transformed to convex optimization problems, can therefore be challenging.

The main goal of this book is to give the reader the background needed to do

this. Once the skill of recognizing or formulating convex optimization problems is

developed, you will ﬁnd that surprisingly many problems can be solved via convex

optimization.

The challenge, and art, in using convex optimization is in recognizing and for-

mulating the problem. Once this formulation is done, solving the problem is, like

least-squares or linear programming, (almost) technology.

剩余727页未读，继续阅读

平江一声吼

粉丝: 0
资源: 7

深度学习中的凸优化实战

最优化理论convex optimization全本加答案解析加课件，超精品

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

1-convex optimization.pdf

convex optimization课后题答案

convex optimization stephen boyd pdf

convex optimization pdf

convex optimization中文版

convex optimization for signal processing

algorithms for convex optimization pdf

convex optimization cambridge university答案

最新资源