优化问题涉及关键词：

凸优化、凸锥、凸集、线性规划、非线性规划（np）、拉格朗日chengzi、hessian矩阵、泰勒展开式、梯度、方向导数、牛顿法、凸二次优化、局部最小化、随机梯度、最速梯度、批量梯度、kkt条件、等高线 、共轭梯度、二次型、二次型矩阵、对偶问题


一，前置条件：需要补充一下知识，才开启下面内容：
方向导数 与 梯度的概念
线性规划
hession矩阵
泰勒展开式
共轭
————————————————————————————————————————————————

二，凸集：

http://www.hanlongfei.com/%E5%87%B8%E4%BC%98%E5%8C%96/2015/05/22/convexset/



————————————————————————————————————————————————


三，线性规划求解：


可以转化为线性规划对偶方式：http://blog.csdn.net/chunyun0716/article/details/52423991


求解：

无约束求解：导数、求极值

有约束求解：

1，图解法——最为简单直观，不需要转化为标准型

2，单纯形表法：

    a，需要转化为标准型：min到max，将不等式变为等式：增加松弛变量

    b，找出所有基解，判断是否是基础可行解，并比较求出最大的那个


————————————————————————————————————————————————

四，非线性规划内的凸优化求解：


也可以转化为对偶方法：http://blog.csdn.net/chunyun0716/article/details/52423991


1，无约束：（无论是否是凸函数、还是非凸函数均可使用）

原理：需要先理解方向导数、梯度概念；

方法：

最速梯度下降（需要方向导数、梯度知识、偏导数原理），

牛顿法（泰勒展开式知识、需要hession矩阵、偏导数原理、对称矩阵、二次型），

随机梯度（由最速梯度衍生），

批量梯度（由最速梯度衍生），

共轭梯度（由最速梯度衍生、共轭概念、共轭矩阵）


2，等式约束（限凸函数）：拉格朗日乘子（需要等高线、法向量知识）将等式有约束变为无约束，之后使用无约束方法求解，拉格朗日乘子原理请查看：https://www.zhihu.com/question/38586401。


3，不等式约束（需要满足kkt条件）：kkt条件（广义拉格朗日乘子），原理：https://www.zhihu.com/question/23311674，如果求解困难，可考虑转化为拉格朗日对偶，之后通过无约束方法求解。


4，对于有约束的优化问题，通过拉格朗日法可以将其转变为等价的无约束优化问题。在这个过程中，新构造的拉格朗日函数存在好玩的对偶性质，从而衍生出了对偶问题。原问题与对偶问题之间的特殊性质，为我们


研究优化问题提供了新的方向和方法。因此，这部分的思路是：对4.1定义的优化问题，通过拉格朗日法构造拉格朗日函数，从而生成原问题Primal problem和对偶问题Dual problem，然后介绍一些引理，揭示原问题


与对偶问题之间的关系。拉格朗日对偶问题，详情查看：https://www.cnblogs.com/90zeng/p/Lagrange_duality.html

————————————————————————————————————————————————


五，凸优化：

凸优化包含：线性规划 与 目标函数与条件函数都是凸函数的 非线性规划。

详情查看：https://www.zhihu.com/question/24641575/answer/164397294


凸优化特性：

a，局部最优解=全局最优解

b，效率高

c，是目前科技比较确定的可以求解的非线性规划方式，

d，许多非凸问题通过一定的手段，要么等价地化归为凸问题，要么用凸问题去近似、逼近。典型的如几何规划、整数规划，它们本身是非凸的，但是可以借助凸优化手段去解，这就极大地扩张了凸优化的应用范围。

e，在非凸优化中，凸优化同样起到很重要的作用    1）当你要解决一个非凸优化问题时，可以先试图建立一个简化多凸优化模型，解出来以后作为非凸问题的一个起始点。    2）很多非凸优化问题的启发式算法的基础都是基于凸优化    3）你可以先建立非凸优化的松弛问题，使用凸优化算法求解，作为非凸优化问题的上限或下限（bound）



求解凸函数的极小值（convex minimization）和凹函数的极大值（concave maximization）都是凸优化问题（convex optimization problem）。


凸优化之所以‘容易’是因为任何可证明的局部最优解（Local Optimal Solution）都同时为全局最优解（Global Optimal Solution）。


凸优化理论中最重要的工具是Lagrange对偶。近些年来关于凸问题的研究非常透彻，以至于只要把某一问题抽象为凸问题，就可以近似认为这个问题已经解决了。


————————————————————————————————————————————————
六，关于非凸非线性规划求解：
解决一个非凸优化问题时，可以先试图建立一个简化的多凸优化模型，解出以后作为非凸问题的一个起始点，很多非凸优化问题的启发式算法的基础都是基于凸优化，可以先建立非凸


优化的松弛问题，使用凸优化算法求解，然后作为非凸优化问题的上限或下限


a，先松弛，例如，某问题有一约束为 x^2+bx+c=0 ，就不构成一个凸集，但等价于 x^2+bx+c<= 0 和 x^2+bx+c>= 0 ，前一个不等式即构成凸集，因此我们可以将后一个不等式从约束中去除，就得到原问题的一个凸


优化松弛问题。

b，利用广义拉格朗日乘子 以及 拉格朗日对偶简化，

c，通过凸优化的无约束条件规划求解。

相关函数：linprog()函数

函数功能：

    用于寻找目标函数的最小值（如果求最大值需做相应变化）

注意事项：


	
1.目标函数f要写成列矩阵的形式
	
	

	
2.约束要写成 <= 的形式
	
	

	
3.函数是为求最小值设置的
	
 

参数解释：

    参数1：所求目标函数未知数的系数                                           {一维数组}

    参数2 ：A_up，此参数为不等式包含未知数一侧  未知数的系数  { 二维数组}

    参数3：B_up，此参数为不等式不包含未知数一侧  的数值         {一维数组}

    参数4：A_eq，此参数为等式 包含未知数一侧   未知数的系数    {二维数组}

    参数5：B_eq ，此参数为等式 不包含未知数一侧  的数值             {一维数组}

    参数6：每个系数的限制

样例：

  

import numpy as np
from scipy import optimize as op
np.set_printoptions(suppress=True)
z = np.array([4, 3])
A_ub = np.array([[2, 1], [1, 1]])
B_ub = np.array([10, 8])
x1 = (0, 8)
x2 = (0, 7)
res = op.linprog(-z, A_ub, B_ub, bounds = (x1,x2))#由于求解最大值，所以此处为-z，答案就是相反数
print(res)

结果：

***Repl Closed***
     con: array([], dtype=float64)
     fun: -25.9999999991197               # 最终结果
 message: 'Optimization terminated successfully.'
     nit: 5
   slack: array([0., 0.])
  status: 0
 success: True
       x: array([2., 6.])               #x1和x2的值

***Repl Closed***

样例2：



要点：

不等式1为  大于等于，应该转换为小于等于：   -2X1 + 5X2 - X3 <= -10

import numpy as np
from scipy import optimize as op
np.set_printoptions(suppress=True)
z = np.array([2, 3, -5])
A_up = np.array([[-2, 5, -1], [1, 3, 1]])
B_up = np.array([-10, 12])
A_eq = np.array([1, 1, 1])
B_eq = np.array([7])
x1 = (0, 7)
x2 = (0, 7)
x3 = (0, 7)
res = op.linprog(-z, A_up, B_up, A_eq, B_eq, bounds=(x1, x2, x3))
print(res)

运行结果：

***Repl Closed***
     con: array([], dtype=float64)
     fun: -14.571428509517212                  #相反数即为所求最大值
 message: 'Optimization terminated successfully.'
     nit: 5
   slack: array([0.00000022, 3.85714293, 0.00000001])
  status: 0
 success: True
       x: array([6.42857145, 0.57142854, 0.        ])

***Repl Closed***

 

求大佬帮忙弄个程序

1.将11个点走完，求最短路程




2.时间的条件约束下求

目的：学会用matlab、lingo软件求解线性规划问题。

二、实验要求：

1.熟悉线性规划问题的数学建模；

2.会用matlab、

lingo软件求解线性规划问题；

3.掌握线性规划的灵敏度分析。

三、实验内容：

1、求解下列线性规划问题：

(1) 给出lingo原始代码；

(2) 计算结果(包括灵敏度分析，求解结果粘贴)；

(3) 回答下列问题：a) 最优解及最优目标函数值是多少；

b) 资源的对偶价格各为多少，并说明对偶价格的含义；

c) 为了使目标函数值增加最多，让你选择一个约束条件，将它的常数项增加一个单位，你将选择哪一个约束条件？这时目标函数值将是多少？

d) 对x2的目标函数系数进行灵敏度分析；e) 对第2个约束的约束右端项进行灵敏度分析；f) 结合本题的结果解释“Reduced Cost”的含义

2、 请写出调用函数linporg求解下述问题的matlab源代码，求解结果粘贴，并对结果分析。

（1）：matlab代码
f=[3;2;1];

A=[1 1 1;-1 0 1;0 -1 1];

b=[6;-4;-3];

lb=[0;0;0];

[x,z]=linprog(f,A,b,[],[],lb,[])
运行结果如下：
Linprog stopped because

no point satisfies the constraints.
（2）：matlab代码
f=[-2;-2];

A=[-1 1;-0.5 1];

b=[1;2];

lb=[0;0];

[x,z]=linprog(f,A,b,[],[],lb,[])
运行结果如下：
Problem is unbounded.

（3）：matlab代码
f=[1;-2];

A=[-1 -1;1 -1;0 1];

b=[-2;-1;3];

lb=[0;0];

[x,z]=linprog(f,A,b,[],[],lb,[])
运行结果如下：
Optimal solution found.
x =

0

3

z =

-6

（4）：matlab代码
f=[-1;-2;0;0;0];

Aeq=[1 0 1 0 0;0 1 0 1 0;1

2 0 0 1];

beq=[4;3;8];

lb=[0;0;0;0;0];

[x,z]=linprog(f,[],[],Aeq,beq,lb,[])
运行结果如下：
Optimal solution found.

x =

4.0000

2.0000

0

1.0000

0

z =

-8
3、（任务分配问题）某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。

生产的工件3的件数为 （件），设乙生产的工件1的件数为（件），生产的工件2的件数为 （件），生产的工件3的件数为（件），设加工费用为W（元）。
   则线性规划如下：

   Min W=13+9+10+11+12+8

(2)试选一数学软件计算上述模型，并给出程序源代码和计算结果报告。
解：matlab代码：
f=[13 9 10 11 12 8];

A=[0.4 1.1 1 0 0 0;0 0 0 0.5 1.2 1.3];

b=[800 900];

Aeq=[1 0 0 1 0 0;0 1 0 0 1 0;0 0 1 0 0 1];

beq=[400 600 500];

LB=[0 0 0 0 0 0];

[x,fval,exitflag]=linprog(f,A,b,Aeq,beq,LB)
运行结果：
Optimization

terminated.
x =

0.0000

600.0000

0.0000

400.0000

0.0000

500.0000

val =.3800e+04];

b=[800 900];

Aeq=[1 0 0 1 0 0;0 1 0 0 1 0;0 0 1 0 0 1];

beq=[400 600 500];

LB=[0 0 0 0 0 0];

[x,fval,exitflag]=linprog(f,A,b,Aeq,beq,LB)
运行结果：

Optimization

terminated.
x =    0.0000

600.0000

0.0000

400.0000

0.0000

500.0000
val =

1.3800e+04

1
由运行结果得，此线性规划有最优值13800（元），满足最优解的=0，=600，=0，=400，=0，=500，即在甲机床上加工的工件2为600件，不加工的工件1和工件2，在乙机床上加工的工件1为400件，加工的工件3为500件，且不加工工件2时，其加工费用最低，为13800元。