Optimization Solver Method Framework
The Optimization`MethodFramework` context provides a framework that enables connecting a solver for a class of optimization problems to the Wolfram Language optimization functions. This notebook describes how to register a solver to be connected and set up definitions that interface with the the Wolfram Language system.
The examples shown below assume that Optimization`MethodFramework` is on the context path.
A candidate method is a solver that can solve minimization problems:
where the objective function and the constraints fit into particular forms that can be used to solve the problem efficiently.
Objective functions with the following forms are supported:
Conic constraints of the form 
are supported for the following proper convex cones 
:
| {"NonNegativeCone", m} |  |  such that  | |
| {"NormCone", m} |  |  such that  ≤ym | |
| {"SemidefiniteCone", m} |  | symmetric positive semidefinite matrices  | |
| "ExponentialCone" |  |  such that  | |
| "DualExponentialCone" |  |  such that  or  | |
| {"PowerCone",α} |  |  such that  | |
| {"DualPowerCone",α} |  |  such that  |
Additionally the following constraint types are supported:
A solver is registered into the system by specifying what sorts of objective function and constraints it supports. Note that it is not expected that a solver has support for all forms of objectives or constraints. For example a linear optimization solver only has support for "EqualityConstraint" and "NonNegativeCone".
Registering a Solver for Connection
A solver is connected to the Wolfram Language optimization system by registering it using RegisterOptimizationMethod.
| RegisterOptimizationMethod[method, assoc] | registers a solver with name method and Association assoc containing details of the solver capabilities |
The solver name method should be a string. Once a solver is registered, it can be used in the Wolfram Language optimization functions by specifying Method->method.
The following keys are considered in the Association assoc:
| "SolveFunction" | the function to evaluate to use the solver | |
| "Submethods" | a list of registered submethods | |
| "ConstraintSupport" | a list of the support for constraints | |
| "ObjectiveSupport" | the type of objective function supported by the method | |
| "MixedIntegerSupport" | whether or not the solver works with mixed integer problems | |
| "ExtendedPrecisionSupport" | whether the method supports extended precision | |
| "FreeMethodDataFunction" | a function to evaluate when the solver data is no longer needed | |
| "MessageHandling" | how to handle any messages generated by the solver |
"ObjectiveSupport"
The value associated with "ObjectiveSupport" should be one of the following:
If "ObjectiveSupport" is not specified, the support is assumed to be linear.
"ConstraintSupport"
The value associated with "ConstraintSupport" should be an association where the keys are the constraint forms supported and the values are the type of support of that list of rules ctype->stype, where ctype describes a constraint type and stype describes the support type.
The constraint type can be given by any of the following:
| "EqualityConstraint" | equality constraints | |
| "NonNegativeCone" | linear inequality constraints | |
| "NormCone" | second order cone constraints | |
| "SemidefiniteCone" | positive semidefinite constraints | |
| "ExponentialCone" | exponential cone constraints | |
| "DualExponentialCone" | dual exponential cone constraints | |
| "PowerCone" | power cone constraints | |
| "DualPowerCone" | dual power cone constraints | |
| "QuadraticConstraint" | quadratic constraints | |
| "NonlinearConstraint" | nonlinear constraints |
The support type can be one of the following:
| "Affine" |  | |
| "Membership" |  | |
| "LinearMatrixInequality" | a1 x1+…+ak xk+b⪰ 0 (SemidefiniteCone only) | |
| "SplitAffine" | separate semidefinite constraints by block structure of the linear matrix inequality (Semidefinite cone only) |
Note that membership support type is a special case of "Affine" support where 
is the zero vector and 
if 
and 0 otherwise. The reason it is included as a separate case is that some authors and solvers describe the standard form of a conic problem by
where Κ is a tensor product of cones 
. This is equivalent to
In cases where the solver requires membership for at least one of the supported cones, the Wolfram Language system automatically converts the problem to one supported by the solver.
SemidefiniteOptimization works by combining all of the constraints in a problem into a single semidefinite cone constraint. Its default solvers expect the problem to be expressed in the form of a single linear matrix inequality. In cases where the solver requires membership for at least one of the supported cones, the Wolfram Language system automatically converts the problem to one supported by the solver.
"SolveFunction"
The value, sfun = assoc["SolveFunction"] associated with the "SolveFunction" key is the main interface to the Wolfram Language optimization functions. When an optimization function is used with Method->method, then sfun[problemData, opts] is evaluated.
| sfun[problemData, opts] | The expression evaluated when Method->method is given to Wolfram Language optimization functions |
| problemData | an Association that contains data about the problem to be solved. |
| opts | Options for the solver to use (may be empty) |
Evaluation of sfun[problemData, opts] should return a list, {status, methodData}.
| Success["Solved",assoc] | the problem was solved | |
| Success["Unbounded",assoc] | the problem was unbounded | |
| Success["Infeasible",assoc] | the problem was infeasible | |
| Failure[reason,assoc] | the solver failed to solve the problem because of reason |
The Association assoc can contain information about solution, but it can be empty () since the Wolfram Language system handles messages automatically.
The method data methodData can be any WolframLanguage expression that has definitions associated with it to retrieve solution properties. See the Method Data section below for details on the expected solution properties.
Note that the number of options depends on how the method winds up being called, so sfun should be able to take an arbitrary number of arguments, so if your solve function is defined via DownValues, the pattern for the opts arguments should be given using BlankNullSequence (opts___). For example the definition might be sfun[problemData_, opts___] := …
Problem Data
The problemData Association is constructed by the Wolfram Language optimization functions to correspond to the problem:
The problem is described using the following keys:
| "ObjectiveVector" |  | |
| "ObjectiveMatrix" | quadratic matrix  if "ObjectiveSupport" is "Quadratic" | |
| "ObjectiveFunction" | nonlinear objective function  | |
| "ConstraintSpecifications" |  | |
| "ConstraintCoefficientArrays" |  | |
| "IntegerVariableColumns" | a list of the column indexes for any components of  that are expected to be integers. | |
| "ConeVariableColumns" | a list of the variable columns associated with each conic contraint that requires variable membership | |
| "ExtraColumns" | the number of extra columns added to convert to conic constraints with variable membership | |
| "Caller" | the Wolfram Language function the solver is being called from |
"ObjectiveVector"
The value associated with "ObjectiveVector" will be defined as a vector 
when "ObjectiveSupport" is "Linear" or "Quadratic" (or not specified and assumed to be linear). In this case, the objective function is 
.
"ObjectiveMatrix"
The value associated with "ObjectiveMatrix will be defined as a positive semidefinite matrix 
only when "ObjectiveSupport" is "Quadratic". In this case, the objective function is 
.
"ObjectiveFunction"
The value associated with "ObjectiveMatrix will be defined as a function 
that is an Experimental`NumericalFunction objective only when "ObjectiveSupport" is "Nonlinear". In this case, the objective function is computed using f[x]. First and second order derivatives may also be computed using f["Gradient"[x]] and f["Hessian"[x]].
"ConstraintSpecifications"
The list associated with "ConstraintSpecifications" may contain the following specifications:
| {"EqualityConstraint", m} |  |  such that  | |
| {"NonNegativeCone", m} |  |  such that  | |
| {"NormCone", m} |  |  such that  ≤ym | |
| {"SemidefiniteCone", m} |  | symmetric positive semidefinite matrices  | |
| "ExponentialCone" |  |  such that  | |
| "DualExponentialCone" |  |  such that  or  | |
| {"PowerCone",α} |  |  such that  | |
| {"DualPowerCone",α} |  |  such that  | |
| "QuadraticConstraint" |  | ||
| "NonlinearConstraint" |  |
The list will be ordered as shown in the table above. Since linear constraints can be combined, there will be at most one instance of "EqualityConstraint" and "NonNegativeCone". Thus, if there are equality constraints, they will appear as the first element, and if there are linear inequality constraints they will be in the first or second element depending on whether there are equality constraints or not.
If the problem has constraints not supported by the solver, the Wolfram Language system will detect this automatically and issue an appropriate message. Thus, only cone specifications that the solver has been registered to provide support for will be included in the specification list.
"ConstraintCoefficientArrays"
The entries in the list associated with "ConstraintCoefficientArrays" correspond one to one with the specifications in the "ConstraintSpecifications" list and will have one of the following forms:
 | the {vector, matrix} pair in  | |
 | the {constant, vector, matrix} triple in  for quadratic constraints | |
| Identity | only when explicit membership of variable components  is required |
For semidefinite constraints, if the support is given as "LinearMatrixInequality", 
is given in the special form {bj,Inactive[Transpose][{aj,…,ajn},{3, 2, 1}]} to make the linear matrix inequality a1 x1+…+ak xk+b⪰
0 as explicit as possible while maintaining mathematical correctness
"ConeVariableColumns"
The key "ConeVariableColumns" will only be present if at least one of the cones specified in the list associated with "ConstraintSpecifications" has been registered with "Membership" support for the solver.
The entries in the list associated with "ConeVariableColumns" correspond one to one with the specifications in the "ConstraintSpecifications" list and will have one of the two following forms:
 |  | |
| None | when the conic constraint is affine ( ) |
"ExtraColumns"
The value associated with "ExtraColumns" will be zero unless the problem was converted to satisfy membership conic constraint requirements. If the problem was converted then this will be the number of extra columns added during the conversion process.
"IntegerVariableColumns"
The list associated with "IntegerVariableColumns" gives the indexes of the variable vector that should have integer values. If the solver is not registered to have mixed integer support this will always be the empty list {}.
Options
The options that will be given to the solver function in sfun[problemData, opts] may be any options that the solver uses as method options in addition to the options given to the Wolfram Language optimization function.
The Wolfram Language optimization function options included are
| MaxIterations | Automatic | maximum number of iterations to use | |
| PerformanceGoal | $PerformanceGoal | aspects of performance to try to optimize | |
| Tolerance | Automatic | the tolerance to use for internal comparisons | |
| WorkingPrecision | MachinePrecision | the precision to use |
These options will only be included in opts if they are given values different from the default values listed above.
The WorkingPrecision option will only be included if the solver was registered with "ExtendedPrecisionSupport"->True.
A method may be specified with method options by using Method->{method, mopts} where mopts are the method options.
Note that when opts is empty, the evaluation of the solver function will be just sfun[problemData]
Method Data
When sfun[problemData, opts] evaluates to {status, methodData} the methodData can be any Wolfram Language expression.
When the status has a Head of Success, there should be definitions for the following solution properties:
| methodData["PrimalMinimizerVector"] |  | |
| methodData["PrimalMinimumValue"] |  | |
| methodData["DualMaximizer"] |  | |
| methodData["DualMaximumValue"] |  | |
| methodData["Slack"] |  (will be computed automatically if not defined) |
These are based on the primal and dual problems with notation described below.
"ExtendedPrecisionSupport"
The typical assumption is that the solver will use machine precision numbers to do the computation. However if the method can work with extended precision numbers, the solve function should accept a WorkingPrecision option and the value associated with the "ExtendedPrecisionSupport" key should be True. When the method can additionally work with exact numerical computations (WorkingPrecision->∞) the associated value should be All. The WorkingPrecision option is processed as a method option, for example Method->{"methodName", WorkingPrecision->20}.
"MessageHandling"
The value associated with "MessageHandling" should be one of the following:
| "Collect" | collect messages (this is the default) | |
| "Issue" | issue messages immediately from when they are generated | |
| "Suppress" | suppress any messages generated by the solver |
With the default value "Collect", messages are collected by the code and issued when the solution is complete. The message tag is modified to the function that is calling the solver.
Examples
"FindMinimum" solver
This example shows the steps necessary to set up a very simple convex solver using a non-linear interior point method through the function FindMinimum. This method is not as fast or robust as using dedicated convex solvers, but serves as as an illustration of the solver registration and interface.
Solver Registration and Definitions
This registers a solver named "FindMinimum" with a solve function named "FindMinimumSolve" and conic constraints that can be vector equality, vector inequality or norm cone constraints with affine left hand side: aj.x+bj==0, aj.x+bj0 or aj.x+bjm0 where x∈n,aj∈mj×n,bj∈mj, j=1... k.
When a property is not given by the solver an appropriate setting for the property is Missing["NotAvailable"]. This is used for any dual properties for the "FindMinimum" solver since the dual is not computed or considered by the general nonlinear interior point algorithm.
"FindMinimum" Solver Use Examples
The main solver function passes any options it gets down to FindMinimum. From the convex solver, if you give Method->{"FindMinimum", fmopts}, fmopts will be passed down to FindMinimum.
When the problem lies outside of the scope of the problem the solver is registered to handle, the Wolfram Language system automatically detects this and issues a message.
The examples above have all showed use of ConicOptimization. Other convex optimization functions may be used as well (for problems appropriate for that solver). For registered convex solvers the functions automatically convert to conic form.
When FindMinimum cannot find the minimum for some reason, typically a message will be issued.
The method was registered without specifying the "MessageHandling" property so the default "Collect" setting is used. With "Collect" any given message is only printed once even if it is encountered multiple times. When working to debug a new solver function it is often more convenient to have the messages printed as soon as they are generated.
The reason the FindMinimum::ucmtd message comes out multiple times is a consequence of the way the Wolfram Language evaluator works when variables are given local values as happens with FindMinimum.
"CVX" solver
An example of using the built-in Wolfram Language external language interface for Python to access the CVXPY package for convex optimization and modeling.
Prerequisites are to install and configure Python for external evaluate, install CVXPY and optionally some solvers that CVXPY can call in addition to those installed by default with CVXPY.
The implementation of the "CVX" convex solver is located in the CVXLink` package.
Solver Registration and Definitions
The registration and definitions shown below are implemented in the CXVLink package and are shown here just for illustration since they will be evaluated when the CVSLink package is loaded.
