非线性最优化问题求解器Ipopt介绍

Ipopt(Interior Point OPTimizer)是求解大规模非线性最优化问题的求解库。可以求解如下形式的最优化问题的(局部)最优解。

其中，f ( x ) : R n → R f(x):R^n → Rf(x):Rn→R是优化目标函数，g ( x ) : R n → R m g(x):R^n → R^mg(x):Rn→Rm是约束函数，f ( x ) , g ( x ) f(x),g(x)f(x),g(x)可以是非线性和非凸的，但是需要二阶微分连续。

一、关键输入信息

为了求解最优化问题，Ipopt需要更多信息，如下：

1、优化问题的维度

1）优化变量x xx的数目；

2）约束函数g ( x ) g(x)g(x)的数目;

2、优化变量的边界

1）优化变量x xx的边界；

2）约束函数g ( x ) g(x)g(x)的边界；

3、优化问题的初始迭代点：

1）优化变量x xx的初始值；

2）拉格朗日乘子的初始值(仅仅是在warm start的时候需要)；

4、优化问题的数据结构(Structure)：

1）约束函数g ( x ) g(x)g(x)的雅可比矩阵的非零元素的数目；
2）拉格朗日函数的海森矩阵的非零元素的数目；
3）约束函数g ( x ) g(x)g(x)​ 的雅可比稀疏矩阵的非零元素的行索引和列索引(sparsity structure，row and column indices of each of the nonzero entries)；
4）拉格朗日函数的海森稀疏矩阵的非零元素的行索引和列索引(sparsity structure，row and column indices of each of the nonzero entries)；

5、优化问题函数的值：

1）优化目标函数f ( x ) f(x)f(x)

2）优化目标函数的梯度函数c cc

3）约束函数g ( x ) g(x)g(x)​

4）约束函数的雅可比矩阵∇ g ( x ) T ∇g(x)^T∇g(x)T

5）拉格朗日函数的海森矩阵σ f ∇ 2 f ( x ) + ∑ i = 1 m λ i ∇ 2 g i ( x ) \sigma_f∇^2f(x) + \sum_{i=1}^{m}\lambda_i∇^2g_i(x)σf​∇2f(x)+∑i=1m​λi​∇2gi​(x)​，如果使用拟牛顿法则不需要此矩阵

---

优化问题的维度和边界约束可以直接获得，并且来自于问题定义。

初始迭代点会影响优化问题的是否收敛或者是否收敛到(局部)最优解，不同的初始值可能会导致收敛到不同的局部最优解。

计算微分矩阵(雅可比矩阵和海森矩阵)可能有一点复杂，Ipopt需要提供约束函数的雅可比矩阵和拉格朗日函数的海森矩阵的非零元素以及他们所在的行索引和列索引，并且标准接口是下三角矩阵(海森矩阵是对称矩阵)。矩阵的非零元素确定后，在整个求解过程中是不可变的，因此，非零元素不可以仅仅包含在初始值条件下，还需要包括在求解过程中不为零的元素。

二、C++ Interface

需要继承纯虚基类Ipopt::TNLP来编写自己的求解类，并且需要重载9个Ipopt::TNLP基类的虚函数，Ipopt通过Ipopt::IpoptApplication类来求解最优化问题。

1、Ipopt::TNLP::get_nlp_info

virtual bool get_nlp_info( Index& n, Index& m, Index& nnz_jac_g, Index& nnz_h_lag, IndexStyleEnum& index_style ) = 0;

Ipopt使用这个函数来确定数组的内存分配，这里如果发生问题，会引起内存泄漏等问题，很难去debug。

• n：优化变量x xx的数目；
• m：约束函数g ( x ) g(x)g(x)的数目；
• nnz_jac_g：雅可比矩阵非零元素的数目；
• nnz_h_lag：海森矩阵非零元素的数目；
• index_style：稀疏矩阵的索引使用C语言风格(从0开始），还是使用Fortran语言风格(从1开始)；

2、Ipopt::TNLP::get_bounds_info

virtual bool get_bounds_info( Index n, Number* x_l, Number* x_u, Index m, Number* g_l, Number* g_u ) = 0;

Ipopt使用这个函数来确定优化变量x xx的边界和约束函数g ( x ) g(x)g(x)的边界。

• n：优化变量x xx的数目；
• x_l：优化变量x xx的下边界，数组；
• x_u：优化变量x xx的上边界，数组；
• m：约束函数g ( x ) g(x)g(x)的数目；
• g_l：约束函数g ( x ) g(x)g(x)的下边界，数组；
• g_u：约束函数g ( x ) g(x)g(x)的上边界，数组；

在Ipopt中默认设置边界值需要在( − 1 0 9 , 1 0 9 ) (-10^9, 10^9)(−109,109)范围内，当不在此范围时，则认为是无穷大或者无穷小。

3、Ipopt::TNLP::get_starting_point

virtual bool get_starting_point( Index n, bool init_x, Number* x, bool init_z, Number* z_L, Number* z_U, Index m, bool init_lambda, Number* lambda ) = 0;

Ipopt使用这个函数来确定迭代优化的起点。

• n：优化变量x xx的数目；
• init_x：如果是true，则需要提供优化变量x xx的初始值；
• x：优化变量x xx的初始值；

其他为dual variables的初始值，一般不用设置。在Ipopt中默认是需要设置x xx的初始值。

4、Ipopt::TNLP::eval_f

virtual bool eval_f( Index n, const Number* x, bool new_x, Number& obj_value ) = 0;

Ipopt使用这个函数来确定优化目标函数。

• n：优化变量x xx的数目；
• x：优化变量x xx的值，用来计算f ( x ) f(x)f(x)；
• new_x：在此之前调用的eval_*函数是否有错误发生，可以忽略；
• obj_value：f ( x ) f(x)f(x)；

5、Ipopt::TNLP::eval_grad_f

virtual bool eval_grad_f( Index n, const Number* x, bool new_x, Number* grad_f ) = 0;

Ipopt使用这个函数来确定优化目标函数的梯度。

• n：优化变量x xx的数目；
• x：优化变量x xx的值，用来计算∇ f ( x ) ∇f(x)∇f(x)；
• new_x：在此之前调用的eval_*函数是否有错误发生，可以忽略；
• grad_f：∇ f ( x ) ∇f(x)∇f(x)，数组的大小和x xx的数组大小一致；

6、Ipopt::TNLP::eval_g

virtual bool eval_g( Index n, const Number* x, bool new_x, Index m, Number* g ) = 0;

Ipopt使用这个函数来确定约束函数g ( x ) g(x)g(x)。

• n：优化变量x xx的数目；
• x：优化变量x xx的值，用来计算∇ f ( x ) ∇f(x)∇f(x)；
• new_x：在此之前调用的eval_*函数是否有错误发生，可以忽略；
• m： 约束函数g ( x ) g(x)g(x)的数目；
• g：g(x)，数组的大小和m一致；

7、Ipopt::TNLP::eval_jac_g

virtual bool eval_jac_g( Index n, const Number* x, bool new_x, Index m, Index nele_jac, Index* iRow, Index* jCol, Number* values ) = 0;

Ipopt使用这个函数来确定约束函数g ( x ) g(x)g(x)的雅可比矩阵的非零元素的值，以及其在稀疏矩阵中的行索引值和列索引值。雅可比矩阵中的第i ii行和第j列的元素值是g i ( x ) g_i(x)gi​(x)对x j x_jxj​的导数。

• n：优化变量x xx的数目；
• x：优化变量x xx的值，用来计算∇ g ( x ) T ∇g(x)^T∇g(x)T；
• new_x：在此之前调用的eval_*函数是否有错误发生，可以忽略；
• m：约束函数g ( x ) g(x)g(x)的数目；
• iRow：存储雅可比矩阵非零元素在矩阵中的行索引值，如果是C语言风格，雅可比矩阵索引值从0开始；
• jCol：存储雅可比矩阵非零元素在矩阵中的列索引值，如果是C语言风格，雅可比矩阵索引值从0开始；
• values：存储雅可比矩阵中的非零元素；

需要注意的是：①iRow、jCol和values三个数组的大小是一致的，并且其储存的值应该和雅可比矩阵非零元素的行索引值、列索引值和非零元素值相对应；②数组iRow和jCol只需要被填写一次，即第一次调用此函数时填写iRow和jCol，第一次调用时x和values都是null，当Ipopt需要values的值时，传递iRow和jCol将会是null，此时对values的值进行填写。

8、Ipopt::TNLP::eval_h

virtual bool eval_h( Index n, const Number* x, bool new_x, Number obj_factor, Index m, const Number* lambda, bool new_lambda, Index nele_hess, Index* iRow, Index* jCol, Number* values )

Ipopt使用这个函数来确定拉格朗日函数海森矩阵的非零元素的值，以及其在稀疏矩阵中的行索引值和列索引值。

• n：优化变量x xx的数目；
• x：优化变量x xx的值，用来计算∇ g ( x ) T ∇g(x)^T∇g(x)T；
• new_x：在此之前调用的eval_*函数是否有错误发生，可以忽略；
• obj_factor：σ f \sigma_fσf​
• m：约束函数g ( x ) g(x)g(x)​ 的数目；
• lambda：拉格朗日乘子λ \lambdaλ；
• new_lambda：如果之前调用的函数使用相同的λ \lambdaλ则为false，一般忽略；
• nele_hess：海森矩阵非零元素的个数(下三角矩阵)；
• iRow：存储海森矩阵非零元素在矩阵中的行索引值，如果是C语言风格，雅可比矩阵索引值从0开始；
• jCol：存储海森矩阵非零元素在矩阵中的列索引值，如果是C语言风格，雅可比矩阵索引值从0开始；
• values：存储海森矩阵中的非零元素；

需要注意的是：①iRow、jCol和values三个数组的大小是一致的，并且其储存的值应该和海森矩阵非零元素的行索引值、列索引值和非零元素值相对应；②数组iRow和jCol只需要被填写一次，即第一次调用此函数时填写iRow和jCol，第一次调用时x、lambda和values都是null，当Ipopt需要values的值时，传递iRow和jCol将会是null，此时对values的值进行填写；③由于海森矩阵是对称阵，Ipopt使用下三角矩阵；④Ipopt默认是需要海森矩阵的，当使用拟牛顿法时，则不需要海森矩阵。

9、Ipopt::TNLP::finalize_solution

virtual void finalize_solution( SolverReturn status, Index n, const Number* x, const Number* z_L, const Number* z_U, Index m, const Number* g, const Number* lambda, Number obj_value, const IpoptData* ip_data, IpoptCalculatedQuantities* ip_cq ) = 0;

Ipopt使用这个函数来得到最优化问题的求解结果，对其重要的值进行介绍。

• status：求解器的状态；
  • SUCCESS：在满足收敛条件的情况下，找到局部最优解；
  • MAXITER_EXCEEDED：超出最大迭代次数；
  • CPUTIME_EXCEEDED：超出最大求解时间；
  • STOP_AT_ACCEPTABLE_POINT：求解收敛在某点，不满足期望的容差，但是在可接受范围内；
  • LOCAL_INFEASIBILITY：在可行域内找不到最优解，一般是由于bounds和约束设置不合理导致的；
• x：优化变量x xx的局部最优解的值；