2. Optimization Solvers

In OPTALG, optimization solvers are objects of type OptSolver, and optimization problems are objects of type OptProblem and represent general problems of the form

\begin{alignat*}{3} & \mbox{minimize} \quad && \varphi(x) \ && \\ & \mbox{subject to} \quad && Ax = b \ && : \lambda \\ & \quad && f(x) = 0 \ && : \nu \\ & \quad && l \le x \le u \ && : \pi, \mu \\ & \quad && Px \in \{0,1\}^m,\ && \end{alignat*}

where \(P\) is a matrix that extracts a sub-vector of \(x\).

Before solving a problem with a specific solver, the solver parameters can be configured using the method set_parameters(). Then, the solve() method can be invoked with the problem to be solved as its argument. The status, optimal primal variables, and optimal dual variables can be extracted using the class methods get_status(), get_primal_variables(), and get_dual_variables(), respectively.

2.1. NR

This solver, which corresponds to the class OptSolverNR, solves problems of the form

\begin{alignat*}{2} & \mbox{find} \quad && x \\ & \mbox{subject to} \quad && Ax = b \\ & \quad && f(x) = 0 \end{alignat*}

using the Newton-Raphson algorithm. It requires the number of variables to be equal to the number of constraints.

2.2. Clp

This is a wrapper of the solver Clp from COIN-OR. It corresponds to the class OptSolverClp, and solves problems of the form

\begin{alignat*}{3} & \mbox{minimize} \quad && c^Tx \ && \\ & \mbox{subject to} \quad && Ax = b \ && : \lambda \\ & \quad && l \le x \le u \ && : \pi, \mu. \end{alignat*}

Linear optimization problems solved with this solver must be instances of the class LinProblem, which is a subclass of OptProblem.

2.3. Cbc

This is a wrapper of the solver Cbc from COIN-OR. It corresponds to the class OptSolverCbc, and solves problems of the form

\begin{alignat*}{3} & \mbox{minimize} \quad && c^Tx \\ & \mbox{subject to} \quad && Ax = b \\ & \quad && l \le x \le u \\ & \quad && Px \in \{0,1\}^m. \end{alignat*}

Mixed-integer linear optimization problems solved with this solver must be instances of the class MixIntLinProblem, which is a subclass of OptProblem.

2.4. IQP

This solver, which corresponds to the class OptSolverIQP, solves convex quadratic problems of the form

\begin{alignat*}{3} & \mbox{minimize} \quad && \frac{1}{2}x^THx + g^Tx \ && \\ & \mbox{subject to} \quad && Ax = b \ && : \lambda \\ & \quad && l \le x \le u \ && : \pi, \mu \end{alignat*}

using a primal-dual interior-point algorithm. Quadratic problems solved with this solver must be instances of the class QuadProblem, which is a subclass of OptProblem. The following example shows how to solve the quadratic problem

\begin{alignat*}{2} & \mbox{minimize} \quad && 3x_1-6x_2 + 5x_1^2 - 2x_1x_2 + 5x_2^2 \\ & \mbox{subject to} \quad && x_1 + x_2 = 1 \\ & \quad && 0.2 \le x_1 \le 0.8 \\ & \quad && 0.2 \le x_2 \le 0.8 \end{alignat*}

using OptSolverIQP:

>>> import numpy as np
>>> from optalg.opt_solver import OptSolverIQP, QuadProblem

>>> g = np.array([3.,-6.])
>>> H = np.array([[10.,-2],
...               [-2.,10]])

>>> A = np.array([[1.,1.]])
>>> b = np.array([1.])

>>> u = np.array([0.8,0.8])
>>> l = np.array([0.2,0.2])

>>> problem = QuadProblem(H,g,A,b,l,u)

>>> solver = OptSolverIQP()

>>> solver.set_parameters({'quiet': True,
...                        'tol': 1e-6})

>>> solver.solve(problem)

>>> print solver.get_status()
solved

Then, the optimal primal and dual variables can be extracted, and feasibility and optimality can be checked as follows:

>>> x = solver.get_primal_variables()
>>> lam,nu,mu,pi = solver.get_dual_variables()

>>> print x
[ 0.20  0.80 ]

>>> print x[0] + x[1]
1.00

>>> print l <= x
[ True  True ]

>>> print x <= u
[ True  True ]

>>> print pi
[ 9.00e-01  1.80e-06 ]

>>> print mu
[ 1.80e-06  9.00e-01 ]

>>> print np.linalg.norm(g+np.dot(H,x)-np.dot(A.T,lam)+mu-pi)
1.25e-15

>>> print np.dot(mu,u-x)
2.16e-06

>>> print np.dot(pi,x-l)
2.16e-06

2.5. INLP

This solver, which corresponds to the class OptSolverINLP, solves general nonlinear optimization problems of the form

\begin{alignat*}{3} & \mbox{minimize} \quad && \varphi(x) \ && \\ & \mbox{subject to} \quad && Ax = b \ && : \lambda \\ & \quad && f(x) = 0 \ && : \nu \\ & \quad && l \le x \le u \ && : \pi, \mu \end{alignat*}

using a primal-dual interior-point algorithm. It computes Newton steps for solving modified KKT conditions and does not have any global convergence guarantees.

2.6. AugL

This solver, which corresponds to the class OptSolverAugL, solves optimization problems of the form

\begin{alignat*}{3} & \mbox{minimize} \quad && \varphi(x) \ && \\ & \mbox{subject to} \quad && Ax = b \ && : \lambda \\ & \quad && f(x) = 0 \ && : \nu \\ & \quad && l \le x \le u \ && : \pi, \mu \end{alignat*}

using an Augmented Lagrangian algorithm. It requires the objective function \(\varphi\) to be convex.

2.7. Ipopt

This is a wrapper of the solver IPOPT from COIN-OR. It corresponds to the class OptSolverIpopt, and solves optimization problems of the form

\begin{alignat*}{3} & \mbox{minimize} \quad && \varphi(x) \ && \\ & \mbox{subject to} \quad && Ax = b \ && : \lambda \\ & \quad && f(x) = 0 \ && : \nu \\ & \quad && l \le x \le u \ && : \pi, \mu. \end{alignat*}