深圳网站建设设计公司,ps网站首页直线教程,网站有收录但是没排名,wordpress 手册插件机器学习笔记之最优化理论与方法——最优化问题概述 引言什么是最优化问题最优化问题的基本形式最优化问题的分类各分类最优化问题的数学表达约束优化VS无约束优化线性规划VS非线性规划连续优化VS离散优化单目标优化VS多目标优化 引言
从本节开始#xff0c;将对最优化理论与… 机器学习笔记之最优化理论与方法——最优化问题概述 引言什么是最优化问题最优化问题的基本形式最优化问题的分类各分类最优化问题的数学表达约束优化VS无约束优化线性规划VS非线性规划连续优化VS离散优化单目标优化VS多目标优化 引言
从本节开始将对最优化理论与方法进行简单认识。
什么是最优化问题
无论是最优化理论还是最优化方法讨论的对象都是最优化问题。
关于最优化问题的一种简单描述最优化问题本质上属于决策问题。
例如路径选择问题确定达到目的地最佳路径的计量标准。其中问题的目标可能包含路径距离最短、行驶费用最少等等。再例如车辆调度问题通过制定行车路线使车辆再满足一定约束条件下有序通过一系列装货点和卸货点以达到如最短路程、耗时最少、费用最小等目标。
也就是说我们需要从若干个可执行策略中挑出一个/若干个策略从而使待处理问题的目标达到最优。
具体的说一个最优化问题会包含如下三个部分
决策变量在执行策略过程中需要做决定的信息。例如车辆调度问题中的路径选择。目标函数在制定策略之前需要明确要优化的目标。而目标函数是对目标的计量方式进行表达。目标函数可能不止一个不同角度的目标可能对应不同的目标函数。例如上述车辆调度问题中的最短路程、耗时最小、费用最小。它们都可以作为目标从而制定相应的目标函数。约束条件由可行策略组成的集合通常使用等式/不等式进行描述。
最优化问题的基本形式
关于最优化问题的数学符号表达如下 { min or max f ( x ) x ( x 1 , ⋯ , x p ) T s.t. { g i ( x ) ≤ 0 i 1 , 2 , ⋯ , m h j ( x ) 0 j 1 , 2 , ⋯ , l x ∈ X \begin{cases} \begin{aligned} \min \text{ or } \max f(x) \quad x (x_1,\cdots,x_p)^T \\ \text{s.t. } \begin{cases} g_i(x) \leq 0 \quad i1,2,\cdots,m \\ h_j(x) 0 \quad j 1,2,\cdots,l \\ \end{cases} \\ x \in \mathcal X \end{aligned} \end{cases} ⎩ ⎨ ⎧min or maxf(x)x(x1,⋯,xp)Ts.t. {gi(x)≤0i1,2,⋯,mhj(x)0j1,2,⋯,lx∈X 其中 x i ( i 1 , 2 , ⋯ , p ) x_i(i1,2,\cdots,p) xi(i1,2,⋯,p)是决策变量而 x x x则表示由若干决策变量组成的决策向量。 而目标函数作为目标的计量方式它必然与决策向量相关。它具体描述为关于决策向量的一个函数 也就是说一旦得到一个/一组确定的决策 x x x,必然会得到目标相应的计量结果 f ( x ) f(x) f(x)。 f ( x ) f ( x 1 , x 2 , ⋯ , x p ) f(x) f(x_1,x_2,\cdots,x_p) f(x)f(x1,x2,⋯,xp) 而 min f ( x ) \min f(x) minf(x)与 max f ( x ) \max f(x) maxf(x)分别表示对目标函数最小化或最大化根据实际情况而定。 而 g i ( x ) g_i(x) gi(x)同样是关于决策向量 x x x的一个函数。在执行决策的过程中可能存在相关资源的限制。而 g i ( x ) ≤ 0 g_i(x) \leq 0 gi(x)≤0则是一种不等式相关的条件限制称作不等式约束。 同理 h j ( x ) 0 h_j(x) 0 hj(x)0则是一种等式相关的条件限制被称作等式约束。 这里的 i , j i,j i,j描述不等式/等式约束的编号对应的 m , l m,l m,l描述不等式/等式约束的数量。 而 x ∈ X x \in \mathcal X x∈X则表示决策向量 x x x的定义域空间 X \mathcal X X。通常情况下对 X \mathcal X X的描述比较简单、宽泛。例如 X ∈ R p \mathcal X \in \mathbb R^p X∈Rp即 x x x是一个实数向量 X ∈ R p \mathcal X \in \mathbb R_^p X∈Rp即 x x x是一个非负的实数向量 X ∈ Z p \mathcal X \in \mathcal Z^p X∈Zp即 x x x是一个整数向量等等。根据具体的实际问题具体设置。
虽然 X \mathcal X X描述了 x x x的基本性质但并不代表 X \mathcal X X内的所有值 x x x都可以取到。观察如下集合 S { x ∈ X ∣ g i ( x ) ≤ 0 , i 1 , 2 , ⋯ , m ; h j ( x ) 0 , j 1 , 2 , ⋯ , l } \mathcal S \{x \in \mathcal X \mid g_i(x) \leq 0,i1,2,\cdots,m;h_j(x) 0,j1,2,\cdots,l\} S{x∈X∣gi(x)≤0,i1,2,⋯,m;hj(x)0,j1,2,⋯,l} 这个集合 S \mathcal S S同样是描述决策向量 x x x的集合但不同于 X \mathcal X X的是它被称作上述优化问题的可行域。也就是说决策向量 x x x可在可行域 S \mathcal S S内进行取值。而 x ∈ S x \in \mathcal S x∈S则表示在可行域范围 S \mathcal S S内的一种决策/一个决策向量 x x x也被称作一个可行解。
最优化问题的分类
关于上述最优化问题的基本形式/一般形式可以通过不同角度对最优化问题进行分类 这仅是几种常见分类~
如果最优化问题中没有约束条件(等式 h j ( x ) 0 h_j(x) 0 hj(x)0、不等式 g i ( x ) ≤ 0 g_i(x) \leq 0 gi(x)≤0约束)被称作无约束优化相反被称作约束优化如果最优化问题中目标函数/约束条件中存在非线性函数被称作非线性优化反之被称作线性优化 其中线性优化也即运筹学中的线性规划。关于决策向量 x x x对其内部随机变量的离散/连续性将其划分为离散优化/连续优化。 也可以通过可行域 S \mathcal S S内决策向量 x x x的数量进行表述。如果数量可数则是离散优化;反之则是连续优化。如果最优化问题中同时存在多个目标函数被称作多目标优化反之被称作单目标优化。
各分类最优化问题的数学表达
约束优化VS无约束优化
关于无约束优化的数学符号表示如下 min f ( x ) \min f(x) minf(x) 虽然在整个运筹学中最优化问题来自于实际的生产问题——在制定决策(目标函数)过程中该决策必然伴随着约束条件。 例如上面描述的资源限制、成本、人力、投资等等实际问题中的限制。
从而基于这些限制建模产生的优化问题通常情况下不会是无约束优化问题。但一些情况下我们可以通过一些策略将约束优化问题转化为无约束优化问题的形式并加以求解。例如一个约束优化示例表示如下 { min f ( x ) s.t. g ( x ) 0 \begin{cases} \min f(x) \\ \text{s.t. } g(x) 0 \end{cases} {minf(x)s.t. g(x)0 并将其转化为如下优化问题的表达形式 min { f ( x ) M ⋅ [ g ( x ) ] 2 } \min \left\{ f(x) \mathcal M \cdot [g(x)]^2 \right\} min{f(x)M⋅[g(x)]2} 其中 M \mathcal M M取一个充分大的数值。之所以将 M \mathcal M M取值充分大的目的是
在保证 f ( x ) f(x) f(x)达到最小之前必然要先保证 g ( x ) ⇒ 0 g(x) \Rightarrow 0 g(x)⇒0因为如果 g ( x ) ≠ 0 g(x) \neq 0 g(x)0那么 [ g ( x ) ] 2 [g(x)]^2 [g(x)]2必然是一个正值该结果与 M \mathcal M M相乘后必然是一个较大的量从而该结果必然与要优化的目标相悖。
可以通过这种方法可以将上述示例的约束优化问题转化为对应的无约束优化问题。一些常见的无约束优化方法如 这里没有添加链接的部分后续补上~
最速下降法(梯度下降法)牛顿法共轭梯度法
而上面这种将约束优化转化为无约束优化的约束优化方法被称作罚函数法。在后续进行逐步介绍。
线性规划VS非线性规划
关于线性规划标准形式的数学符号描述(示例)表示如下 { min C T x s.t. A x b ; x ≥ 0 \begin{cases} \min \mathcal C^T x \\ \text{s.t. } \mathcal A x b;x \geq 0 \end{cases} {minCTxs.t. Axb;x≥0
针对求解线性规划问题的常用方法是单纯形算法 ( Simplex Algorithm ) (\text{Simplex Algorithm}) (Simplex Algorithm)。它的思路可简单描述为 线性规划方法这里仅作科普使用~
算法支撑如果线性规划问题的最优解存在则一定可以在其可行域的顶点中找到。具体思路先找出可行域内的一个顶点根据一定规则判断其是否最优如果上述顶点不是最优则转换到与该顶点相邻的另一顶点并使目标函数达到最优直到找到某最优解为止。
关于非线性规划(示例)—— Markowitz \text{Markowitz} Markowitz均值-方差模型 假设投资市场中有 n n n个可投资的风险资产 ( Risk Assets ) (\text{Risk Assets}) (Risk Assets)对当前时刻的价格已知但不知其未来时刻的价格 其中编号为 i ( i 1 , 2 , ⋯ , n ) i(i1,2,\cdots,n) i(i1,2,⋯,n)的资产它的收益率表示为 R i \mathcal R_i Ri作为投资者在资产 i i i上的投资比重(单位百分比)记作 x i x_i xi其中 x i ∈ [ 0 , 1 ] x_i \in [0,1] xi∈[0,1]对应地投资者对所有风险资产均存在一个投资比重从而得到一个投资比重向量(决策向量) X \mathcal X X X ( x 1 , x 2 , ⋯ , x n ) T ∑ i 1 n x i 1 \mathcal X (x_1,x_2,\cdots,x_n)^T \quad \sum_{i1}^n x_i 1 X(x1,x2,⋯,xn)Ti1∑nxi1 关于决策向量 X \mathcal X X对应的收益量是关于 X \mathcal X X的一个函数并表示为如下形式 R ( X ) R 1 ⋅ x 1 R 2 ⋅ x 2 ⋯ R n ⋅ x n \mathcal R(\mathcal X) \mathcal R_1 \cdot x_1 \mathcal R_2 \cdot x_2 \cdots \mathcal R_n \cdot x_n R(X)R1⋅x1R2⋅x2⋯Rn⋅xn 由于这些资产是风险资产那么关于各资产的收益率 R i ( i 1 , 2 , ⋯ , n ) \mathcal R_i(i1,2,\cdots,n) Ri(i1,2,⋯,n)自然是不确定的。因而 R i \mathcal R_i Ri是一个随机变量在 Markowitz \text{Markowitz} Markowitz均值-方差模型中对收益描述表示为收益量期望 E [ R ( X ) ] \mathbb E[\mathcal R(\mathcal X)] E[R(X)]的形式 记 E [ R i ] r i ( i 1 , 2 , ⋯ , n ) \mathbb E[\mathcal R_i] r_i(i1,2,\cdots,n) E[Ri]ri(i1,2,⋯,n)。 E [ R ( X ) ] E [ R 1 ⋅ x 1 R 2 ⋅ x 2 ⋯ R n ⋅ x n ] r 1 ⋅ x 1 r 2 ⋅ x 2 ⋯ r n ⋅ x n ∑ i 1 n r i ⋅ x i \begin{aligned} \mathbb E[\mathcal R(\mathcal X)] \mathbb E[\mathcal R_1 \cdot x_1 \mathcal R_2 \cdot x_2 \cdots \mathcal R_n \cdot x_n] \\ r_1 \cdot x_1 r_2 \cdot x_2 \cdots r_n \cdot x_n \\ \sum_{i1}^n r_i \cdot x_i \end{aligned} E[R(X)]E[R1⋅x1R2⋅x2⋯Rn⋅xn]r1⋅x1r2⋅x2⋯rn⋅xni1∑nri⋅xi 由于收益的不确定性越大风险越大。因此 Markowitz \text{Markowitz} Markowitz均值-方差模型关于对风险的描述表示为收益量方差 Var [ R ( X ) ] \text{Var}[\mathcal R(\mathcal X)] Var[R(X)]衡量随机变量 R ( X ) \mathcal R(\mathcal X) R(X)关于期望结果 E [ R ( X ) ] \mathbb E[\mathcal R(\mathcal X)] E[R(X)]附近波动程度的考量 其中 Cov ( R i , R j ) \text{Cov}(\mathcal R_i,\mathcal R_j) Cov(Ri,Rj)表示随机变量 R i , R j \mathcal R_i,\mathcal R_j Ri,Rj的协方差结果。记作 σ i j \sigma_{ij} σij。 Var [ R ( X ) ] ∑ i 1 n ∑ j 1 n Cov ( R i , R j ) x i x j ∑ i 1 n ∑ j 1 n σ i j ⋅ x i x j \text{Var}[\mathcal R(\mathcal X)] \sum_{i1}^n\sum_{j1}^n \text{Cov}(\mathcal R_i,\mathcal R_j) x_i x_j \sum_{i1}^n\sum_{j1}^n \sigma_{ij} \cdot x_ix_j Var[R(X)]i1∑nj1∑nCov(Ri,Rj)xixji1∑nj1∑nσij⋅xixj 从而对应的最优化问题描述表示如下 { max ∑ i 1 n r i ⋅ x i min ∑ i 1 n ∑ j 1 n σ i j ⋅ x i x j \begin{cases} \begin{aligned} \max \sum_{i1}^n r_i\cdot x_i \\ \min \sum_{i1}^n \sum_{j1}^n \sigma_{ij} \cdot x_ix_j \end{aligned} \end{cases} ⎩ ⎨ ⎧maxi1∑nri⋅ximini1∑nj1∑nσij⋅xixj
针对上述问题一种建模方式是在给定收益量范围的条件下使风险达到最小 其中 Γ \Gamma Γ描述给定收益量范围的下界~ { min ∑ i 1 n ∑ j 1 n σ i j ⋅ x i x j s.t. { ∑ i 1 n r i ⋅ x i ≥ Γ ∑ i 1 n x i 1 X ≥ 0 \begin{cases} \begin{aligned} \min \sum_{i1}^n \sum_{j1}^n \sigma_{ij} \cdot x_i x_j \\ \text{s.t. } \begin{cases} \sum_{i1}^n r_i \cdot x_i \geq \Gamma \\ \sum_{i1}^n x_i 1 \\ \mathcal X \geq 0 \end{cases} \end{aligned} \end{cases} ⎩ ⎨ ⎧mini1∑nj1∑nσij⋅xixjs.t. ⎩ ⎨ ⎧∑i1nri⋅xi≥Γ∑i1nxi1X≥0 很明显虽然约束条件均是线性约束但目标函数明显是二次的、非线性的。关于上述问题的建模方式不止一种很容易能够联想到在给定风险接受范围的条件下使收益达到最大
同理这里的 Δ \Delta Δ描述风险接受范围的上界~无论上面还是下面都可以称作‘均值-方差模型’ Mean-Variance \text{Mean-Variance} Mean-Variance。不管是目标函数还是约束条件中存在非线性函数,它们都称作非线性优化问题。 { max ∑ i 1 n r i ⋅ x i s.t. { ∑ i 1 n ∑ j 1 n σ i j ⋅ x i x j ≤ Δ ∑ i 1 n x i 1 X ≥ 0 \begin{cases} \begin{aligned} \max \sum_{i1}^n r_i \cdot x_i \\ \text{s.t. } \begin{cases} \sum_{i1}^n \sum_{j1}^n \sigma_{ij} \cdot x_ix_j \leq \Delta \\ \sum_{i1}^n x_i 1 \\ \mathcal X \geq 0 \end{cases} \end{aligned} \end{cases} ⎩ ⎨ ⎧maxi1∑nri⋅xis.t. ⎩ ⎨ ⎧∑i1n∑j1nσij⋅xixj≤Δ∑i1nxi1X≥0
连续优化VS离散优化
这里依然以上述的均值-方差模型为例关于决策变量 x i ( i 1 , 2 , ⋯ , n ) x_i(i1,2,\cdots,n) xi(i1,2,⋯,n)的取值 ∈ [ 0 , 1 ] \in [0,1] ∈[0,1]也就是说该范围内的任意值均有意义。因而该优化也是连续优化
如果在均值-方差模型约束条件的基础上增加额外的约束条件将风险资产的投资数量限制在 m m m个 ( m n ) (m n) (mn)其余条件以及目标函数均不变。对应建模结果如下 可以利用指示函数 I ( ⋅ ) \mathbb I(\cdot) I(⋅)对该约束条件进行描述 ⇒ I ( x i ) { 1 if x i 0 0 Otherwise \Rightarrow \mathbb I(x_i) \begin{cases} 1 \quad \text{if }x_i 0 \\ 0 \quad \text{Otherwise} \end{cases} ⇒I(xi){1if xi00Otherwise { min ∑ i 1 n ∑ j 1 n σ i j ⋅ x i x j s.t. { ∑ i 1 n r i ⋅ x i ≥ Γ ∑ i 1 n x i 1 X ≥ 0 ∑ i 1 n I ( x i ) ≤ m \begin{cases} \begin{aligned} \min \sum_{i1}^n \sum_{j1}^n \sigma_{ij} \cdot x_i x_j \\ \text{s.t. } \begin{cases} \sum_{i1}^n r_i \cdot x_i \geq \Gamma \\ \sum_{i1}^n x_i 1 \\ \mathcal X \geq 0 \\ \sum_{i1}^n \mathbb I(x_i) \leq m \end{cases} \end{aligned} \end{cases} ⎩ ⎨ ⎧mini1∑nj1∑nσij⋅xixjs.t. ⎩ ⎨ ⎧∑i1nri⋅xi≥Γ∑i1nxi1X≥0∑i1nI(xi)≤m 很明显要从 n n n个风险资产中离散地选择 m m m个结果这是明显的离散优化并且是整数规划。
单目标优化VS多目标优化
依然可以使用 Markowitz \text{Markowitz} Markowitz均值-方差模型为例关于它的最优化问题 { max ∑ i 1 n r i ⋅ x i min ∑ i 1 n ∑ j 1 n σ i j ⋅ x i x j \begin{cases} \begin{aligned} \max \sum_{i1}^n r_i\cdot x_i \\ \min \sum_{i1}^n \sum_{j1}^n \sigma_{ij} \cdot x_ix_j \end{aligned} \end{cases} ⎩ ⎨ ⎧maxi1∑nri⋅ximini1∑nj1∑nσij⋅xixj 明显可以理解为包含两个目标函数的多目标优化关于多目标优化的处理方式
按照非线性规划中的处理方式将其中一个目标函数保留其他目标函数转化为约束条件将多目标优化转化为单目标优化。即多个目标函数整合成一个目标函数。例如给各目标函数赋予权重 通过负号将两个目标函数的优化方向归一;通过权重 τ \tau τ控制两个目标函数的比重。 min { τ ⋅ [ ∑ i 1 n ∑ j 1 n σ i j ⋅ x i x j ] − ∑ i 1 n r i ⋅ x i } \min \left\{\tau \cdot \left[\sum_{i1}^n \sum_{j1}^n \sigma_{ij} \cdot x_i x_j\right] - \sum_{i1}^n r_i \cdot x_i\right\} min{τ⋅[i1∑nj1∑nσij⋅xixj]−i1∑nri⋅xi}
相关参考 最优化理论与方法-第一讲最优化问题概述
