Lecture3——线性最优化(Linear Optimization)

2024-06-14 08:04

本文主要是介绍Lecture3——线性最优化(Linear Optimization),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一,本文重点

  • 线性最优化(LP)和标准线性最优化(Standard LP form)的定义
  • 如何将LP转换为Standard LP
  • 用Python解决LP问题
  • 将非线性最优化问题(NLP)转换为LP

二,定义

1,线性最优化
  • 定义

线性最优化问题,或者线性规划(linear programming,缩写:LP)是一个目标函数和所有限制函数(在决策变量中)都是线性的最优化问题。

注意:线性最优化是连续最优化的子集

  • 普遍表达

一个LP问题通常可以写成如下模式:

m1,m2,m3是{1,...,m}的子集,n1,n2,n3是{1,...,n}的子集。

注意:最大化问题与之类似。

  • 紧凑型表达

借助矩阵的知识,让形式更紧凑

在这里A1,A2,A3都是矩阵(维度为m1xn,m2xn,m3xn),b,d,e都是向量,变量x是维度为n的列向量。

2,标准形式(Standard LP form)
  • 定义

标准型通常更系统和紧凑,在不同的课本中对标准形式的定义可能不同,在本系列采用如下形式。

x∈Rn,A是维度为m×n的矩阵,b\in R^{m}

三,将LP转换为Standard LP

1,说明

标准形式主要用于分析,平时解决问题只需要能够便于理解就行,但LP到Standard LP的转换技巧可以帮助我们分析和解决问题

2,技巧和步骤

(1)步骤

  • 首先检查变量范围,Standard LP要求变量非负。
  • 然后检查目标函数,将求最大转换为求最小
  • 最后检查限制条件,将不等式转换为等式

(2)技巧(数学表达)

  • maxx c⊤x → minx −c⊤x
  • Ax ≤b →Ax+s =b,s ≥0
  • Ax ≥b →Ax−s =b,s ≥0
  • xi ≤ 0 →yi =−xi ≥0 free
  • xi → xi = x+ i −x− i ,x+ i ≥ 0,x− i ≥ 0
3,示例

转化为standard LP:

minimize -x1  -2x2

s.t             x1            +s1                    =100

                        2x2         +s2              =200

                 x1 + x2                 +s3       =150

                x1, x2, s1, s2, s3              >=0

四,用Python解决LP问题

1,方案

被用来解决最优化问题的语言有MATLAB,Python,Julia,而一个非常重要的库是CVX。课上教授用的多是MATLAB,不过笨人更习惯Python,所以会用Python来解决课程中的问题。学习步骤如下:

  • 下载cvxpy(Python中的CVX)
  • 学习如何使用
  • 解决问题

2,示例

以前文的例子为例:

使用Python解决:

#import package
import cvxpy as cp#decision variable
x1=cp.Variable()
x2=cp.Variable()#constraint
consts=[x1<=100,2*x2<=200,x1+x2<=150,x1>=0,x2>=0]#construct problem
obj=cp.Maximize(x1+2*x2)
prob=cp.Problem(obj,consts)#output result
result=prob.solve()
x1_sol=x1.value
x2_sol=x2.valueprint("Best result:",result)
print("Best x1:",x1_sol)
print("Best x2:",x2_sol)'''
Output:
Best result: 249.99999997999043
Best x1: 49.99999998623639
Best x2: 99.99999999687702
'''

五,非线性问题向线性问题的转化。

1,常见的非线性因素
  • 目标函数或限制条件自带最大值最小值函数
  • 目标函数或限制条件包含绝对值函数

对于两种问题有不同的解决方案

2,对于自带最大值最小值的问题
  • 最大化问题

(1)思路

假设变量S小于或等于问题中的min

(2)示例:

原问题:

转换:\Delta \leq t_{j+1}-t_{j}

结果:

  • 最小化问题

(1)思路

假设变量S大于或等于问题中的max

(2)示例

原问题:

转换:

结果:

3,对于绝对值
  • 最小化问题

采用最大值方式,假设变量t,使t大于或等于绝对值。

  • 通用模式(可将绝对值扩展到函数)

假设变量t,使t大于或等于函数。

  • 数学表达范例

minimize\underset{x}{}\sum_{i=1}^{n}f_{i}(x) s.t. x\in \Omega

可以转换成minimize\underset{x,t}{}\sum_{i=1}^{n}t_{i} s.t. x\in \Omega , f_{i}(x)\leq t_{i },\forall i

这篇关于Lecture3——线性最优化(Linear Optimization)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1059834

相关文章

线性因子模型 - 独立分量分析(ICA)篇

序言 线性因子模型是数据分析与机器学习中的一类重要模型,它们通过引入潜变量( latent variables \text{latent variables} latent variables)来更好地表征数据。其中,独立分量分析( ICA \text{ICA} ICA)作为线性因子模型的一种,以其独特的视角和广泛的应用领域而备受关注。 ICA \text{ICA} ICA旨在将观察到的复杂信号

理解分类器(linear)为什么可以做语义方向的指导?(解纠缠)

Attribute Manipulation(属性编辑)、disentanglement(解纠缠)常用的两种做法:线性探针和PCA_disentanglement和alignment-CSDN博客 在解纠缠的过程中,有一种非常简单的方法来引导G向某个方向进行生成,然后我们通过向不同的方向进行行走,那么就会得到这个属性上的图像。那么你利用多个方向进行生成,便得到了各种方向的图像,每个方向对应了很多

✨机器学习笔记(二)—— 线性回归、代价函数、梯度下降

1️⃣线性回归(linear regression) f w , b ( x ) = w x + b f_{w,b}(x) = wx + b fw,b​(x)=wx+b 🎈A linear regression model predicting house prices: 如图是机器学习通过监督学习运用线性回归模型来预测房价的例子,当房屋大小为1250 f e e t 2 feet^

【高等代数笔记】线性空间(一到四)

3. 线性空间 令 K n : = { ( a 1 , a 2 , . . . , a n ) ∣ a i ∈ K , i = 1 , 2 , . . . , n } \textbf{K}^{n}:=\{(a_{1},a_{2},...,a_{n})|a_{i}\in\textbf{K},i=1,2,...,n\} Kn:={(a1​,a2​,...,an​)∣ai​∈K,i=1,2,...,n

带头结点的线性链表的基本操作

持续了好久,终于有了这篇博客,链表的操作需要借助图像模型进行反复学习,这里尽可能的整理并记录下自己的思考,以备后面复习,和大家分享。需要说明的是,我们从实际应用角度出发重新定义了线性表。 一. 定义 从上一篇文章可以看到,由于链表在空间的合理利用上和插入、删除时不需要移动等优点,因此在很多场合下,它是线性表的首选存储结构。然而,它也存在某些实现的缺点,如求线性表的长度时不如顺序存储结构的

浙大数据结构:02-线性结构4 Pop Sequence

这道题我们采用数组来模拟堆栈和队列。 简单说一下大致思路,我们用栈来存1234.....,队列来存输入的一组数据,栈与队列进行匹配,相同就pop 机翻 1、条件准备 stk是栈,que是队列。 tt指向的是栈中下标,front指向队头,rear指向队尾。 初始化栈顶为0,队头为0,队尾为-1 #include<iostream>using namespace std;#defi

深度学习与大模型第3课:线性回归模型的构建与训练

文章目录 使用Python实现线性回归:从基础到scikit-learn1. 环境准备2. 数据准备和可视化3. 使用numpy实现线性回归4. 使用模型进行预测5. 可视化预测结果6. 使用scikit-learn实现线性回归7. 梯度下降法8. 随机梯度下降和小批量梯度下降9. 比较不同的梯度下降方法总结 使用Python实现线性回归:从基础到scikit-learn 线性

C#中的各种画刷, PathGradientBrush、线性渐变(LinearGradientBrush)和径向渐变的区别

在C#中,画刷(Brush)是用来填充图形(如形状或文本)内部区域的对象。在.NET框架中,画刷是System.Drawing命名空间的一部分,通常用于GDI+绘图操作。以下是一些常用的画刷类型: SolidBrush:用于创建单色填充的画刷。HatchBrush:用于创建具有图案填充的画刷。TextureBrush:用于创建具有图像纹理填充的画刷。LinearGradientBrush:用于创

(感知机-Perceptron)—有监督学习方法、非概率模型、判别模型、线性模型、参数化模型、批量学习、核方法

定义 假设输入空间(特征空间)是 χ \chi χ ⊆ R n \subseteq R^n ⊆Rn,输出空间是y = { + 1 , − 1 } =\{+1,-1 \} ={+1,−1} 。输入 x ∈ χ x \in \chi x∈χ表示实例的特征向量,对应于输入空间(特征空间)的点;输出 y ∈ y \in y∈y表示实例的类别。由输入空间到输出空间的如下函数: f ( x ) = s

逻辑回归与线性回归的目标函数和应用场景比较

概述 逻辑回归和线性回归是两种常用的预测模型,它们在目标函数和应用场景上存在显著差异。本文将详细比较这两种回归模型,并提供相应的代码示例。 线性回归 线性回归是一种预测连续数值的模型,其目标是找到特征( X )和目标变量( Y )之间的线性关系。线性回归的目标函数是最小化预测值和实际值之间的平方差,即均方误差(MSE)。 目标函数 线性回归的损失函数是均方误差: [ J(\theta)