Functions | |
| virtual NDOSolver * | GetNDOSolver (void) |
Reading the data of the problem | |
| virtual Index | GetBNC (cIndex wFi) |
| virtual Index | GetBNR (cIndex wFi) |
| virtual Index | GetBNZ (cIndex wFi) |
| virtual void | GetBDesc (cIndex wFi, int *Bbeg, int *Bind, double *Bval, double *lhs, double *rhs, double *cst, double *lbd, double *ubd) |
| virtual Index | GetANZ (cIndex wFi, cIndex strt=0, Index stp=Inf< Index >()) |
| virtual void | GetADesc (cIndex wFi, int *Abeg, int *Aind, double *Aval, cIndex strt=0, Index stp=Inf< Index >()) |
Detailed Description
In some cases, the function Fi to be minimized is composed of several different components [see GetNrFi() above] which can be subdivided into two different classes:
- "difficult" components, that are known only through a "complicated" oracle (the usual situation), and
- "easy" components, for which a "compact, efficient" description is known.
These methods allow an NDO solver to obtain a compact description of the "easy" components of Fi; in particular, the components are considered easy if they can be described with a "compact" linear program (any polyhedral function can be described a linear program, but here the idea is that the linear program must have "few" variables and constraints). That is, the h-th component is "easy" if
Fi[ h ]( Lambda ) = sup{ ( c[ h ] - Lambda * A[ h ] ) x[ h ] : d[ h ] <= B[ h ] x[ h ] <= e[ h ] , l[ h ] <= x[ h ] <= u[ h ] }
i.e., if Fi[ h ] is the Lagrangian function of a "compact" linear program. A typical case is when the whole Fi is a Lagrangian function of a complex problem, where the Lagrangian problem decomposes into some "easy" (linear) and some "hard" (nonlinear/nonconvex) problems. Note that if some component has a linear (affine) part, all these are considered to be "embedded" in the linear (affine) 0-th component of Fi.
Some NDO solvers may exploit the knowledge of a complete description of the "easy" components of the function; these methods are thought for providing the interested solver with the information.
- Note
- Important: "easy" components that reveal themselves cannot be considered "standard" components; that is, the "ordinary" Fi(), NewGi(), SetGi(), ... [see below] machinery for computing function values and subgradients is not assumed to work with easy components, and the NDOSolver is not allowed to call them for "easy" components. In other words, by declaring a component as "easy" the FiOracle is basically freed by all obligations regarding it, and it's the NDOSolver's duty to use the provided information to handle it (or refuse to do so and die gracefully). Clearly, whether or not an "easy" component is declared as such is a decision of the FiOracle, which can then avoid to do so if the NDOSolver it's going to be used with does not support it, or if it can handle it (presumably) more efficiently than a generic linear solver due to its knowledge of the structure of the subproblem.
- These methods are intended to be called only with 1 <= wFi <= GetNrFi(). Calls with wFi > GetNrFi() make no sense. Calls with wFi == 0 would indeed make sense, as the linear 0-th component of Fi is precisely one very special case of function which has a compact polyhedral description (with only one variable x[ 0 ], an empty B[ 0 ], l[ 0 ] == u[ 0 ] == 1 and A[ 0 ] = b). However, other means are already provided for obtaining this very special description [see GetGi() below].
- The existence of a polyhedral description of the components is not assumed to vary over time. That is, either a component always has a polyhedral description, or it never has one; in other words, GetBNC( h ) must always return the same value throughout all the life of a FiOracle object, or at least as long as the FiOracle is used by one given NDO solver. Changes in the number of variables might in principle happen in some cases (e.g., variables generation within the polyhedral description) but this is not supported by the current version of this interface.
For any component h that has a polyhedral description, the NDO solver should in principle call these methods only once, or at least few times once and for all during the initialization stages. This means that these methods should not be a computational bottleneck, and no particular care should be required to implement them very efficiently. However, the NDO solver may call these methods a few times, and there are cases where repeated calls are clearly needed. The first is if the NDO solver uses variables generation techniques, which try to solve a NDO problem by restricting it to a (small) "active set" of the variables, minimizing the function in that subspace and possibly revising the active set. Such a NDO solver may acquire the information about different parts of the matrix A[ h ] in different moments, as it only works with a submatrix. Another is if the NDO solver discovers that one of the components which have a polyhedral description is changed (e.g., because the methods ChgFiV() and ChgSbG() of class NDOSolver are called, see NDOSlver.h); in this case, it may want to call these methods again to acquire the new description.
Since in most cases a polyhedral description of the components is not available, these methods are not "pure virtual"; rather, they are given a default implementation which corresponds to "no polyhedral description available".
Function Documentation
◆ GetADesc()
|
inlinevirtual |
Return a description of the submatrix of A[ wFi ] containing all the rows with indices between start and min( stp , GetNumVar() ) - 1; the meaning of Abeg, Aind and Aval is analogous to that of Bbeg, Bind and Bval in GetBDesc() [see above].
◆ GetANZ()
Returns the number of nonzeroes in the matrix A[ wFi ] (whose number of columns is GetBNC( wFi ) and whose number of rows is GetNumVar()); more precisely, it returns the number of nonzeroes in the submatrix of A[ wFi ] containing all the rows with indices between start and min( stp , GetNumVar() ) - 1 (corresponding to the variables with those "names").
◆ GetBDesc()
|
inlinevirtual |
Returns a description of the matrix B[ wFi ] and of the vectors d[ wFi ], e[ wFi ], c[ wFi ], l[ wFi ] and u[ wFi ]. Bbeg, Bind and Bval must point respectively to a (GetBNC( wFi ) + 1)-vector of ints, a GetBNZ( wFi )-vector of ints and a GetBNZ( wFi )-vector of doubles; upon return, a description of B[ wFi ] has to be written in these arrays. Bbeg[ i ] says where the description of the i-th column of the matrix starts in the arrays Bind[] and Bval[], for i = 0 ... GetBNC() - 1; for all the indices Bbeg[ i ] <= j < Bbeg[ i + 1 ], Bval[ j ] is the value of (B[ h ])[ Bind[ j ] ][ i ], while all the other elements on the i-th column are zero. lhs and rhs must point to GetBNR( wFi )-vectors of doubles; upon return, the vectors d[ wFi ] and e[ wFi ] have to be written there. Finally, cst, lbd and ubd must point to GetBNC()-vectors of doubles; upon return, the vectors c[ wFi ], l[ wFi ] and u[ wFi ] have to be written there.
Note that bounds, either of the constraints or on the variables, may be infinite. In particular, for any 0 <= i < GetBNR( wFi ), lhs[ wFi ][ i ] can be == - Inf< double >() to indicate that the i-th constraint has the form B[ wFi ][ i ] x[ wFi ] <= rhs[ wFi ][ i ], while rhs[ wFi ][ i ] can be == + Inf< double >() to indicate that the i-th constraint has the form lhs[ wFi ][ i ] <= B[ wFi ][ i ] x[ wFi ]; it is assumed that at least one of the two bounds is finite, for otherwise there is no i-th constraint. Similarly, any 0 <= j < GetBNC( wFi ), lbd[ wFi ][ j ] can be == - Inf< double >() and/or ubd[ wFi ][ j ] can be == + Inf< double >(), to indicate that x[ wFi ][ j ] has no finite lower/upper bound. In this case, both bounds infinite (respectively - and +) can happen, although some NDO solvers may require the overall feasible region of the wFi-th subproblem to be compact (this makes the function finite everywhere and therefore "more regular"). Note that, however, it is always assumed that lhs[ wFi ][ i ] <= rhs[ wFi ][ i ] (equality is a definite possibility, corresponding to an equality constraint), and lbd[ wFi ][ j ] <= ubd[ wFi ][ j ] (equality here being unlikely, for it corresponds to a fixed variable that can always be dealt with implicitly), for otherwise the component is "trivially empty" (constant - INF, i.e., not proper convex).
The NDO solver is allowed to query only a subset of the information; that is, by passing 0 to some of the pointers, the oracle will not write the corresponding information. This can be done for all parameters individually, except for the first three; that is, if just one among Bbeg, Bind and Bval is 0, then all the other ones are to be treated as if they were 0, too. It if of course expected that at least one among lhs, rhs, cst, lbd and ubd, and/or the three Bbeg, Bind and Bval, be nonzero at each call.
◆ GetBNC()
Returns the number of variables of the "easy" linear problem which describes Fi[ wFi ], that is, the number of columns of the matrices B[ wFi ] and A[ wFi ] and the length of the vectors x[ wFi ], c[ wFi ], l[ wFi ] and u[ wFi ]. If GetBNC( wFi ) returns 0, then no polyhedral description of Fi[ wFi ] is available, and no calls to any other of these methods with the same wFi are permitted.
◆ GetBNR()
Returns the number of rows of the matrix B[ wFi ] and the length of the vectors d[ wFi ] and e[ wFi ]; GetBNR( wFi ) can return 0 if only "box" constraints are imposed on the variables x[ wFi ].
◆ GetBNZ()
Returns the number of nonzeroes in the matrix B[ wFi ]; this is clearly 0 if GetBNR( wFi ) == 0.
◆ GetNDOSolver()
|
inlinevirtual |
This method allows to read back the pointer to the NDOSolver that has been passed to the FiOracle through SetNDOSolver() [see above], if any.
Generated by
1.12.0