Sandia Home Sandia Home
Main Page | Publications | Downloads | Configuration | Running the Code | Solver Parameters | FAQ | Namespace List | Class Hierarchy | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

APPSPACK::Constraints::Linear Class Reference

#include <APPSPACK_Constraints_Linear.hpp>

Collaboration diagram for APPSPACK::Constraints::Linear:

Collaboration graph
[legend]
List of all members.

Detailed Description

Constraint class that implements general linear inequality constraints.

We consider the following linearly constrained problem

\[ \begin{array}{rlcrcl} \displaystyle\mbox{minimize} & \multicolumn{5}{c}{f(x)} \\ x \in R^n \\ \mbox{subject to} & b^{\rm lower} & \le & x & \le & b^{\rm upper}\\ & b^{\rm ineq\_lower} & \le & A^{\rm ineq} x & \le & b^{\rm ineq\_upper} \\ & & & A^{\rm eq} x & = & b^{\rm eq} \end{array} \]

The bounds in the inequalities are not required to be finite, e.g., it is allowable that $b^{\rm lower} = -\infty$.

Because it can dramatically improves performance, variable scaling is used. The scaling vector is denoted by $s$. The scaling can be specified by the user; see Linear Constraint Parameters. If all variable bounds are finite, a default scaling vector is provided; namely

\[ s_i = u_i - \ell_i. \]

In the case where any element of $x$ is unbounded, the user is required to specify $s$ within the Linear Constraint Parameters.

We define the variables in the scaled space as follows:

\[ \begin{array}{lcl} \tilde{x} &=& S^{-1}(x - \hat{\ell}), \\ \tilde{f(\tilde x)} &=& f(S \tilde x + \hat{\ell}) = f(x), \\ \tilde{b}^{\rm lower} &=& S^{-1}(b^{\rm lower} - \hat{\ell}), \\ \tilde{b}^{\rm upper} &=& S^{-1}(b^{\rm upper} - \hat{\ell}), \\ \tilde{b}^{\rm ineq\_lower} &=& b^{\rm ineq\_lower} - A^{\rm ineq} \hat{\ell}, \\ \tilde{b}^{\rm ineq\_upper} &=& b^{\rm ineq\_upper} - A^{\rm ineq} \hat{\ell}, \\ \tilde{b}^{\rm eq} &=& b^{\rm eq} - A^{\rm eq} \hat{\ell}, \\ \tilde{A}^{\rm ineq} &=& A^{\rm ineq} S, \\ \tilde{A}^{\rm eq} &=& A^{\rm eq} S. \end{array} \]

Here

\[ S = \left(\begin{array}{ccc} s_1 \\ & \ddots \\ & & s_n \end{array}\right) \]

and

\[ \hat{\ell}_ = \left\{ \begin{array}{cl} b^{\rm lower}_i & {\rm if } \; b^{\rm lower}_i > -\infty \\ 0 & {\rm otherwise}. \end{array} \right. \]

The scaled problem is then given by

\[ \begin{array}{rlcrcl} \displaystyle\mbox{minimize} & \multicolumn{5}{c}{\tilde f(\tilde x)} \\ \tilde x \in R^n \\ \mbox{subject to} & \tilde b^{\rm lower} & \le & \tilde x & \le & \tilde b^{\rm upper}\\ & \tilde b^{\rm ineq\_lower} & \le & \tilde A^{\rm ineq} \tilde x & \le & \tilde b^{\rm ineq\_upper} \\ & & & \tilde A^{\rm eq} \tilde x & = & \tilde b^{\rm eq} \end{array} \]

Combining the bound and linear inequality constraints, we get

\[ \begin{array}{rlcrcl} \displaystyle\mbox{minimize} & \multicolumn{5}{c}{\tilde f(\tilde x)} \\ \tilde x \in R^n \\ \mbox{subject to} & \hat b^{\rm lower} & \le & \hat A^{\rm ineq} \tilde x & \le & \hat b^{\rm upper} \\ & & & \tilde A^{\rm eq} \tilde x & = & \tilde b^{\rm eq} \end{array} \]

where

\[ \begin{array}{ccccc} \hat{b}^{\rm lower} = \left(\begin{array}{l} \tilde{b}^{\rm lower} \\ \tilde{b}^{\rm ineq\_lower} \end{array} \right), & & \hat{b}^{\rm upper} = \left(\begin{array}{l} \tilde{b}^{\rm upper} \\ \tilde{b}^{\rm ineq\_upper} \end{array} \right), & & \hat{A} = \left(\begin{array}{l} I \\ \tilde{A}^{\rm ineq} \end{array} \right). \end{array} \]

With respect to the scaled system, APPSPACK::Constraints::Linear stores the following as member variables: $ \hat{A} $, $\hat{b}^{\rm lower}$, $\hat{b}^{\rm upper}$, $ \tilde{A}^{\rm eq} $, and $\tilde{b}^{\rm eq}$.

Definition at line 203 of file APPSPACK_Constraints_Linear.hpp.

Public Member Functions

 Linear (Parameter::List &params)
 Constructor.
 ~Linear ()
 Destructor.
void print () const
 Prints the bounds, scaling, and general linear constraint information.
Accessors
double getEpsMach () const
 Returns machine epsilon value, epsMach.
const Vector & getScaling () const
 Returns scaling vector, scaling.
const Vector & getLower () const
 Return vector of lower bounds, bLower.
const Vector & getUpper () const
 Return vector of upper bounds, bUpper.
const Vector & getBhatLower () const
 Return lower bound on scaled inequality constraints, bIneqLower.
const Vector & getBhatUpper () const
 Return upper bound on scaled inequality constraints, bIneqUpper.
const Vector & getBtildeEq () const
 Return right-hand side vector of scaled equality constraints, bEq.
const Matrix & getAhat () const
 Return coefficient matrix for scaled inequality constraints, aIneq.
const Matrix & getAtildeEq () const
 Return coefficient matrix for scaled equality constraints, aEq.
void getNominalX (Vector &x) const
 Returns a point (x) that is initially feasible with respect to the bound constraints.
Projectors.
void scale (Vector &x) const
 Maps x to scaled space via affine linear transformation.
void unscale (Vector &w) const
 Maps w to unscaled space via affine linear transformation.
Feasibility verifiers.
bool isFeasible (const Vector &x) const
 Return true if feasible, false otherwise.
void assertFeasible (const Vector &x) const
 Throws an error if x is infeasible; see isFeasible().
Constraint analysis.
bool isBoundsOnly () const
 Returns true if only variable bounds exists, false otherwise.
double maxStep (const Vector &x, const Vector &d, double step) const
 Returns maximum feasible step in interval [0, step] along direction d.
void getActiveIndex (const Vector &xdist, double epsilon, vector< ActiveType > &index) const
 Returns a vector indexing bound type with respect to inequality constraints.
void formDistanceVector (const Vector &x, Vector &xdist) const
 Returns (nullspace projected) distance from x to each inequality constraints.
void snapToBoundary (Vector &x, double esnap) const
 Attempts to find the closest point to x that satisfies all constraints within distance esnap.
void makeBoundsFeasible (Vector &x) const
 Makes x feasible with respect to variable bounds.
void formSnapSystem (const Vector &xtilde, double esnap, Matrix &Asnap, Vector &bsnap) const
 Forms system Asnap, and bsnap. On exit Asnap has full row rank.

Private Member Functions

void error (const string &fname, const string &msg) const
 Print an error message and throw an exception.
void errorCheck () const
 Error checks on input.
Constructor assistance.
void setup (Parameter::List &params)
 Used by constructor to fill the parameter list with appropriate defaults and return the scaling.
void setupBounds (Parameter::List &params)
 Sets up lower and upper bounds.
void setupScaling (Parameter::List &params)
 Sets up scaling vector.
void setupRhs (Parameter::List &params)
 Form the corresponding right-hand side vector of the coefficient matrix.
void setupMatrix (Parameter::List &params)
 Form the coefficient matrix wrt bound and linear constraints.
void setupScaledSystem ()
 Form the corresponding scaled right-hand side vector of the coefficient matrix.
Constraint categorizers.
StateType getIneqState (int i, BoundType bType, const Vector &xTilde, double epsilon=-1) const
 Get state of inequality constraint i with respect to the given point.
StateType getEqState (int i, const Vector &xTilde, double epsilon=-1) const
 Get state of equality constraint i with respect to the given point.
bool isEqualityFeasible (const Vector &xtilde) const
 Returns true if equality constraints are feasible.
bool isInequalityFeasible (const Vector &xtilde) const
 Returns true if inequality constraints are feasible.

Private Attributes

const double epsMach
 Machine epsilon.
bool displayMatrix
Vector scaling
 Scaling.
Vector bLower
 Unscaled lower bounds.
Vector bUpper
 Unscaled upper bounds.
Unscaled-sytem members.
Matrix aIneq
 The coefficient matrix of the unscaled general linear inequality constraints.
Matrix aEq
 The coefficient matrix of unscaled linear equality constraints.
Vector bIneqLower
 The unscaled lower bounds on general linear inequality constraints.
Vector bIneqUpper
 The unscaled upper bounds on general linear inequality constraints.
Vector bEq
 The right-hand side of unscaled equality constraints.
Scaled-sytem members.
Matrix aHat
 The scaled coefficient matrix of the linear (bound and general) inequality constraints.
Vector aHatZNorm
 Holds two norms of rows of aHat projected into the nullspace of the scaled equality constraints.
Vector aHatNorm
 Holds two norms of rows of aHat.
Vector bHatLower
 The scaled lower bounds on the linear (bound and general) inequality constraints.
Vector bHatUpper
 The scaled upper bounds on the linear (bound and general) inequality constraints.
Matrix aTildeEq
 The scaled coefficient matrix of linear equality constraints.
Vector bTildeEq
 The scaled right-hand side of equality coefficient matrix.
Vector lHat
 Used in transforming x to scaled space.

Constructor & Destructor Documentation

APPSPACK::Constraints::Linear::Linear (  Parameter::List &  params  ) 
 

Constructor.

Parameters:
params (input/output) See Linear Constraint Parameters for details of what it should contain. Defaults are inserted for any values that are not defined.

Definition at line 47 of file APPSPACK_Constraints_Linear.cpp.

References errorCheck(), and setup().

APPSPACK::Constraints::Linear::~Linear (   ) 
 

Destructor.

Definition at line 55 of file APPSPACK_Constraints_Linear.cpp.

Member Function Documentation

double APPSPACK::Constraints::Linear::getEpsMach (   )  const
 

Returns machine epsilon value, epsMach.

Definition at line 361 of file APPSPACK_Constraints_Linear.cpp.

Referenced by APPSPACK::Directions::addCompassDirections(), APPSPACK::Directions::addNormalDirections(), APPSPACK::Directions::appendNewDirections(), and APPSPACK::Directions::buildWithLapack().

const APPSPACK::Vector & APPSPACK::Constraints::Linear::getScaling (   )  const
 

Returns scaling vector, scaling.

Definition at line 366 of file APPSPACK_Constraints_Linear.cpp.

Referenced by APPSPACK::Directions::addCompassDirections(), APPSPACK::Directions::addNormalDirections(), APPSPACK::Directions::buildWithCddlib(), APPSPACK::Directions::buildWithLapack(), APPSPACK::Directions::buildWithNothing(), APPSPACK::Directions::generateUnconstrained(), and APPSPACK::Solver::initializeBestPointPtr().

const APPSPACK::Vector & APPSPACK::Constraints::Linear::getLower (   )  const
 

Return vector of lower bounds, bLower.

Definition at line 371 of file APPSPACK_Constraints_Linear.cpp.

const APPSPACK::Vector & APPSPACK::Constraints::Linear::getUpper (   )  const
 

Return vector of upper bounds, bUpper.

Definition at line 376 of file APPSPACK_Constraints_Linear.cpp.

const APPSPACK::Vector & APPSPACK::Constraints::Linear::getBhatLower (   )  const
 

Return lower bound on scaled inequality constraints, bIneqLower.

Definition at line 381 of file APPSPACK_Constraints_Linear.cpp.

const APPSPACK::Vector & APPSPACK::Constraints::Linear::getBhatUpper (   )  const
 

Return upper bound on scaled inequality constraints, bIneqUpper.

Definition at line 386 of file APPSPACK_Constraints_Linear.cpp.

const APPSPACK::Vector & APPSPACK::Constraints::Linear::getBtildeEq (   )  const
 

Return right-hand side vector of scaled equality constraints, bEq.

Definition at line 391 of file APPSPACK_Constraints_Linear.cpp.

const APPSPACK::Matrix & APPSPACK::Constraints::Linear::getAhat (   )  const
 

Return coefficient matrix for scaled inequality constraints, aIneq.

Definition at line 396 of file APPSPACK_Constraints_Linear.cpp.

Referenced by APPSPACK::Directions::buildNormalCone().

const APPSPACK::Matrix & APPSPACK::Constraints::Linear::getAtildeEq (   )  const
 

Return coefficient matrix for scaled equality constraints, aEq.

Definition at line 401 of file APPSPACK_Constraints_Linear.cpp.

Referenced by APPSPACK::Directions::buildNormalCone().

void APPSPACK::Constraints::Linear::getNominalX (  Vector &  x  )  const
 

Returns a point (x) that is initially feasible with respect to the bound constraints.

Note:
This point may not be feasible with respect to the linear constraints.

Definition at line 406 of file APPSPACK_Constraints_Linear.cpp.

References bLower, bUpper, APPSPACK::exists(), APPSPACK::Vector::resize(), scaling, and APPSPACK::Vector::size().

Referenced by APPSPACK::Solver::initializeBestPointPtr().

void APPSPACK::Constraints::Linear::scale (  Vector &  x  )  const
 

Maps x to scaled space via affine linear transformation.

Replaces $x$ with $ S^{-1} (x - \hat{\ell}) $.

Definition at line 422 of file APPSPACK_Constraints_Linear.cpp.

References error(), lHat, scaling, and APPSPACK::Vector::size().

Referenced by formDistanceVector(), isFeasible(), maxStep(), and snapToBoundary().

void APPSPACK::Constraints::Linear::unscale (  Vector &  w  )  const
 

Maps w to unscaled space via affine linear transformation.

Replaces $w$ with $ Sw + \hat{\ell} $.

Definition at line 431 of file APPSPACK_Constraints_Linear.cpp.

References error(), lHat, scaling, and APPSPACK::Vector::size().

Referenced by snapToBoundary().

bool APPSPACK::Constraints::Linear::isFeasible (  const Vector &  x  )  const
 

Return true if feasible, false otherwise.

We consider the point x to be feasible with respect to a given constraint if it is a distance of no more than epsMach away; see getIneqState() and getEqState().

Definition at line 440 of file APPSPACK_Constraints_Linear.cpp.

References error(), isEqualityFeasible(), isInequalityFeasible(), scale(), scaling, and APPSPACK::Vector::size().

Referenced by assertFeasible(), APPSPACK::Solver::generateTrialPoints(), and APPSPACK::Solver::initializeBestPointPtr().

void APPSPACK::Constraints::Linear::assertFeasible (  const Vector &  x  )  const
 

Throws an error if x is infeasible; see isFeasible().

Definition at line 461 of file APPSPACK_Constraints_Linear.cpp.

References error(), and isFeasible().

Referenced by APPSPACK::Solver::generateTrialPoints(), and APPSPACK::Solver::initializeBestPointPtr().

bool APPSPACK::Constraints::Linear::isBoundsOnly (   )  const
 

Returns true if only variable bounds exists, false otherwise.

Definition at line 467 of file APPSPACK_Constraints_Linear.cpp.

References aEq, aIneq, and APPSPACK::Matrix::empty().

double APPSPACK::Constraints::Linear::maxStep (  const Vector &  x,
const Vector &  d,
double  step
)  const
 

Returns maximum feasible step in interval [0, step] along direction d.

Parameters:
x (input) current point
d (input) search direction
step (input) maximum step
On exit a nonnegative scalar $ \alpha $ is returned that gives the maximum feasible step that can be made along direction d. A constraint is said to be a blocking constraint if d points towards its infeasible region. A finite variable lower bound is considered to be a blocking constraint if

\[ d_i < -scaling[i]*\epsilon. \]

Similarly, a finite variable upper bound is considered to be a blocking constraint if

\[ d_i > scaling[i]*\epsilon. \]

A general linear inequality $ a_i^T x \le b_i $ is considered to be a blocking constraint if $ a_i^T d > \epsilon $. Here $\epsilon$ equals the the user modifiable parameter epsMach.

If any blocking inequality constraint is deemed active, via a call to APPSPACK::Constraints::Linear::getIneqState, a value of $ 0$ is returned. Otherwise,

\[ \alpha = {\rm min} \left(\{\Delta\} \cup \left\{\frac{b_i - a_i^T x}{a_i^T d} \Big |\; i \in \mathcal{B}\right\}\right) \]

is returned, where $ \mathcal{B}$ denotes the set of blocking inequality constraints.

Note:
We require that d lie in the null space (numerically at least) with respect to the equality constraints. d is said to lie in the null space if $ a_i^T d < \epsilon$ for all equality constraints. If $ d$ does not lie in the null space, a value of zero is returned.

Definition at line 472 of file APPSPACK_Constraints_Linear.cpp.

References APPSPACK::Constraints::Active, aEq, aIneq, bIneqLower, bIneqUpper, bLower, bUpper, APPSPACK::Matrix::empty(), getIneqState(), APPSPACK::Matrix::getNrows(), APPSPACK::Constraints::Inactive, APPSPACK::Constraints::LowerBound, maxStep(), APPSPACK::Matrix::multVec(), scale(), scaling, APPSPACK::Vector::size(), and APPSPACK::Constraints::UpperBound.

Referenced by APPSPACK::Solver::generateTrialPoints(), and maxStep().

void APPSPACK::Constraints::Linear::getActiveIndex (  const Vector &  xdist,
double  epsilon,
vector< ActiveType > &  index
)  const
 

Returns a vector indexing bound type with respect to inequality constraints.

Parameters:
xdist Records distance to each inequality constraint from a given point. It is assumed that xdist has been formed via a call to formDistanceVector().
epsilon The ith inequality constraint is considered active at its lower bound if

\[ {\rm xdist}(i) < {\rm epsilon}. \]

Similarly, the ith inequality constraint is consider active at its upper bound if

\[ {\rm xdist}(i + m ) < {\rm epsilon}. \]

Here $ m $ denotes the number of rows in $ \hat A^{\rm ineq} $.

index On exit index[i] equals one of the enumeration Constraints::ActiveType.
  • index[i] = NeitherActive if the $i_{ith}$ constraint is inactive at both its lower and upper bounds.
  • index[i] = LowerActive if the $i_{ith}$ constraint is active at its lower bound, but not its upper bound.
  • index[i] = UpperActive if the $i_{ith}$ constraint is active at its upper bound, but not its lower bound.
  • index[i] = BothActive if the $i_{ith}$ constraint is active at both its upper and lower bound.

Definition at line 559 of file APPSPACK_Constraints_Linear.cpp.

References aHat, APPSPACK::Matrix::getNrows(), and APPSPACK::Matrix::resize().

Referenced by APPSPACK::Directions::updateConstraintState().

void APPSPACK::Constraints::Linear::formDistanceVector (  const Vector &  x,
Vector &  xdist
)  const
 

Returns (nullspace projected) distance from x to each inequality constraints.

Parameters:
x (input) A given point.
xdist (output) Gives the distance from x to each inequality constraints when moving within the nullspace of the scaled equality constraints.
Distance is always determined in terms of the scaled system (for a detailed description see Linear):

\[ \hat b^{\rm lower} \le \hat A^{\rm ineq} \tilde x \le \hat b^{\rm upper}. \]

In order to differentiate between lower bounds and upper bounds, the inequality constraints are implicitly stacked as follows:

\[ \left(\begin{array}{c} -\hat A^{\rm ineq} \\ \hat A^{\rm ineq} \end{array}\right) \tilde x \le \left(\begin{array}{c} -\hat b^{\rm lower} \\ \hat b^{\rm upper}\end{array}\right). \]

Thus on exit, the length of xdist is necessarily twice the number of rows in $ \hat A^{\rm ineq} $. If we let

\[ C = \left(\begin{array}{c} -\hat A^{\rm ineq} \\ \hat A^{\rm ineq} \end{array}\right), \; {\rm and } \; d = \left(\begin{array}{c} -\hat b^{\rm lower} \\ \hat b^{\rm upper}\end{array}\right), \]

and let $\varepsilon$ denotes epsMach and $Z$ denotes a matrix whose columns form an orthonormal basis for ${\rm null}(\tilde A^{eq})$, we can define xdist as follows:

If $|d_i| < \infty $the entries of xdist are given by

\[ {\rm xdist}(i) = \left\{ \begin{array}{ll} | c_i^T \tilde x - d_i | / \|Z^T c_i\|_2 & {\rm if } \; \|Z^T c_i\| > \epsilon, \\ 0 & {\rm if } \; \|Z^T c_i \| < \epsilon, \;{\rm and }\; |c_i^T \tilde x - d_i| < \epsilon, \\ \infty & {\rm if } \; \|Z^T c_i \| < \epsilon \;{\rm and }\; |c_i^T \tilde x - d_i| > \epsilon. \\ \end{array} \right. \]

If $|d_i| = \infty$ then ${\rm xdist}(i) = \infty$.

Note:
We are computing distance constrained to movement within the nullspace of the equality constraints. In exact arithmetic, the distance $d(x,a,b)$ from a point $x$ to the constraint $a^T y \le b$ within the space spanned by the orthonormal matrix $Z$ is given by

\[d(x,a,b) = \left\{ \begin{array}{ll} | a^T x - b | / \|Z^T a\|_2 & {\rm if }\; Z^T a \ne 0, \\ 0 & {\rm if } \; Z^T a = 0 \; {\rm and } \; |a^T x - b| = 0, \\ \infty & {\rm if }\; Z^T a = 0 \; {\rm and } \; |a^T x - b| > 0. \\ \end{array} \right. \]

Definition at line 587 of file APPSPACK_Constraints_Linear.cpp.

References aHat, aHatZNorm, bHatLower, bHatUpper, APPSPACK::dne(), APPSPACK::exists(), APPSPACK::Matrix::getNrows(), APPSPACK::Matrix::multVec(), APPSPACK::Vector::resize(), and scale().

Referenced by APPSPACK::Directions::computeNewDirections().

void APPSPACK::Constraints::Linear::snapToBoundary (  Vector &  x,
double  esnap
)  const
 

Attempts to find the closest point to x that satisfies all constraints within distance esnap.

Parameters:
x Current point.
esnap Used to define epsilon ball about x to determine which constraints are nearby.
The primary purpose of this method is to avoid scenarios where 1) the true solution lies on the boundary, and 2) the boundary is is asymptotically being approached but never reached. In order to avoid this "half-stepping" to the boundary, snapToBoundary() attempts to generate the closest point to the current point x that satisfies all constraints lying within the given distance esnap. The method begins by calling findNearbyConstraints() to determine all constraint within esnap of the current point x. A matrix $A_{\rm esnap}$ is then formed that consists of the rows $\tilde A^{Eq} $ followed by the rows of $\hat A $ that correspond to nearby constraints. An LQ factorization of $A_{\rm esnap}$ is then formed to determine a linearly independent subset of $A_{\rm esnap}$. $A_{\rm esnap}$ is then redefined (if necessary) so that $A_{\rm esnap}$ has full row rank. The corresponding right-hand side vector $ b_{\rm esnap}$ is at this time also formed. The solution $ y^\ast $ to the below equality-constrained least-squares problem is then computed:

\[ \begin{array}{cc} minimize & \|y - x\| \\ subject & A_{\rm esnap} y = b_{\rm esnap}. \end{array} \]

On exit, x is set equal to $y^\ast $.

Method requires that APPSPACK be configured with LAPACK.

Definition at line 631 of file APPSPACK_Constraints_Linear.cpp.

References APPSPACK::Matrix::constrainedLSQR(), formSnapSystem(), scale(), and unscale().

Referenced by APPSPACK::Solver::generateTrialPoints(), and APPSPACK::Solver::initializeBestPointPtr().

void APPSPACK::Constraints::Linear::makeBoundsFeasible (  Vector &  x  )  const
 

Makes x feasible with respect to variable bounds.

On exit,

\[x_i = \left \{ \begin{array}{cc} \ell_i & {\rm if } \; x_i < \ell_i \\ u_i & {\rm if } \; x_i > u_i \\ x_i & {\rm otherwise}. \end{array} \right. \]

Here $ \ell $ and $u$ are used to denote the lower and upper bounds of x, respectively.

Definition at line 648 of file APPSPACK_Constraints_Linear.cpp.

References bLower, bUpper, APPSPACK::exists(), and APPSPACK::Vector::size().

Referenced by APPSPACK::Solver::initializeBestPointPtr().

void APPSPACK::Constraints::Linear::formSnapSystem (  const Vector &  xtilde,
double  esnap,
Matrix &  Asnap,
Vector &  bsnap
)  const
 

Forms system Asnap, and bsnap. On exit Asnap has full row rank.

Add more comments

Definition at line 659 of file APPSPACK_Constraints_Linear.cpp.

References APPSPACK::Matrix::addRow(), aHat, aHatNorm, bHatLower, bHatUpper, APPSPACK::Matrix::clear(), APPSPACK::Matrix::empty(), epsMach, APPSPACK::Vector::erase(), APPSPACK::exists(), APPSPACK::Matrix::getNcols(), APPSPACK::Matrix::getNrows(), APPSPACK::Matrix::getRow(), isEqualityFeasible(), APPSPACK::Matrix::multVec(), APPSPACK::Matrix::pruneDependentRows(), APPSPACK::Vector::push_back(), APPSPACK::Vector::resize(), and APPSPACK::Vector::size().

Referenced by snapToBoundary().

void APPSPACK::Constraints::Linear::print (   )  const
 

Prints the bounds, scaling, and general linear constraint information.

Definition at line 738 of file APPSPACK_Constraints_Linear.cpp.

References aEq, aIneq, bEq, bIneqLower, bIneqUpper, bLower, bUpper, APPSPACK::Matrix::empty(), APPSPACK::exists(), scaling, and APPSPACK::Vector::size().

void APPSPACK::Constraints::Linear::setup (  Parameter::List &  params  )  [private]
 

Used by constructor to fill the parameter list with appropriate defaults and return the scaling.

Definition at line 59 of file APPSPACK_Constraints_Linear.cpp.

References setupBounds(), setupMatrix(), setupRhs(), setupScaledSystem(), and setupScaling().

Referenced by Linear().

void APPSPACK::Constraints::Linear::setupBounds (  Parameter::List &  params  )  [private]
 

Sets up lower and upper bounds.

Definition at line 68 of file APPSPACK_Constraints_Linear.cpp.

References APPSPACK::Vector::assign(), bLower, bUpper, APPSPACK::Vector::copyToBool(), APPSPACK::dne(), APPSPACK::Vector::empty(), error(), APPSPACK::exists(), APPSPACK::Parameter::List::getParameter(), APPSPACK::Parameter::List::getVectorParameter(), APPSPACK::Parameter::List::isParameterVector(), scaling, and APPSPACK::Vector::size().

Referenced by setup().

void APPSPACK::Constraints::Linear::setupScaling (  Parameter::List &  params  )  [private]
 

Sets up scaling vector.

Definition at line 151 of file APPSPACK_Constraints_Linear.cpp.

References bLower, bUpper, APPSPACK::Vector::empty(), error(), APPSPACK::exists(), APPSPACK::Parameter::List::getParameter(), APPSPACK::Vector::push_back(), scaling, and APPSPACK::Vector::size().

Referenced by setup().

void APPSPACK::Constraints::Linear::setupRhs (  Parameter::List &  params  )  [private]
 

Form the corresponding right-hand side vector of the coefficient matrix.

Definition at line 195 of file APPSPACK_Constraints_Linear.cpp.

References aEq, aIneq, APPSPACK::Vector::assign(), bEq, bIneqLower, bIneqUpper, APPSPACK::dne(), error(), APPSPACK::Matrix::getNrows(), APPSPACK::Parameter::List::getVectorParameter(), APPSPACK::Parameter::List::isParameterVector(), and APPSPACK::Vector::size().

Referenced by setup().

void APPSPACK::Constraints::Linear::setupMatrix (  Parameter::List &  params  )  [private]
 

Form the coefficient matrix wrt bound and linear constraints.

Definition at line 172 of file APPSPACK_Constraints_Linear.cpp.

References aEq, aIneq, APPSPACK::Matrix::empty(), error(), APPSPACK::Parameter::List::getMatrixParameter(), APPSPACK::Matrix::getNcols(), APPSPACK::Parameter::List::isParameterMatrix(), scaling, and APPSPACK::Vector::size().

Referenced by setup().

void APPSPACK::Constraints::Linear::setupScaledSystem (   )  [private]
 

Form the corresponding scaled right-hand side vector of the coefficient matrix.

Definition at line 226 of file APPSPACK_Constraints_Linear.cpp.

References APPSPACK::Matrix::addMatrix(), aEq, aHat, aHatNorm, aHatZNorm, aIneq, aTildeEq, bEq, bHatLower, bHatUpper, bIneqLower, bIneqUpper, bLower, bTildeEq, bUpper, APPSPACK::dne(), APPSPACK::Matrix::empty(), epsMach, error(), APPSPACK::exists(), APPSPACK::Matrix::getNcols(), APPSPACK::Matrix::getNrows(), APPSPACK::Matrix::getRow(), lHat, APPSPACK::Matrix::multMat(), APPSPACK::Matrix::multVec(), APPSPACK::Vector::norm(), APPSPACK::Matrix::nullSpace(), APPSPACK::Vector::push_back(), APPSPACK::Vector::resize(), APPSPACK::Matrix::scale(), scaling, APPSPACK::Matrix::setToIdentity(), and APPSPACK::Vector::size().

Referenced by setup().

APPSPACK::Constraints::StateType APPSPACK::Constraints::Linear::getIneqState (  int  i,
BoundType  bType,
const Vector &  xTilde,
double  epsilon = -1
)  const [private]
 

Get state of inequality constraint i with respect to the given point.

Computes the state of inequality constraint i with respect to point $ \tilde x $. (It is assumed the point $ \tilde x $ is scaled.)

Constraint i is deemed active if the (scaled) point is within a distance of $\varepsilon$ of the (scaled) constraint. Mathematically speaking, for constraint i with respect to the lower bound, that means

\[ \frac{ | \hat a_i^T \tilde x - \hat b_i^{\rm lower} | } { \| \hat a_i \| } \leq \varepsilon \]

Parameters:
i (input) Constraint index. Let $n$ denote the number of variables, i.e., the size of $ \tilde x $. Let $m$ denote the number of linear inequality constraints, i.e., the number of rows in $A^{\rm ineq}$. Let $p = n + m$. Constraints 0 thru $n-1$ correspond to the bound constraints, and constraints $n$ thru $p-1$ correspond to the linear inequality constraints.
bType (input) Specify upper or lower bound; see BoundType.
xTilde (input) Vector in scaled space.
epsilon (optional input) A point is considered active if it is less than this distance from the constraint (in the scaled space). Defaults to epsMach.

Definition at line 795 of file APPSPACK_Constraints_Linear.cpp.

References aHat, aHatNorm, bHatLower, bHatUpper, APPSPACK::Vector::dot(), APPSPACK::exists(), and APPSPACK::Matrix::getRow().

Referenced by isInequalityFeasible(), and maxStep().

APPSPACK::Constraints::StateType APPSPACK::Constraints::Linear::getEqState (  int  i,
const Vector &  xTilde,
double  epsilon = -1
)  const [private]
 

Get state of equality constraint i with respect to the given point.

Computes the state of equality constraint i with respect to point $ \tilde x $. (It is assumed the point $ \tilde x $ is scaled.)

Constraint i is deemed satisfied if the (scaled) point is within a distance of $\varepsilon$ of the (scaled) constraint. Mathematically speaking, for constraint i with respect to the lower bound, that means

\[ \frac{ | (\tilde a_i^{\rm eq})^T \tilde x - \tilde b_i^{\rm eq} | } { \| \tilde a_i^{\rm eq} \| } \leq \varepsilon \]

Parameters:
i (input) Constraint index. Let $n$ denote the number of variables, i.e., the size of $ \tilde x $. Let $m$ denote the number of linear inequality constraints, i.e., the number of rows in $A^{\rm ineq}$. Let $p = n + m$. Constraints 0 thru $n-1$ correspond to the bound constraints, and constraints $n$ thru $p-1$ correspond to the linear inequality constraints.
xTilde (input) Vector in scaled space.
epsilon (optional input) A point is considered satisfied if it is less than this distance from the constraint (in the scaled space). Defaults to epsMach.

Definition at line 830 of file APPSPACK_Constraints_Linear.cpp.

References aTildeEq, bTildeEq, APPSPACK::Vector::dot(), APPSPACK::Matrix::getRow(), and APPSPACK::Vector::norm().

Referenced by isEqualityFeasible().

bool APPSPACK::Constraints::Linear::isEqualityFeasible (  const Vector &  xtilde  )  const [private]
 

Returns true if equality constraints are feasible.

see getEqState()

Definition at line 855 of file APPSPACK_Constraints_Linear.cpp.

References aTildeEq, getEqState(), APPSPACK::Matrix::getNrows(), and APPSPACK::Constraints::Violated.

Referenced by formSnapSystem(), and isFeasible().

bool APPSPACK::Constraints::Linear::isInequalityFeasible (  const Vector &  xtilde  )  const [private]
 

Returns true if inequality constraints are feasible.

see getIneqState()

Definition at line 868 of file APPSPACK_Constraints_Linear.cpp.

References aHat, getIneqState(), APPSPACK::Matrix::getNrows(), APPSPACK::Constraints::LowerBound, APPSPACK::Constraints::UpperBound, and APPSPACK::Constraints::Violated.

Referenced by isFeasible().

void APPSPACK::Constraints::Linear::error (  const string &  fname,
const string &  msg
)  const [private]
 

Print an error message and throw an exception.

Definition at line 732 of file APPSPACK_Constraints_Linear.cpp.

Referenced by assertFeasible(), errorCheck(), isFeasible(), scale(), setupBounds(), setupMatrix(), setupRhs(), setupScaledSystem(), setupScaling(), and unscale().

void APPSPACK::Constraints::Linear::errorCheck (   )  const [private]
 

Error checks on input.

Definition at line 330 of file APPSPACK_Constraints_Linear.cpp.

References aEq, aIneq, bIneqLower, bIneqUpper, bLower, bUpper, APPSPACK::Matrix::empty(), error(), APPSPACK::exists(), APPSPACK::Matrix::getNrows(), scaling, and APPSPACK::Vector::size().

Referenced by Linear().

Member Data Documentation

const double APPSPACK::Constraints::Linear::epsMach [private]
 

Machine epsilon.

Definition at line 579 of file APPSPACK_Constraints_Linear.hpp.

Referenced by formSnapSystem(), and setupScaledSystem().

bool APPSPACK::Constraints::Linear::displayMatrix [private]
 

If true, equality and inequality constraint information will be printed explicitly for certain debug levels.

Definition at line 584 of file APPSPACK_Constraints_Linear.hpp.

Vector APPSPACK::Constraints::Linear::scaling [private]
 

Scaling.

Definition at line 587 of file APPSPACK_Constraints_Linear.hpp.

Referenced by errorCheck(), getNominalX(), isFeasible(), maxStep(), print(), scale(), setupBounds(), setupMatrix(), setupScaledSystem(), setupScaling(), and unscale().

Vector APPSPACK::Constraints::Linear::bLower [private]
 

Unscaled lower bounds.

Definition at line 590 of file APPSPACK_Constraints_Linear.hpp.

Referenced by errorCheck(), getNominalX(), makeBoundsFeasible(), maxStep(), print(), setupBounds(), setupScaledSystem(), and setupScaling().

Vector APPSPACK::Constraints::Linear::bUpper [private]
 

Unscaled upper bounds.

Definition at line 593 of file APPSPACK_Constraints_Linear.hpp.

Referenced by errorCheck(), getNominalX(), makeBoundsFeasible(), maxStep(), print(),