Optimization Solver Methods

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.

Load the OptimizationMethodFramework package

A candidate method is a solver that can solve minimization problems:

minimize
subject to constraints

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:

"Linear"linear objective
"Quadratic"quadratic objective
"Nonlinear"general nonlinear objective

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:

{"LinearEqualityConstraint", m}
"QuadraticConstraint"
"NonlinearConstraint"

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

Registering a solver method.

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:

"Linear"linear objective
"Quadratic"quadratic objective
"Nonlinear"general nonlinear objective

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+b0 (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

minimize
subject to constraints

where Κ is a tensor product of cones . This is equivalent to

minimize
subject to constraints

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
problemDataan Association that contains data about the problem to be solved.
optsOptions for the solver to use (may be empty)

"SolveFunction" evaluation.

Evaluation of sfun[problemData, opts] should return a list, {status, methodData}.

The status should be one of:

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:

minimize
subject to constraints

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
Identityonly 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+b0 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:

Nonewhen 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

MaxIterationsAutomaticmaximum number of iterations to use
PerformanceGoal$PerformanceGoalaspects of performance to try to optimize
ToleranceAutomaticthe tolerance to use for internal comparisons
WorkingPrecisionMachinePrecisionthe 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.

The primal problem is:

minimize
subject to constraints

This is equivalent to:

minimize
subject to constraints

The dual problem is:

maximize
subject to constraints

"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

Load the OptimizationMethodFramework` package.
Register a method named "FindMinimum" as an optimization solver method.

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 xn,ajmj×n,bjmj, j=1... k.

Define a function to convert the vector inequality conic constraints into regular equality and inequality constraints.
Define the main solver function. It constructs arguments for the function FindMinimum and records the solution in FindMinimumSolutionData.
Set up rules for the solution properties.

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

Use ConicOptimization with the newly set up convex method "FindMinimum".

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.

Specify the non-linear interior point method from the IPOPT library.
Specify the non-linear "InteriorPoint" method implemented in Wolfram Language.

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.

Try to solve a problem expressed in terms of "SemidefiniteCone" using the "FindMinimum" method.
Solve the semidefinite problem with the default solver.

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.

Solve a second order cone problem using the "FindMinimum" method.
Solve a quadratic optimization problem using the "FindMinimum" method.

When FindMinimum cannot find the minimum for some reason, typically a message will be issued.

The "Newton" method is inappropriate since it is for unconstrained problems:

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.

Change the method registration so that messages are printed immediately:
Run the same example again with the modified message handling:

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.

Find the location of the CVXLink` package
Load the CVXLink` package
Load the OptimizationMethodFramework` 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.

Register a method named "CVX" as a convex solver method.
Define the main solver function. It constructs a data object that keeps information about the problem and the Python session and returns solution status and data.
Set up rules for the solution properties.

"CVX" Solver Use Examples

Use ConicOptimization with the newly set up convex method "CVX":
Specify a sub-method for method "CVX" to get CVXPY to call the desired solver:
Use options Verbose, Tolerance or MaxIterations with the ECOS solver: