概述

对于约束优化问题我们可以用到的工具有Matlab，Lingo和Python的优化库，本次先了解下Matlab解决优化问题的方法。

Matlab优化工具箱

简介

我们先来了解下Matlab的优化工具箱(Optimization-Toolbox)。
查阅官网文档，2017b版本的Matlab优化工具箱支持的优化问题包括了线性优化，非线性优化，多目标优化，混合整数线性规划等问题，其中非线性优化中包含了有约束和无约束两种情况。
其中用于解决无约束非线性优化问题的算法有三种，为拟牛顿法，Nelder-Mead 算法和信赖域算法。原文的三种算法简介如下：

Optimization Toolbox 使用三种算法求解无约束非线性最小化问题：

拟牛顿算法使用二次和三次混合线搜索法并结合 Broyden-Fletcher-Goldfarb-Shanno (BFGS) 公式来更新海赛矩阵的近似值。

Nelder-Mead 算法（或下坡单纯形）是只使用函数值（不要求导数）的直接搜索算法，可用于处理非平滑目标函数。Global Optimization Toolbox 为非线性优化提供了更多的非求导优化算法。

信赖域算法用于无约束非线性问题，特别适用于有稀疏性或其他结构的大规模问题。

用于有约束非线性优化问题的算法包括内点法，SQP算法和信赖域反射算法，原文简介如下：

约束非线性优化问题由线性或非线性目标函数构成，并可能受到线性和非线性约束。Optimization Toolbox 使用三种算法求解这些问题：

内点算法用于常规非线性优化。它特别适用于具有稀疏性或其它结构的大规模问题，并且可容许用户自定义的目标和约束函数评估失败情形。它基于障碍函数，且在优化运行过程中可选择保持所有迭代对于边界严格可行。

SQP 算法用于常规非线性优化。它服从所有迭代的边界，并且容许用户定义的目标和约束函数评估失败情形。

信赖域反射算法仅用于限制约束问题或线性等式。它特别适用于大规模问题。

约束优化函数

由于本次学习的是约束优化问题，所以只列举与其相关的函数。
2017b版本提供的约束优化问题相关函数有3个，为fminbnd，fmincon和fseminf。fminbnd主要解决的单变量的优化问题，fmincon主要解决多变量非线性问题，而fseminf所控制的约束条件比前一个函数更丰富一些，官方介绍其功能的描述是：

Find minimum of semi-infinitely constrained multivariable nonlinear function

fminbnd

fminbnd函数的优化对象为如下目标函数：

$\min_{x} f(x)\ such\ that\ x_1<x<x_2$

使用方式为：

1	[x,fval,exitflag,output] = fminbnd(fun,x1,x2,options)

使用第二个和第三个参数约束变量的取值范围。第四个参数为一下优化选项，包括允许的最大迭代次数。函数最大值等一般使用的时候选择默认值即可。

fmincon

fmincon函数的优化对象如下：

$\min_{x} f(x)\ such\ that\ \begin{cases} c(x)\leqslant0 \\cep(x)=0 \\A*x\leqslant b \\Aep*x= Bep \\lb\leqslant x\leqslant ub \end{cases}$

使用方法为：

1	[x,fval,exitflag,output,lambda,grad,hessian] = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)

第一个输入参数为目标函数，第二个输入参数为迭代的初始点，其他输入参数的含义对应上述公式的约束条件。输出的exitflag表示了迭代停止的条件，每个整数对应了一种情况，例如输出为”-2”时表示无可行点；输出的output为显示优化的过程信息，例如迭代的次数等信息。

fseminf

fseminf函数优化的对象为

$\min_{x} f(x)\ such\ that\ \begin{cases} A*x\leqslant b \\Aep*x= Bep \\lb\leqslant x\leqslant ub \\c(x)\leqslant0 \\cep(x)=0 \\K_i(x,w_i)\leqslant 0,1\leqslant i\leqslant n \end{cases}$

可以发现其约束条件比fmincon多了一种非线性的优化条件。使用方法如下：

1	[x,fval,exitflag,output,lambda]= fseminf(fun,x0,ntheta,seminfcon,A,b,Aeq,beq,lb,ub,options)

其输入参数对应上述约束条件的名称，各项输出意义与上一函数同。

示例

列举一个fmincon函数的示例。
其目标函数为：

$f(x)=100(x_2-x_1^2)^2+(1-x_1)^2$

约束条件为：

$\begin{cases} 0\leqslant x_1 \leqslant 0.5 \\0.2\leqslant x_2 \leqslant 0.8 \\(x_1-1/3)^2 + (x_2-1/3)^2 - (1/3)^2 \end{cases}$

可以发现约束条件描述可行域的是一个圆中的一部分，即为一个圆弧。代码实现如下：

% test.m
fun = @(x)100*(x(2)-x(1)^2)^2 + (1-x(1))^2;
lb = [0,0.2];
ub = [0.5,0.8];
A = [];
b = [];
Aeq = [];
beq = [];
x0 = [1/4,1/4];
nonlcon = @circlecon;
[x,fval,exitflag,output]  = fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)

以及

% circlecon.m
function [c,ceq] = circlecon(x)
c = (x(1)-1/3)^2 + (x(2)-1/3)^2 - (1/3)^2;
ceq = [];

输出结果如下：

x =
    0.5000    0.2500
fval =
    0.2500
exitflag =
     1
output = 
         iterations: 17
          funcCount: 55
    constrviolation: 0
           stepsize: 2.1339e-06
          algorithm: 'interior-point'
      firstorderopt: 1.6050e-08
       cgiterations: 0
            message: 'Local minimum found that satisfies the constraints.…'

小结

相比lingo主要解决线性规划问题而言，Matlab的优化工具箱功能更加的全面，但是其在计算之前需要把相关的约束条件转变为矩阵形式，严格按照函数的参数格式进行优化。但是Lingo的语法描述会更简单一些，所以在解决线性规范问题的时候我觉得Lingo更方便一些，但是在非线性约束的时候，Matlab的优化工具箱函数很实用的。
函数相关参数更详细的介绍可以参考官方文档。