OPTALG Documentation¶
Welcome! This is the documentation for OPTALG version 1.1.7, last updated Nov 30, 2019.
What is OPTALG?
OPTALG is a Python package that provides algorithms, wrappers, and tools for solving large and sparse optimization problems.
License
OPTALG is released under the BSD 2-clause license.
Contents
Getting Started¶
This section describes how to get started with OPTALG.
Installation¶
In order to install OPTALG, the following tools are needed:
- Linux and Mac OS X:
- Windows:
After getting these tools, the OPTALG Python module can be installed using:
pip install numpy cython
pip install optalg
By default, no wrappers are built for any external solvers. If the environment variable OPTALG_IPOPT has the value true during the installation, OPTALG will download and build the solver IPOPT for you, and then build its Python wrapper. Similarly, if the environment variables OPTALG_CLP amd OPTALG_CBC have the value true during the installation, OPTLAG will download and build the solvers Clp and Cbc for you, and then build their Python wrappers.
To install the module from source, the code can be obtained from https://github.com/ttinoco/OPTALG, and then the following commands can be executed on the terminal or Anaconda prompt from the root directory of the package:
pip install numpy cython
python setup.py install
Running the unit tests can be done with:
pip install nose
python setup.py build_ext --inplace
nosetests -s -v
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
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.
NR¶
This solver, which corresponds to the class OptSolverNR, solves problems of the form
using the Newton-Raphson algorithm. It requires the number of variables to be equal to the number of constraints.
Clp¶
This is a wrapper of the solver Clp from COIN-OR. It corresponds to the class OptSolverClp, and solves problems of the form
Linear optimization problems solved with this solver must be instances of the class LinProblem, which is a subclass of OptProblem.
Cbc¶
This is a wrapper of the solver Cbc from COIN-OR. It corresponds to the class OptSolverCbc, and solves problems of the form
Mixed-integer linear optimization problems solved with this solver must be instances of the class MixIntLinProblem, which is a subclass of OptProblem.
IQP¶
This solver, which corresponds to the class OptSolverIQP, solves convex quadratic problems of the form
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
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
INLP¶
This solver, which corresponds to the class OptSolverINLP, solves general nonlinear optimization problems of the form
using a primal-dual interior-point algorithm. It computes Newton steps for solving modified KKT conditions and does not have any global convergence guarantees.
AugL¶
This solver, which corresponds to the class OptSolverAugL, solves optimization problems of the form
using an Augmented Lagrangian algorithm. It requires the objective function \(\varphi\) to be convex.
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
API Reference¶
Linear Solvers¶
-
optalg.lin_solver.new_linsolver(name, prop)[source]¶ Creates a linear solver.
Parameters: - name : string
- prop : string
Returns: - solver :
LinSolver
-
class
optalg.lin_solver.lin_solver.LinSolver(prop='unsymmetric')[source]¶ Linear solver class.
Parameters: - prop : {
symmetric,unsymmetric}
-
analyzed= None¶ Flag that specifies whether the matrix has been analyzed.
-
is_analyzed(self)[source]¶ Determine whether the matrix has been analyzed.
Returns: - flags : {
True,False}
- flags : {
-
name= None¶ Name (string)
-
prop= None¶ Linear system property {
'symmetric','unsymmetric'}.
- prop : {
-
class
optalg.lin_solver.mumps.LinSolverMUMPS(prop='unsymmetric')[source]¶ Linear solver based on MUMPS.
Optimization Problems¶
-
class
optalg.opt_solver.problem.OptProblem[source]¶ Class for representing general optimization problems.
Parameters: - problem : Object
-
A= None¶ Matrix for linear equality constraints
-
H_combined= None¶ Linear combination of Hessians of nonlinear constraints
-
Hphi= None¶ Objective function Hessian (lower triangular)
-
J= None¶ Jacobian of nonlinear constraints
-
P= None¶ Integer flags (boolean array)
-
b= None¶ Right-hand side for linear equality constraints
-
combine_H(self, coeff, ensure_psd=False)[source]¶ Forms and saves a linear combination of the individual constraint Hessians.
Parameters: - coeff : vector
- ensure_psd : {
True,``False``}
-
eval(self, x)[source]¶ Evaluates the objective value and constraints at the give point.
Parameters: - x : vector
-
f= None¶ Nonlinear equality constraint function
-
get_num_linear_equality_constraints(self)[source]¶ Gets number of linear equality constraints.
Returns: - num : int
-
get_num_nonlinear_equality_constraints(self)[source]¶ Gets number of nonlinear equality constraints.
Returns: - num : int
-
gphi= None¶ Objective function gradient
-
l= None¶ Lower limits
-
lam= None¶ Lagrande multipliers for linear equality constraints
-
mu= None¶ Lagrande multipliers for upper limits
-
nu= None¶ Lagrande multipliers for nonlinear equality constraints
-
phi= None¶ Objective function value
-
pi= None¶ Lagrande multipliers for lower limits
-
recover_dual_variables(self, lam, nu, mu, pi)[source]¶ Recovers dual variables for original problem.
Parameters: - lam : ndarray
- nu : ndarray
- mu : ndarray
- pi : ndarray
-
recover_primal_variables(self, x)[source]¶ Recovers primal variables for original problem.
Parameters: - x : ndarray
-
u= None¶ Upper limits
-
wrapped_problem= None¶ Wrapped problem
-
x= None¶ Initial point
-
class
optalg.opt_solver.problem_lin.LinProblem(c, A, b, l, u, x=None, lam=None, mu=None, pi=None)[source]¶ Linear program class.
Parameters: - c : vector
- A : matrix
- l : vector
- u : vector
- x : vector
Optimization Solvers¶
-
class
optalg.opt_solver.opt_solver.OptSolver[source]¶ Optimization solver class.
-
callbacks= None¶ List of callback functions.
-
fdata= None¶ Function data container.
-
get_dual_variables(self)[source]¶ Gets dual variables.
Returns: - lam : vector
- nu : vector
- mu : vector
- pi : vector
-
info_printer= None¶ Information printer (function).
-
is_status_solved(self)[source]¶ Determines whether the solver solved the given problem.
Returns: - flag : {
True,False}
- flag : {
-
line_search(self, x, p, F, GradF, func, smax=inf, maxiter=40)[source]¶ Finds steplength along search direction p that satisfies the strong Wolfe conditions.
Parameters: - x : current point (ndarray)
- p : search direction (ndarray)
- F : function value at x (float)
- GradF : gradient of function at x (ndarray)
- func : function of x that returns function object with attributes F and GradF (function)
- smax : maximum allowed steplength (float)
Returns: - s : stephlength that satisfies the Wolfe conditions (float).
-
parameters= None¶ Parameters dictionary.
-
set_info_printer(self, printer)[source]¶ Sets function for printing algorithm progress.
Parameters: - printer : Function.
-
terminations= None¶ List of termination conditions.
-