数学优化问题(最优化问题)

点击次数:   更新时间:2020-06-30 00:23     来源:365官网

  数学优化(Mathematical Optimization)问题,也叫最优化问题,是指在一定约束条件下,求解一个目标函数的最大值(或最小值)问题。

  数学优化问题的定义为:给定一个目标函数(也叫代价函数)f : A → R,寻找一个变量(也叫参数)x∗∈ D,使得对于所有D中的x,f(x∗) ≤ f(x)(最小化);或者f(x∗) ≥ f(x)(最大化),其中D为变量x的约束集,也叫可行域;D中的变量被称为是可行解。

  根据输入变量x的值域是否为实数域,数学优化问题可以分为离散优化问题和连续优化问题。

  离散优化(Discrete Optimization)问题是目标函数的输入变量为离散变量,比如为整数或有限集合中的元素。连续优化(Continuous Optimization)问题是目标函数的输入变量为连续变量x ∈ Rd,即目标函数为实函数。离散优化问题主要有两个分支:

  离散优化问题的求解一般都比较困难,优化算法的复杂度都比较高。后面的内容主要以连续优化为主。

  在连续优化问题中,根据是否有变量的约束条件,可以将优化问题分为无约束优化问题和约束优化问题。

  约束优化问题(Constrained Optimization)中变量x需要满足一些等式或不等式的约束。约束优化问题通常使用拉格朗日乘数法来进行求解。

  如果目标函数和所有的约束函数都为线性函数,则该问题为线性规划问题(Linear Programming)。相反,如果目标函数或任何一个约束函数为非线性函数,则该问题为非线性规划问题(Nonlinear Programming)。

  在非线性优化问题中,有一类比较特殊的问题是凸优化问题(Convex Programming)。在凸优化问题中,变量x的可行域为凸集,即对于集合中任意两点,它们的连线全部位于在集合内部。目标函数f也必须为凸函数,即满足

  优化问题一般都是通过迭代的方式来求解:通过猜测一个初始的估计x0,然后不断迭代产生新的估计x1, x2, · · · xt,希望xt最终收敛到期望的最优解x∗。一个好的优化算法应该是在 一定的时间或空间复杂度下能够快速准确地找到最优解。同时,好的优化算法受初始猜测点的影响较小,通过迭代能稳定地找到最优解x∗的邻域,然后迅速收敛于x∗。

  优化算法中常用的迭代方法有线性搜索和置信域方法等。线性搜索的策略是寻找方向和步长,具体算法有梯度下降法、牛顿法、共轭梯度法等。

  对于很多非线性优化问题,会存在若干个局部的极小值。局部最小值,或局部最优解x∗定义为:存在一个δ 0,对于所有的满足x − x∗≤ δ 的x,公式f(x∗) ≤ f(x)成立。也就是说,在x∗的附近区域内,所有的函数值都大于或者等于f(x∗)。对于所有的x∈A,都有f(x∗) ≤ f(x)成立,则x∗为全局最小值,或全局最优解。一般的,求局部最优解是容易的,但很难保证其为全局最优解。对于线性规划或凸优化问题,局部最优解就是全局最优解。

  【概述】 SVM训练分类器的方法是寻找到超平面,使正负样本在超平面的两侧(分类正确性即“分得开”),且样本到超平面...

  [原]量化投资教程:基于Spark的ADMM分布式算法在组合优化中的应用

  概述 首先,您有必要了解一下,为什么我们需要用分布式算法来计算我们的组合优化问题。 在实际生产中,即使我们基于传统...

  本章涉及到的知识点清单:1、决策面方程2、函数间隔和几何间隔3、不等式约束条件4、SVM最优化模型的数学描述(凸二...

  李理:Theano tutorial和卷积神经网络的Theano实现 Part1

  本系列文章面向深度学习研发者,希望通过Image Caption Generation,一个有意思的具体任务,深入...

  以西瓜书为主线,以其他书籍作为参考进行补充,例如《统计学习方法》,《PRML》等 第一章 绪论 1.2 基本术语 ...

365官网
CopyRight 365官网 ALL Rights Reserved