凸优化在机器学习中的应用

机器学习

148 浏览量更新于2024-06-27 2 收藏 11.07MB PDF 举报

身份认证购VIP最低享 7 折!

30元优惠券

"Convex Optimization for Machine Learning.pdf" 这篇资源是一本关于凸优化在机器学习中应用的书籍，作者是Changho Suh。凸优化是一种强大的优化方法，它在计算机科学，尤其是机器学习领域，有着广泛应用。这本书旨在帮助读者理解和掌握凸优化的基本概念，并教导如何将这些理论应用于实际的机器学习任务。凸优化的核心在于它处理的是凸函数，这种函数具有全局最优解的特性，因此可以避免在多维度空间中陷入局部最优。在机器学习中，我们经常需要优化模型的参数以最小化损失函数，凸优化提供了一种有效且理论上保证找到全局最优解的方法。这在训练复杂的模型，如支持向量机(SVM)、逻辑回归和一些深度学习网络中尤其重要。书中的内容可能涵盖了以下知识点： 1. **凸函数与凸集**：首先，会介绍凸函数的定义和性质，以及如何识别凸函数。此外，还会讨论凸集的概念，它是凸优化问题的基础。 2. **凸优化基本理论**：包括凸优化问题的形式化定义，如线性规划、二次规划和锥规划，以及相关的算法，如梯度下降法、牛顿法和拟牛顿法。 3. **凸分析**：深入讲解与凸优化相关的数学工具，如微分学、凸分析和泛函分析，这些是理解和解决凸优化问题的关键。 4. **机器学习中的凸优化**：书中会阐述凸优化在机器学习中的应用，比如在逻辑回归、朴素贝叶斯分类器、支持向量机等模型中的优化过程。 5. **算法实现与案例研究**：可能包含实际的编程练习和案例研究，让读者有机会实践如何在实际问题中应用凸优化。 6. **非凸优化的凸近似**：在某些情况下，虽然问题本身是非凸的，但可以通过构建凸近似来寻找接近全局最优的解。 7. **开放访问与许可**：该作品遵循Creative Commons Attribution-NonCommercial许可，允许非商业性的分享和使用。这本书的出版得到了Google教育赠款和韩国信息通信技术规划与评估院(IITP)的资助，表明了凸优化在当前学术界和工业界的重视程度。同时，作者特别感谢Hyun Seung Suh提供的初学者视角的反馈，这有助于确保书中的内容对初学者来说是清晰易懂的。通过阅读这本书，读者不仅可以深化对凸优化的理解，还能学会如何将其应用于机器学习项目中，解决实际问题，提升模型的性能和效率。

资源详情

资源推荐

8 Convex Optimization Basics

in which the objective function and the functions that appear in constraints are

all linear. We will delve into its formal deﬁnition later on. Unlike the least-squares

problem, the LP has no closed form solution. But the good news is that Kantorovich

could develop a very efﬁcient algorithm that achieves the optimal solution. Actually

having a closed form solution is not that important as long as we know how to get

to the optimal solution. This achievement won him the Nobel Prize in Economics

in 1975 (Kantorovich, 1989).

The development of LP made people become very excited again, trying to

translate an interested problem into a least-squares problem or LP. While many

LP-translation techniques (that we will also study) have been developed, people

encountered still many situations in which the translation is not doable.

A class of tractable optimization problems Inspired by the development

of LP, people tried to come up with a class of tractable optimization problems

which can be solved reliably & efﬁciently. LP is one such instance. In a decade,

another tractable problem, called quadratic program (QP), was developed (Frank

and Wolfe, 1956). It is a generalized version, as it includes as special cases the least-

squares problem and LP. See Fig. 1.5.

In the 1990s, another problem, called second-order cone program (SOCP),

was developed which subsumes as special cases all of the prior problems (Nes-

terov and Nemirovskii, 1994). Around at the same time, a larger class of problem,

called semi-deﬁnite program (SDP), was developed (Alizadeh, 1991; Nesterov and

Nemirovskii, 1994). More and more tractable problems have been developed so far.

It turns out that all of the tractable problems share the common property (concern-

ing the word “convex”), and this property established the class of tractable prob-

lems, named convex optimization, which we will focus mostly on throughout this

book.

Least-squares

Linear Program

(LP)

Quadratic Program (QP)

Second-Order Cone Program

(SOCP)

Semi-Definite Program

(SDP)

……

Convex Optimization

1939

1800s

1956

1994

Figure 1.5. A class of tractable optimization problems: Convex optimization.

10 Convex Optimization Basics

1.2 Deﬁnition of Convex Optimization

Recap In the last section, we ﬁgured out how the optimization theory was devel-

oped. There were two breakthroughs in the history of optimization. The ﬁrst was

made by the famous Gauss. In the process of solving an astronomy problem of ﬁg-

uring out the orbit of Ceres (which many astronomers were trying to address in

the 1800s), he could develop an optimization problem, which is now known as

the least-squares problem. The beauty of the least-squares problem is two folded:

(i) it has a closed form solution; and (ii) there is an algorithm which enables us to

efﬁciently do matrix inversion required for computing the solution. The beauty of

the problem opened up the optimization ﬁeld and has played a signiﬁcant role in

the ﬁeld.

The second breakthrough was made by Leonid Kantorovich. In the process of

solving a military-related problem, he could formulate a problem which is now

known as linear program (LP). The good thing about LP is that there is an efﬁcient

algorithm which allows us to compute the optimal solution reliably and efﬁciently

although the closed form solution is unknown. In other words, Kantorovich came

up with the concept of tractable optimization problems which can be solved via

an algorithm without the knowledge of the concrete form of the optimal solution.

This motivated many followers to mimic his approach, thereby coming up with

a class of tractable optimization problems: convex optimization. See the class of

convex optimization problems in Fig. 1.6.

Outline The goal of this section is to understand what convex optimization is.

To this end, we will cover four stuffs. First we will study a standard mathematical

formulation of optimization problems. It turns out the deﬁnition of convex opti-

mization problems requires the knowledge of convex functions. But the deﬁnition of

convex functions relies upon the concept of convex sets. So in the second part, we

Least-squares

Linear Program

(LP)

Quadratic Program (QP)

Second-Order Cone Program

(SOCP)

Semi-Definite Program

(SDP)

……

Convex Optimization

1939

1800s

1956

1994

Figure 1.6. A class of tractable optimization problems: Convex optimization.

Deﬁnition of Convex Optimization 11

will study what the convex set is. We will also investigate some important examples

which help us to be familiar with the concept as well as which play an important

role in deﬁning convex optimization. Next we will study the deﬁnition of convex

functions, building upon a couple of examples and crucial properties to be explored

in depth. Using all of these, we will ﬁnally investigate a standard mathematical for-

mulation of convex optimization problems.

Optimization problem in standard form Let us start by recalling the deﬁni-

tion of optimization: Choosing an optimization variable that minimizes (or maxi-

mizes) a certain quantity of interest possibly given constraints. We denote the opti-

mization variable by x := [x

, . . . , x

]

∈ R

where d indicates the dimension

of the variable. Denote the objective function (the certain quantity) by f (x) ∈ R.

Notice that the objective function should always be a real number, not a vector.

There are two types of constraints: (i) inequality constraints; and (ii) equality con-

straints. The inequality constraints are represented by the form like f

(x) ≤ c

where

i ∈ {1, . . . , m}. Here m indicates the number of the constraints. Without loss of

generality (WLOG), the constant c

can be merged with f

(x) and hence the form

can be simpliﬁed as: f

(x) ≤ 0. Here the WLOG means that the general case can

readily be covered with some proper modiﬁcation to the simpliﬁed case of focus.

That’s why here we say that there is no loss of generality although we focus on the

simpliﬁed case. Similarly the equality constraints can be represented by: h

(x) = 0

where i ∈ {1, . . . , p} and p denotes the number of the equality constraints.

Using these notations, one can write the standard form of optimization prob-

lems as:

min

x∈R

f (x)

subject to f

(x) ≤ 0, i ∈ {1, 2, . . . , m},

(x) = 0, i ∈ {1, 2, . . . , p}.

(1.6)

WLOG, it sufﬁces to consider the minimization problem, since the maximization

problem can readily come by ﬂipping the sign of f (x): min f (x) is equivalent to

max −f (x). Here we have two conventions that allow us to simplify the above

form (1.6). First we use the colon “:” to indicate the “subject to”. Second, x ∈ R

placed below min is often omitted since the role of x is clear enough from the

context. Hence, the simpler form reads:

min f (x) : f

(x) ≤ 0, i ∈ {1, 2, . . . , m},

(x) = 0, i ∈ {1, 2, . . . , p}.

(1.7)

12 Convex Optimization Basics

Two more things to note. One is the optimal value, denoted by p

∗

:= min f (x).

The other is the optimal solution, denoted by x

∗

:= arg min f (x). Or it is called the

minimizer. Here “arg min” stands for “argues the one that minimizes”.

Convex set Now what is convex optimization that we wish to ﬁgure out in this

section? As mentioned in the beginning, to deﬁne this, we need to know about the

concept of convex functions. But the deﬁnition of convex functions requires the

knowledge of convex sets. So we will ﬁrst study the deﬁnition of the convex set.

A set S is said to be convex if and only if

x, y ∈ S H⇒ λx + (1 − λ)y ∈ S, ∀λ ∈ [0, 1] (1.8)

where the sign “∀” means “for all”.

Examples: Point, line, plane, line segment, … To get a concrete feel about

what the convex set means, let us explore several examples. The ﬁrst simplest exam-

ple is the set containing a single point. This is obviously a convex set, as any convex

combination that lies in between x and y, represented as λx +(1 − λ)y, is just the

single point.

The second simplest example is perhaps the set that contains a line that lives in a

2-dimensional ambient space. This is also convex because any convex combination

of two points lying on a line should also lie on the line. Here let us investigate

how to represent the convex set. This representation will help us to understand the

concept of convex optimization later on. Notice that the line in a 2-dimensional

space can be represented as: y = ax + b where a and b indicate the slope and

y-intercept, respectively. Hence, one can represent the set as:

S = {x := [x

, x

]

: x

= a

+ b

}. (1.9)

Here we use the notations (x

, x

) instead of (x, y); also (a

, b

) instead of (a, b).

Using vector notations, one can deﬁne a := [−a

, 1]

and b

:= b, which in turn

simpliﬁes the representation (1.9) as:

S = {x : a

x − b = 0}. (1.10)

The third example is the naive extension of the second example: a plane living

in a 3-dimensional space. This is also obviously a convex set, as any combination of

two points lying on a plane also lies on the plane. The representation of the convex

set is exactly the same as (1.10), except that now the dimension of x and a are 3.

Why?

The fourth example is the one in which the dimension of an object of interest

differs from d ≥ 2 by 2. One such example is the set that contains a line living

in a 3-dimensional space. This is also a convex set, since the object of interest is a

剩余378页未读，继续阅读

努力+努力=幸运

粉丝: 2
资源: 136

凸优化在机器学习中的应用

MIT Optimization for Machine Learning.2012.

Optimization Methods for Large-Scale Machine Learning

MIT Optimization for Machine Learning

MIT Optimization for Machine Learning.

First-Order and Stochastic Optimization Methods for Machine Learning.pdf

MIT+-+Optimization+for+Machine+Learning.2012.pdf

一个基于 Vue.js 的简单游戏项目示例：猜数字游戏 这个游戏的目标是让用户猜测一个随机生成的数字，并根据用户的输入给出提示

thinc_gpu_ops-0.0.4+cuda102-cp35-cp35m-win_amd64.whl

android自定义5级联动,使用Android如何实现5级联动地址选择器

精灵破坏粉碎爆炸切割割片插件：Destructible 2D v3.0.10

课程作业管理&基于java的课程作业管理系统设计与实现（毕业论文+ppt+开题报告）

基于车载相机的深度感知算法研究

Pytorch基础.ipynb

基于YOLOv11的口罩佩戴检测系统（包含详细的完整的程序和数据）

simplejson-3.17.6-cp39-cp39-win_amd64.whl

生成式人工智能大模型及其电力系统数智化应用前沿报告

基于MMSkeleton工具包中的ST-GCN模型实现一种基于动态拓扑图的人体骨架动作识别算法python源码+使用说明.zip

【Unity高级实例化插件】GPU Instancer 轻松创建大规模、高细节密度的游戏环境

招聘信息管理系统-论文.zip

Pycluster-1.59-cp38-cp38-win_amd64.whl

最新资源

一个基于 Vue.js 的简单游戏项目示例：猜数字游戏这个游戏的目标是让用户猜测一个随机生成的数字，并根据用户的输入给出提示