【优化1】线性优化

概览

线性优化,指的是目标函数和约束条件都是线性的优化问题。

面对一个优化问题,首先需要建立优化问题的模型,因此需要编程语言;对优化问题建模后需要求解该问题,因此需要求解不同优化问题的solver。

本系列使用的编程语言以及solver如下:

  • 编程语言Julia:是一个由MIT学生开发的高性能动态编程语言,有很多包可以添加来扩充其功能。
  • 优化库JuMP:是Julia的一个包,用于建立优化问题。
  • solver:Jump支持很多开源与商业的solver,这些solver用于求解优化问题。常用的solver有COIN Clp, COIN Cbc, Gurobi等。

本系列大部分内容参考了下面课程,予以感谢:MITx: 15.053x Optimization Methods in Business Analytics。

线性化的必要性

求解线性问题要比求解非线性问题容易很多,因此将非线性的目标函数或者约束跳进进行线性化,有利于求解优化问题。 本文将介绍三种常见的非线性约束并探讨如何将其线性化。

非线性条件线性化

绝对值约束

绝对值约束将绝对值拆开即可。

|x1+x2–x3–x4|≤5{x1+x2–x3–x4≥−5x1+x2–x3–x4≤5

\begin{equation} |x1 +x2 –x3 –x4|≤5 \left\{\begin{aligned} x1 +x2 –x3 –x4 \ge -5\\ x1 +x2 –x3 –x4≤5 \end{aligned}\right. \end{equation}

最大最小约束

最大最小约束(或最小最大约束),可以将优化目标用一个自变量代替,然后补充满足条件的自变量的约束条件即可。

maxmin{50x1,25x2,20x3,15x4}⎧⎩⎨⎪⎪⎪⎪⎪⎪maxzz≤50x1z≤25x2z≤20x3z≤15x4

\begin{equation} \max \min \{50x_1, 25x_2, 20x_3, 15x_4\} \left\{\begin{aligned} \max z \\ z \le 50x_1 \\ z \le 25x_2 \\ z \le 20x_3 \\ z \le 15x_4 \end{aligned}\right. \end{equation}

比例约束

对于比例约束,只需要将两边同乘以分母即可,有以下两点需要注意:

  • 分母如果是负数,必须得变化符号。
  • 分母如果是0,那么新的约束同样满足条件,所以0的情况不用考虑。

x1(x1+x2+x3+x4)≥.2{.8x1−.2x2−.2x3−.2x4≥0

\begin{equation} \frac{x1}{(x1 +x2 +x3 +x4)} ≥ .2 \left\{\begin{aligned} .8x1 -.2x2 -.2x3 -.2x4 ≥0 \end{aligned}\right. \end{equation}

总结

大部分情况下,非线性的目标函数或者约束都不可以直接转化成线性,只有下面三种除外:

  • 绝对值约束
  • 最大最小约束
  • 比例约束

Julia优化例子

Knapsack

using JuMP, DataFrames
# Define model
m = Model()
# Define capacity
capacity = 11
# Read data from CSV file using readtable
data = readtable("knapsack_data.csv", header = false)
# Weights from first column, weights = [1 2 15 6 28]
weights = data[:,1]
# Values from second column, values = [1 6 18 22 7]
values = data[:,2]
# Assign binary values to items
@variable(m, x[1:5], Bin)
# Constraint on total weight
@constraint(m, sum{weights[i]*x[i], i in 1:5} <= capacity) 
# Maximize value from items
@objective(m, Max, sum{values[i]*x[i], i in 1:5})
# Solve model
solve(m)
# Determine which items to carry 
println("Variable Values: ", getvalue(x))
# Determine value from items carried
println("Objetive value: ", getobjectivevalue(m))

Diet

using JuMP
#Define model 
m = Model()
#Food available
S = ["brownies","ice cream","cola","cheese cake"]
#Non-negativity
@defVar(m, x[S] >= 0)
#Minimum calories
@addConstraint(m, 400x["brownies"] + 200x["ice cream"] + 150x["cola"] + 500x["cheese cake"] >= 500)
#At least 6 grams of chocolate
@addConstraint(m, 3x["brownies"] + 2x["ice cream"] >= 6)
#At least 10 grams of sugar
@addConstraint(m, 2x["brownies"] + 2x["ice cream"] + 4x["cola"] + 4x["cheese cake"] >= 10)
#At least 8 grams of fat
@addConstraint(m, 2x["brownies"] + 4x["ice cream"] + 1x["cola"] + 5x["cheese cake"] >= 8)
#Minimize cost of consumption
@setObjective(m, Min, 0.5x["brownies"] + 0.2x["ice cream"] + 0.3x["cola"] + 0.8x["cheese cake"])
#Solve the optimization problem
solve(m)
#Determine consumption amounts
println("variable values: ", getValue(x))
#Determine optimal cost of consumption
println("Objetive value: ", getObjectiveValue(m))

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏生信宝典

SOM基因表达聚类分析初探

上周的暑期生信黑马培训有老师提出要做SOM分析,最后卡在code plot只能出segment plot却出不来line plot。查了下,没看到解决方案。今天...

712
来自专栏云时之间

机器学习重要算法-PCA主成分分析

大家好,很高兴可以和大家一起来继续学习机器学习,这几天时间,我着重研究了下主成分分析法,不过因为其数学推理实在有些过于繁琐和复杂,我也没太搞得太清楚,如果在文章...

4679
来自专栏大数据文摘

有这5小段代码在手,轻松实现数据可视化(Python+Matplotlib)

2096
来自专栏算法channel

@all: 新浪 机器学习算法岗 面试实录

二面面试官来了。是个算法大佬。是个专门做算法的。直接手出题,他说时间不多,就让我说思路。

932
来自专栏机器学习和数学

[高大上的DL] Activation function (激活函数)的初步认识

今天简单认识一下什么激活函数以及都有那些激活函数。说到激活函数这里有几个比较容易混淆的概念,比如Pooling池化和Sampling采样,loss functi...

3188
来自专栏数据结构与算法

Day2上午解题报告

预计分数:100+0+60=160 实际分数:100+0+60=160 mmpT1数据错了。。。 T1遭遇 题目描述 你是能看到第一题的 friends呢。 —...

3864
来自专栏软件开发 -- 分享 互助 成长

经典算法学习之回溯法

回溯法的应用范围:只要能把待求解的问题分成不太多的步骤,每个步骤又只有不太多的选择就可以考虑使用回溯法。  若用回溯法求问题的所有解时,要回溯到根,且根结点的所...

2068
来自专栏红色石头的机器学习之路

Coursera吴恩达《神经网络与深度学习》课程笔记(3)-- 神经网络基础之Python与向量化

上节课我们主要介绍了逻辑回归,以输出概率的形式来处理二分类问题。我们介绍了逻辑回归的Cost function表达式,并使用梯度下降算法来计算最小化Cost f...

2480
来自专栏刘望舒

算法(一)时间复杂度

前言 算法很重要,但是一般情况下做移动开发并不经常用到,所以很多同学早就将算法打了个大礼包送还给了老师了,况且很多同学并没有学习过算法。这个系列就让对算法头疼的...

1758
来自专栏PPV课数据科学社区

【机器学习】确定最佳聚类数目的10种方法

在聚类分析的时候确定最佳聚类数目是一个很重要的问题,比如kmeans函数就要你提供聚类数目这个参数,总不能两眼一抹黑乱填一个吧。之前也被这个问题困扰过,看了很多...

2917

扫码关注云+社区