算法中的最优化方法01
00 课程简介
优化尽可能用最佳的方式处理一下事项
- 计算机中基于优化的算法
- 多准则控制器的设计
- 模糊建模中的聚类
- 机器人轨迹规划
- 流程工业中的调度
- 系统参数估计
- 连续时间系统的数字计算机仿真
- 具有输入饱和的预测控制器设计
相关课程
- 模型预测控制
- 过滤和识别
- 最优控制理论
- 凸优化与系统理论
三个子问题
- 方案 Formulation
- 工程需求和要求的翻译
- 转化为数学上定义良好的优化问题
- 初始化 Initialization
- 正确算法的选择
- 参数初始值的选择
- 优化程序 Optimization procedure
- 各种优化技术
- 各种计算机平台
课程目录 Context . Optimization Techniques
- 课程简介 Introduction
- 线性规划 Linear Programming
- 二次规划 Quadratic Programming
- 非线性规划 Nonlinear Optimization
- 非线性规划中的约束 Constraints in Nonlinear Optimization
- 凸优化 Convex Optimization
- 全局优化 Global Optimization
- 总结 Summary
- 优化工具箱 Matlab Optimization Toolbox
- 多目标优化 Multi-Objective Optimization
- 整数优化 Integer Optimization
第一讲 介绍 Introduction
一、数学框架
\[\min_x f(x) \]s.t.
\[h(x) = 0 ( 等式约束 )\\g(x)≤0(不等式约束) \]其中f(x)是标量, h(x)g(x)可能是矢量。
· 无约束的优化
\[\min_x f(x)=f(x^*) \]\[其中: x^*=arg \min_x f(x)=f(x^*) \]· 有约束的优化
\[f(x^*) = \min_x f(x) \\h(x^*)=0 \\g(x^*)≤0 \\其中: x^* = arg \{ \min_x f(x) , h(x)=0 , g(x)≤0 \} \]· 值的转化
\[\max_x f(x) = -\min_x (-f(x)) \]二、优化问题的分类(见更新)
- 线性规划
- 二次规划
- 凸优化
- 非线性优化
三、凸集和凸函数
1.凸集(Convex Set)
\[若C是集合, x,y ∈ C , \lambda∈[0,1]:若满足(1-\lambda)x+\lambda y∈C,则称C为凸集. \]2.单峰函数(Unimodel Function)
若函数 f 满足以下条件:
- \[dom(f)(f的定义域)是一个凸集, \]
- \[\exist x^* ∈ dom(f)满足f(x^*) ≤ f(x) ,\forall x ∈ dom(f ), \]
- \[对 \forall x_0 ∈ dom(f),总有一条轨迹x(\lambda)∈ dom(f),其中x(0)=x_0且x(1)=x^*,\\并有f(x(\lambda))≤f(x_0),\forall \lambda ∈[0,1]. \]
3. 拟凸函数(Quasiconvex function)
若函数 f 满足:
\[\\dom(f)是一个凸集 \\\forall x,y∈dom(f),\forall \lambda ∈[0,1],都有f((1-\lambda)x+\lambda y)≤max\{f(x),f(y)\}. \]则称函数 f 是一个拟凸函数 。
另一种定义:
若函数 f 任意数值等高线下所有的可行域都为凸集,则称 f 为拟凸函数。
\[\forall \alpha ∈f(x),L(α) = \{ x ∈ dom(f ) : f (x) ∈ α \},其中L(α)为凸集。 \]4. 凸函数
若函数 f 满足:
\[\\dom(f)是一个凸集 \\\forall x,y∈dom(f),\forall \lambda ∈[0,1],都有f((1 − λ)x + λy)= (1 − λ)f (x) + λf (y) \]则称函数 f 是一个凸函数 。
四、梯度和海森矩阵
梯度(gradirnt)的定义如下:
\[∇f(x) = \begin{bmatrix} ∂f/∂x_1 \\ ∂f/∂x_2 \\ :\\ ∂f/∂x_n \end{bmatrix} \]海森(Hessian)矩阵的定义如下:
\[H(x) = \begin{bmatrix} ∂f^2/∂x^2_1&∂f^2/∂x_1∂x_2&...&∂f^2/∂x_1∂x_n \\ ∂f^2/∂x_2∂x_1&∂f^2/∂x^2_2&...&∂f^2/∂x_2∂x_n \\ :&:&&:\\ ∂f^2/∂x_n∂x_1&∂f^2/∂x_n∂x_2&...&∂f^2/∂x^2_n \end{bmatrix} \]Jacobi矩阵定义如下:其中h为向量组函数,x为变量
\[∇h(x) = \begin{bmatrix} ∂h_1/∂x_1&∂h_2/∂x_1&...&∂h_m/∂x_1\\ ∂h_1/∂x_2&∂h_2/∂x_2&...&∂h_m/∂x_2\\ :&:& &:\\ ∂h_1/∂x_n&∂h_2/∂x_n&...&∂h_m/∂x_n \end{bmatrix} \]函数 f 在x0点处沿β方向的方向导数为:
\[D_βf (x_0) = ∇^Tf (x_0) · β = ||∇f (x0)||_2 cos θ \]∇ f (x0) 和 β 在平行时。D在 ∇ f (x0) 方向上取得最大增幅。对应地,-∇ f (x0) 为其最陡下降方向,该方向垂直于通过x0等高线。
正定矩阵
设A为n阶方阵,若对于任意n×1的x矩阵,都有:
\[x^T A x>0 \]则称A为正定矩阵,若上式≥0则称为半正定矩阵。
正定矩阵的所有特征值都>0,半正定矩阵的所有特征值都≥0。
正定矩阵的所有顺序主子式都>0,半正定矩阵的所有顺序主子式都≥0。
极值的特性
∇f (x) = 0 且 H(x) > 0 → 极小值
∇f (x) = 0 且 H(x) < 0 → 极大值
∇f (x) = 0 且 H(x)不定 → 鞍点
Kuhn-Tucker条件与全局最优互为充要条件
5.收敛
\[\beta_1 = \lim_{k→\infin}{||x_{k+1}-x^*||_2 \over || x_k - x^* ||_2 } \]线性收敛时,β1∈(0,1);超线性收敛时β1=0.
\[\beta_2 = \lim_{k→\infin}{||x_{k+1}-x^*||_2 \over || x_k - x^* ||_2^2 } \]二次收敛时,β2∈(0,1)。
标签:01,dom,矩阵,算法,Optimization,forall,优化,最优化,lambda From: https://www.cnblogs.com/Qujinkongyuyin/p/16704514.html