OBOE FAQ

OBOE FAQ OBOE (Oracle Based Optimization Engine) Frequently Asked Questions

What is OBOE?
OBOE is an optimization engine for solving non-differentiable convex problems. It solves problems where the objective function is composed of 2 parts, one smooth and the other non-smooth. It uses the sub-differential information for the non-smooth and the gradients and hessian for the smooth part to find the optimal solution using interior point methods.
What is ACCPM?
ACCPM stands for Analytic Center Cutting Plane Methods, which is a class of methods using analytic centers of a localization set defining the problem domain. It uses interior point method framework to move from one solution to the next and eventually converging to optimality.
What is the difference between OBOE and ACCPM?
ACCPM is the methodology behind OBOE. OBOE is the product based on ACCPM theory.
What does "proximal" refer to in proximal ACCPM?
ACCPM uses polyhedral relaxation scheme to minimize the non-differentiable convex functions. This involves replacing the original function with variables bounding these functions and using these variables in the objective function. So instead of minimizing f1(y), where f1(.) is a convex non-diffentiable function we minimize z, such that
```
	f1(y) <= z.
```
In general ACCPM minimizes a linear objective function which is a surrogate for the original f1(y) + f2(y). It also adds a lograthmic barrier fucntion to the objective function which ensures the required constraints are satisfied. The use of this barrier term is standard in interior point methods.
The proximal ACCPM adds one more component to the objective to be minimized. The proximal term given by:
```
	(&rho/2) * (y - yc) * Q * (y - yc),
```
is also added to the objective function.
This term can be seen as a spring which can be used to control the movement of the query point from the current analytic center, yc.
The parameter &rho can be controlled by the ACCPM::Parameter Rho and DynamicRho.
How do I use OBOE?
OBOE is a distributed as a bunch of C++ libraries. The user needs to implement the "Oracle" by deriving from the ACCPM::Oracle class.
Then the user creates a query point generator object ACCPM::QpGenerator which takes in the oracle and parameters. The parameter setting are input by creating an ACCPM::Parameter object which reads in set of parameters from a text file.
How do I set the parameters for OBOE?
OBOE provides a parameter class, ACCPM::Parameter. The user needs to instantiate an object of this class and provide the parameter values in one of 2 ways:
i.Write the parameters and their values in a text file and instantiate the parameter object with this file. This can be used only for specifying integer, real and string valued parameters. To specify a vector of values for example to set the starting point or set lower bounds on variables the user needs to use the API of ACCPM::Parameter class. The text file based parameter setting is useful incase the user wants to try different settings, in this case they only need to change the values in the text file and run the executable again, there is no need to compiling their code again.
ii. The other way is to use the API provided by ACCPM::Parameter class.
How do I set the starting point?
The user can use the following function provided with ACCPM::Parameter
```
	bool setStartingPoint(const StdRealVector& v);
```
How do I set the weights on the objective function?
OBOE supports the following formulation:
```
	min &pi * f1(y) + f2(y)
```
The &pi vector can be set using the following function of ACCPM::Parameter
```
	bool setPi(const StdRealVector& v);
```
The vector v should be of same size as the "NumSubproblems" number of subproblems parameter. This parameter is default to 1, but can be more if the user chooses to decompose the non-smooth component f1(.) and represent it as a weighted sum of non-smooth functions.
How do I set the linear component?
The linear component i.e the case when the smooth function f2(.) is a linear function can specified easily with either of the following functions of ACCPM::Parameter
```
	bool setB(const StdRealVector& v);
	bool setB(const AccpmVector& v);
```
The vector v should have the same size as the number of variables "NumVariables" parameter.
This is easier than having to specify the linear function as a smooth function and implementing the oracle for it, since in this case the gradient value is always the same.
Note, however if the f2(.) is a smooth function which has a linear component and a non-linear component, the user needs to specify this via the smooth oracle using the ACCPM::Oracle object and implementing the ACCPM::Oracle::eval function. OBOE supports either the linear component being specified via setB() function or specifying the smooth oracle but not both.
How do I specify the smooth component f2(.)?
To specify the smooth component the user needs to implement another oracle which gives the gradient and hessian of the function at a given query point.
What does the NumSubProblems parameter do?
The "NumSubProblems" parameter is used to specify the number of components of the non-smooth f1(.) function. By default this value is 1. For some problems it is more natural to specify the f1(.) function as a sum of convex functions. This is referred to as the disaggregated mode. The user can then give the sungradients of each of the component functions instead of giving one subgradient. This approach helps in cases the oracle gives more information at each iteration and hence the number of iterations needed for convergence is expected to reduce. On the other hand this increases the size of the matrices as the oracle returns NumSubProlems number of cuts at each iteration.
What is the difference between Outer and Inner Iterations?
Outer Iterations are the iterations which OBOE needs to reach convergence or some other termination criterion. At each iteration OBOE comes back with a query point and asks the user defined oracle to give the subgradient information via the ACCPM::Oracle::eval function call. The user can specify the maximum number of such iterations to be performed by using the parameter MaxOuterIterations.
Inner Iterations on the other hand are the iterations performed within each outer iteration to solve the Newton System to a certain precision.The user can specify the maximum number of such iterations to be performed by using the parameter MaxInnerIterations. The default value for this parameter is 50.
In the end OBOE reports the total number of outer as well as inner iterations.
Can I specify general non-linear constraints?
No, currently OBOE does not support general non-linear constraints. The only non-linear constraint supported is of the form of a "ball constraint" i.e. the variables are restricted to be within a ball centered around a given point and with a given radius,
```
	(y - c)'(y - c) <= r.
```
How do I set bounds on the variables?
The ACCPM::Parameter object provides API for this functionality.
The user needs to create an std vector of size equal to number of variables
in the problem. The vector should have the bounds for the variables.
The following functions allow the user to set the lower and upper bounds respectively:
```
	bool setVariableLB(const StdRealVector& v);
	bool setVariableUB(const StdRealVector& v);
```
How do I specify ball constraints for the variables?
The user needs to give the center and the radius of the ball in which the
variables lie. The center can be specified by the following function of
ACCPM::Parameter
```
	bool setCenterBall(const StdRealVector& v);
```
and the radius is set using the double parameter "RadiusBall", for example,
```
	param.setRealParameter("RadiusBall", 5); 
```
How does the Filter parameter work?
The Filter parameter which is set by the following example code:
```
	param.setIntParameter("Filter", true)
```
or putting it in the input parameter file as follows
```
	Filter Int 1
```
This enables OBOE to filter away duplicate cuts incase the oracle generates them. The default value of this parameter is set to 1, unless the user has strong reason to disable it we recommend that the user keeps the filter enabled as it does away with redundant cut information.
How do I disable Filter?
The user can disable Filter by adding the following to the parameter file:
```
	Filter Int 0
```
Can I verify if my problem satifies convexity with OBOE?
The user can use the "ConvexityCheck" parameter for enabling the checking of
convexity. This reports if the user has given cuts which violate convexity.
The user can instruct OBOE to "fix" these violations if it is possible, by enabling the ConvexityFix parameter.
By default both these parameters are off.
What is the termination criterion for OBOE?
OBOE uses one of the following criterion for termination:
1. MaxOuterIterations : If the number of outer iterations reaches this number OBOE terminates.
2. Tolerance : If the relative gap becomes less than the specified Tolerance value.
3. User Stop : If the user signals to stop the iterations by sending a 1 in the ACCPM::Oracle::eval function.
What is Relative Gap?
Relative Gap is used as a measure for the quality of a solution. For minimization problem it is defined as follows:
```
(ObjectiveUB - ObjectiveLB) / ObjectiveUB,
```
where ObjectiveUB and ObjectiveLB are the current upper and lower bounds on the objective function.
What is the Tolerance parameter?
The Tolerance parameter is used to specify the quality of the solution. If the MaxOuterIterations is not exceeded, OBOE continues execution until the computed Relative Gap becomes less than the specified Tolerance. By default Tolerance is set to 1e-6.
What is the Rho parameter?
The Rho parameter specifies the weight, &rho of the proximal term:
```
	&rho/2 *(y - yc)*Q*(y - yc),
```
where yc is the current analytic center.
This is used to control the movement of the query point. If the DynamicRho parameter is off the weight remains the same throughout the run. If the DynamicRho is turned on then this weight changes based on an internal strategy. The changes to Rho can be limited by the RhoMax and RhoMin paramerters. OBOE will not lower the Rho beyond RhoMin or raise it above RhoMax.
What is the ComputeLowerBound parameter?
OBOE has an internal strategy for computing the lower bound (or upper bound in case of maximization). For most problems it is a good idea to use this inbuilt lower bound computation and hence the default of this parameter is set to 1 i.e it is enabled.
However, there are some problems where the user has a better idea of how to compute the bound instead of using the generic computation. In this case the user can turn off the OBOE bound computation and provide a lower bound at each outer iteration by implementing the following functions of ACCPM::Oracle :
```
	virtual bool computesLowerBound() const { return false; }
	virtual double getLowerBound() const { return ACCPM_MINUS_INF; }
```
The above are the default implementations and it is upto the user to correctly define them and update the bounds. If the oracle returns true for computesLowerBound() function, OBOE calls the getLowerBound() function at every outer interation and updates the lower bound.
Note: The parameter is called ComputeLowerBound because internally all problems are considered as minimizations problems and hence OBOE always computes lower bounds.
Can I specify the bounds on the objective function?
Yes, the user can use the ObjectiveLB and ObjectiveUB parameters to specify the lower and upper bound for the objective function.
How can I specify the weight on the epigraph cut?
The weight on the epigraph cut is specified by the following parameters:
```
	WeightEpigraphCutInit and
	WeightEpigraphCutInc
```
The default for both these parameters is 1, but the user can specify different initial epigraph cut weight via the parameter WeightEpigraphCutInit and the amount to increase it in every outer iteration via the WeightEpigraphCutInc parameter.
Can I give non-diagonal Hessian for the smooth oracle?
No, currently OBOE only supports diagonal Hessian for the smooth oracle. The Hessian information is hence a vector of size equal to the number of variables, and this is interpreted as the diagonal of the Hessian matrix for the smooth oracle.