Condition Class Reference

Condition numbers More...

#include <lurupa/Condition.h>

Collaboration diagram for Condition:

Collaboration graph
[legend]

List of all members.


Public Member Functions

void cond (const Lp *lp, INTERVAL &enclosure)
 Compute verified condition number.
 Condition (Lurupa *lurupa, Report *report)
 Constructor.
void rho_d (const Lp *lp, INTERVAL &enclosure)
 Compute distance to dual infeasibility.
void rho_p (const Lp *lp, INTERVAL &enclosure)
 Compute distance to primal infeasibility.
 ~Condition ()
 Destructor.

Private Member Functions

Lp * generate_lp_rho_d (const Lp *lp)
 Generate lp to compute distance to dual infeasibility.
Lp * generate_lp_rho_p (const Lp *lp)
 Generate lp to compute distance to primal infeasibility.
int norm (const Lp *lp, INTERVAL &enclosure)
 Enclosure of the norm of an lp.
INTERVAL norm_1 (const INTERVAL_VECTOR &ix)
 Enclosure of the 1 norm of a vector.
INTERVAL norm_11 (const INTERVAL_MATRIX &IA, const INTERVAL_MATRIX &IB)
 Enclosure of the 1,1 operator norm of a matrix.
INTERVAL norm_F (const INTERVAL_MATRIX &IA, const INTERVAL_MATRIX &IB)
 Enclosure of the Frobenius norm of a matrix.
INTERVAL norm_L1 (const INTERVAL_MATRIX &IA, const INTERVAL_MATRIX &IB)
 Enclosure of the L1 norm of a matrix.
void rot (int *rg, int i1, int i2, int i3)
 Rotate elements of array.
void swap (int *rg, int i, int iT)
 Swap elements of array.

Private Attributes

Lurupa * lurupa
 Lurupa reference for bound computation.
Report * preport
 Reporting and debugging.

Detailed Description

Condition numbers

This class implements the computation of verified condition numbers. It is based on Ordonez and Freund's [8] linear programming characterization of the condition number. This in turn can be bounded with Lurupa.

Constructor & Destructor Documentation

Condition::Condition ( Lurupa *  lurupa,
Report *  preport 
)

Constructor.

Parameters:
[in] lurupa Lurupa reference for bound computations.
[in] preport Report reference for reporting and debugging.

Member Function Documentation

Lp * Condition::generate_lp_rho_d ( const Lp *  lp  )  [private]

Generate lp to compute distance to dual infeasibility.

Generate the lp to compute the distance to dual infeasibility. Ordonez and Freund's lp (3.15) translates to the following lp. Note the transformation from $p_L$ to $-p_L$.

\begin{align*} &\min && \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} y \\ h_L \\ h_E \\ x \\ p \\ g \end{pmatrix} \\ &s.t. && \begin{pmatrix} -1 & e & e & 0 & 0 & 0 \\ -1 & 0 & 0 & c^T & 0 & 1 \\ -1 & 0 & 0 & -c^T & 0 & -1 \\ 0 & -I & 0 & A & I & 0 \\ 0 & 0 & -I & B & 0 & 0 \\ 0 & -I & 0 & -A & -I & 0 \\ 0 & 0 & -I & -B & 0 & 0 \\ \end{pmatrix} \begin{pmatrix} y \\ h_L \\ h_E \\ x \\ p_L \\ g \end{pmatrix} \le \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} \\ & && x_{L_B} \ge 0, x_{U_B} \le 0 \\ & && p \ge 0, g \ge 0 \\ & && y, h_L, h_E \ge 0 \\ \end{align*}

References Lp::free_variables, Lp::free_variables_size, Lp::ia, Lp::IA, Lp::ib, Lp::IB, Lp::ic, Lp::infinite, Lp::ix, Lp::iy, Lp::iz, Lp::lurupa, Lp::maximize, Lp::name, Lp::non_fixed_vars, Lp::xl, and Lp::xu.

Referenced by rho_d().

Lp * Condition::generate_lp_rho_p ( const Lp *  lp  )  [private]

Generate lp to compute distance to primal infeasibility.

Generate the lp to compute the distance to primal infeasibility. Ordonez and Freund's lp (3.14) translates to the following lp. Note the transformation from $y_L$ to $-y_L$.

\begin{align*} &\min && \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} \begin{pmatrix} x \\ h \\ y_L \\ y_E \\ v \\ s^+ \\ s^- \end{pmatrix} \\ &s.t. && \begin{pmatrix} -1 & e & 0 & 0 & 0 & 0 & 0 \\ -1 & 0 & -a^T & b^T & -1 & 0 & 0 \\ -1 & 0 & a^T & -b^T & 1 & 0 & 0 \\ 0 & -I & -A^T & B^T & 0 & I & -I \\ 0 & -I & A^T & -B^T & 0 & -I & I \\ 0 & 0 & 0 & 0 & -1 & -\underline{x}^T & +\overline{x}^T \\ \end{pmatrix} \begin{pmatrix} x \\ h \\ y_L \\ y_E \\ v \\ s^+ \\ s^- \end{pmatrix} \le \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} \\ & && x, h, y_L, s_{L_B}^+, s_{U_B}^- \ge 0 \\ & && s_{N \setminus L_B}^+, s_{N \setminus U_B}^- = 0 \end{align*}

References Lp::free_variables, Lp::free_variables_size, Lp::ia, Lp::IA, Lp::ib, Lp::IB, Lp::ic, Lp::infinite, Lp::ix, Lp::iy, Lp::iz, Lp::lurupa, Lp::maximize, Lp::name, Lp::non_fixed_vars, Lp::xl, and Lp::xu.

Referenced by rho_p().

int Condition::norm ( const Lp *  lp,
INTERVAL &  enclosure 
) [private]

Enclosure of the norm of an lp.

Compute an enclosure of the norm of lp. This is bounded by

References Lp::IA, Lp::ia, Lp::IB, Lp::ib, Lp::ic, Lp::ix, norm_1(), norm_11(), norm_F(), norm_L1(), preport, and Report::print().

Referenced by cond().

INTERVAL Condition::norm_1 ( const INTERVAL_VECTOR &  ix  )  [private]

Enclosure of the 1 norm of a vector.

Compute an enclosure of the 1 norm of ix.

Parameters:
[in] ix the vector
Returns:
the norm enclosure

References Lp::ix.

Referenced by norm(), norm_11(), and norm_L1().

INTERVAL Condition::norm_11 ( const INTERVAL_MATRIX &  IA,
const INTERVAL_MATRIX &  IB 
) [private]

Enclosure of the 1,1 operator norm of a matrix.

Compute an enclosure of the 1,1 norm of the matrix

\[ \left\| \begin{pmatrix} A\\B \end{pmatrix} \right\| := \text{max}_j \left\| \begin{pmatrix} A\\B \end{pmatrix}_{:j} \right\|_1. \]

Parameters:
[in] IA upper part of the matrix
[in] IB lower part of the matrix
Returns:
the norm enclosure

References norm_1().

Referenced by norm().

INTERVAL Condition::norm_F ( const INTERVAL_MATRIX &  IA,
const INTERVAL_MATRIX &  IB 
) [private]

Enclosure of the Frobenius norm of a matrix.

Compute an enclosure of the Frobenius norm of the matrix $\left( \begin{smallmatrix} A\\B \end{smallmatrix} \right) $.

Parameters:
[in] IA upper part of the matrix
[in] IB lower part of the matrix
Returns:
the norm enclosure

Referenced by norm().

INTERVAL Condition::norm_L1 ( const INTERVAL_MATRIX &  IA,
const INTERVAL_MATRIX &  IB 
) [private]

Enclosure of the L1 norm of a matrix.

Compute an enclosure of the L1 norm of the matrix $\left( \begin{smallmatrix} A\\B \end{smallmatrix} \right) $.

Parameters:
[in] IA upper part of the matrix
[in] IB lower part of the matrix
Returns:
the norm enclosure

References norm_1().

Referenced by norm().

void Condition::rho_d ( const Lp *  lp,
INTERVAL &  enclosure 
)

Compute distance to dual infeasibility.

Compute distance to dual infeasibility $\rho_d$. Consists of the following steps:

  • generate new lp
  • tell module to transform lp to solver representation
  • iterate over i/j settings maintaining enclosure of optimal value, i.e.,
    • set x_i = j
    • compute lower/upper bound
    • update enclosure, set to smallest lower/upper bound

Parameters:
[in] lp Lp to compute distance to primal infeasibility for
[out] enclosure Enclosure of distance to primal infeasibility

References Lp::free_variables, Lp::free_variables_size, generate_lp_rho_d(), Lp::IA, Lp::IB, Lp::infinite, Lp::ix, Lurupa::lower_bound(), Solver_module_interface::lp2solver, lurupa, Lp::non_fixed_vars, preport, Report::print(), Solver_module_interface::set_bounds, Lurupa::solve_lp(), Lurupa::solver_module, swap(), Lurupa::upper_bound(), Lp::xl, and Lp::xu.

Referenced by cond(), and Lurupa::rho_d().

void Condition::rho_p ( const Lp *  lp,
INTERVAL &  enclosure 
)

Compute distance to primal infeasibility.

Compute distance to primal infeasibility $\rho_p$. Consists of the following steps:

  • generate new lp
  • tell module to transform lp to solver representation
  • iterate over i/j settings maintaining enclosure of optimal value, i.e.,
    • set y_i = j
    • compute lower/upper bound
    • update enclosure, set to smallest lower/upper bound

Parameters:
[in] lp Lp to compute distance to primal infeasibility for
[out] enclosure Enclosure of distance to primal infeasibility

References Lp::free_variables, Lp::free_variables_size, generate_lp_rho_p(), Lp::IA, Lp::IB, Lp::infinite, Lp::ix, Lurupa::lower_bound(), Solver_module_interface::lp2solver, lurupa, Lp::non_fixed_vars, preport, Report::print(), rot(), Solver_module_interface::set_bounds, Lurupa::solve_lp(), Lurupa::solver_module, swap(), Lurupa::upper_bound(), Lp::xl, and Lp::xu.

Referenced by cond(), and Lurupa::rho_p().

void Condition::rot ( int *  rg,
int  i1,
int  i2,
int  i3 
) [private]

Rotate elements of array.

Rotate the elements with index i1, i2 and i3 of array rg clockwise.

Parameters:
[in,out] rg the array
[in] i1 index to rotate
[in] i2 index to rotate
[in] i3 index to rotate

References swap().

Referenced by rho_p().

void Condition::swap ( int *  rg,
int  i,
int  iT 
) [private]

Swap elements of array.

Swap the elements with index i and iT of array rg.

Parameters:
[in,out] rg the array
[in] i index to swap
[in] iT index to swap

Referenced by rho_d(), rho_p(), and rot().

The documentation for this class was generated from the following files:
Generated on Thu Jun 26 18:08:54 2008 for Lurupa by  doxygen 1.5.6