返回列表
最优化算法的简单基础介绍(主要侧重于二次规划(QP)的问题优化)
发布者:佚名发布时间:2024-09-09 13:04

最优化方法相当于一门学科,大多为求最大值最小值。因为我刚开始看什么都不懂,所以在网上搜集了一些资料,算个简单的基础吧,让大家对整个的比较熟悉,我主要关注的是二次规划问题(Quadratic Programming)QP 问题的求解,所以里面的更多的关于这个方面的。,

最优化问题根据变量取值可分为:连续最优化问题(continuous optimizationproblem)和离散最优化问题(discrete optimization problem),而离散最优化问题也称为组合优化问题(combinatorial optimization problem).
连续最优化问题又分为:
线性规划(linear program) (要求目标函数与约束条件均为线性的);
非线性规划(nonlinear program) (目标函数与约束条件未必是线性的).
非线性规划又可分为:
二次规划(quadratic program) (目标函数是二次,约束条件是线性);
凸规划(convex program) (目标函数是凸函数,约束条件是凸集);

离散最优化问题可分为:
整数规划(integer program);
0-1规划(0-1 program) ;
网络流问题(network flow problem) ;
旅行商问题(traveling salesman problem) .
上述线性规划、非线性规划、整数规划统称为数学规划(mathematical program-ming problem).

采用最优化算法解决实际问题主要分为下列两步:

 

最优化算法有三要素:变量(Decision Variable)、约束条件(Constraints)和目标函数(Objective function)。最优化算法,其实就是一种搜索过程或规则,它是基于某种思想和机制,通过一定的途径或规则来得到满足用户要求的问题的解。

搜到的几个简便易懂的博客的介绍,感谢下面博主的分享。
最优化算法——常见优化算法分类及总结【比较清晰 推荐】
常见的几种最优化方法
拉格朗日乘数法
[Math & Algorithm] 拉格朗日乘数法
凸优化问题,凸二次规划问题QP,凸函数

二次型最优控制QP的介绍:
什么是二次型最优控制
二次型最优控制
二次规划_1_——Lagrange方法
QP问题的解法(拉格朗日乘子法)
二次规划问题(Quadratic Programming)(Octave求解)

最优化系列(2)—— 最优化问题

关于梯度概念的补充:
梯度 ▽
  在微积分里面,对多元函数的参数求?偏导数,把求得的各个参数的偏导数以向量的形式写出来,就是梯度。比如函数f(x,y), 分别对x,y求偏导数,求得的梯度向量就是(?f/?x, ?f/?y)T,简称grad f(x,y)或者▽f(x,y)。对于在点(x0,y0)的具体梯度向量就是(?f/?x0, ?f/?y0)T.或者▽f(x0,y0),如果是3个参数的向量梯度,就是(?f/?x, ?f/?y,?f/?z)T,以此类推。
那么这个梯度向量求出来有什么意义呢?他的意义从几何意义上讲,就是函数变化增加最快的地方。具体来说,对于函数f(x,y),在点(x0,y0),沿着梯度向量的方向就是(?f/?x0, ?f/?y0)T的方向是f(x,y)增加最快的地方。或者说,沿着梯度向量的方向,更加容易找到函数的最大值。反过来说,沿着梯度向量相反的方向,也就是 -(?f/?x0, ?f/?y0)T的方向,梯度减少最快,也就是更加容易找到函数的最小值。
转载:感谢博主皮特大熊
推荐书籍:
1、最优化导论(第四版)(美)钟(Chong,E. K. P. ), (美) 扎克(Zak,S. H.) 著,孙志强 等译 /2015-10-01 /电子工业出版社
《最优化导论》-8梯度方法
《最优化导论》-20等式约束优化
内容编排合理,符合知识学习的基本逻辑;知识层次设计合理,大多数数学推导都伴以几何演示,便于学生理解和掌握;例题丰富;内容涵盖全面。
2、数值最优化方法 高立 编著 /2014-08-01 /北京大学出版社

《数值最优化方法》系统地介绍了数值求解光滑非线性无约束和有约束化问题的基本方法和基本性质。本书在选材上,注重化方法的基础性与实用性;在内容的处理上,注重由浅入深、循序渐进;在叙述上,力求清晰、准确、简明易懂。

3、运筹学与最优化方法 第2版 吴祈宗,侯福均 编著 /2013-03-01 /机械工业出版社 运筹学与最优化方法 第2版
4、最优化理论与算法(第二版) 陈宝林 编著 /2005-10-01 /清华大学出版社
最优化理论与算法
《最优化理论与算法》(陈宝林)——第7章:最优性条件

平台注册入口