ConstrainedOptPack: C++ Tools for Constrained (and Unconstrained) Optimization  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
ConstrainedOptPack_ConstraintsRelaxedStd.hpp
1 // @HEADER
2 // ***********************************************************************
3 //
4 // Moocho: Multi-functional Object-Oriented arCHitecture for Optimization
5 // Copyright (2003) Sandia Corporation
6 //
7 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
8 // license for use of this work by or on behalf of the U.S. Government.
9 //
10 // Redistribution and use in source and binary forms, with or without
11 // modification, are permitted provided that the following conditions are
12 // met:
13 //
14 // 1. Redistributions of source code must retain the above copyright
15 // notice, this list of conditions and the following disclaimer.
16 //
17 // 2. Redistributions in binary form must reproduce the above copyright
18 // notice, this list of conditions and the following disclaimer in the
19 // documentation and/or other materials provided with the distribution.
20 //
21 // 3. Neither the name of the Corporation nor the names of the
22 // contributors may be used to endorse or promote products derived from
23 // this software without specific prior written permission.
24 //
25 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
26 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
29 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
31 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
32 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
33 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
34 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 //
37 // Questions? Contact Roscoe A. Bartlett (rabartl@sandia.gov)
38 //
39 // ***********************************************************************
40 // @HEADER
41 
42 #ifndef QP_SCHUR_CONSTRAINTS_RELAXED_STD_H
43 #define QP_SCHUR_CONSTRAINTS_RELAXED_STD_H
44 
45 #include <list>
46 
47 #include "ConstrainedOptPack_QPSchur.hpp"
48 #include "AbstractLinAlgPack_MatrixOp.hpp"
49 #include "AbstractLinAlgPack_VectorSpaceBlocked.hpp"
50 
51 namespace ConstrainedOptPack {
52 namespace QPSchurPack {
53 
90 public:
91 
92  // /////////////////////////////////////////////
93  // Public types
94 
105  class MatrixConstraints : public MatrixOp {
106  public:
107 
113 
123  void initialize(
124  const VectorSpace::space_ptr_t &space_d_eta
125  ,const size_type m_in
126  ,const size_type m_eq
127  ,const MatrixOp *E
129  ,const Vector *b
130  ,const MatrixOp *F
132  ,const Vector *f
133  ,size_type m_undecomp
134  ,const size_type j_f_undecomp[]
135  );
136 
139 
141  size_type nd() const
142  { return nd_; }
144  size_type m_in() const
145  { return m_in_; }
147  size_type m_eq() const
148  { return m_eq_; }
150  const MatrixOp* E() const
151  { return E_; }
154  { return trans_E_; }
156  const Vector* b() const
157  { return b_; }
159  const MatrixOp* F() const
160  { return F_; }
163  { return trans_F_; }
165  const Vector* f() const
166  { return f_; }
168  const GenPermMatrixSlice& P_u() const
169  { return P_u_; }
170 
172 
175 
177  const VectorSpace& space_cols() const;
179  const VectorSpace& space_rows() const;
181  MatrixOp& operator=(const MatrixOp& m);
182 // ///
183 // void Mp_StPtMtP(
184 // DMatrixSlice* gms_lhs, value_type alpha
185 // ,const GenPermMatrixSlice& P_rhs1, BLAS_Cpp::Transp P_rhs1_trans
186 // ,BLAS_Cpp::Transp M_trans
187 // ,const GenPermMatrixSlice& P_rhs2, BLAS_Cpp::Transp P_rhs2_trans
188 // ) const ;
190  void Vp_StMtV(
191  VectorMutable* vs_lhs, value_type alpha, BLAS_Cpp::Transp trans_rhs1
192  ,const Vector& vs_rhs2, value_type beta
193  ) const;
195  void Vp_StPtMtV(
196  VectorMutable* vs_lhs, value_type alpha
197  ,const GenPermMatrixSlice& P_rhs1, BLAS_Cpp::Transp P_rhs1_trans
198  ,BLAS_Cpp::Transp M_rhs2_trans
199  ,const SpVectorSlice& sv_rhs3, value_type beta
200  ) const;
201 
203 
204  private:
205  typedef std::vector<size_type> row_i_t;
206  typedef std::vector<size_type> col_j_t;
207  size_type nd_; // # unknowns d
208  size_type m_in_; // # op(E)*d inequality constraints
209  size_type m_eq_; // # op(F)*d equality constraints
210  const MatrixOp *E_; // If NULL then no general inequalities
211  BLAS_Cpp::Transp trans_E_;
212  const Vector *b_;
213  const MatrixOp *F_; // If NULL then no general equalities
214  BLAS_Cpp::Transp trans_F_;
215  const Vector *f_;
216  GenPermMatrixSlice P_u_;
217  row_i_t P_u_row_i_;
218  col_j_t P_u_col_j_;
219  VectorSpace::space_ptr_t space_cols_;
220  VectorSpaceBlocked space_rows_;
221  }; // end class MatrixConstraints
222 
225  ADD_BOUNDS_THEN_MOST_VIOLATED_INEQUALITY
226  ,ADD_BOUNDS_THEN_FIRST_VIOLATED_INEQUALITY
227  ,ADD_MOST_VIOLATED_BOUNDS_AND_INEQUALITY
228  };
229 
232 
235  STANDARD_MEMBER_COMPOSITION_MEMBERS( value_type, bounds_tol );
236 
239  STANDARD_MEMBER_COMPOSITION_MEMBERS( value_type, inequality_tol );
240 
243  STANDARD_MEMBER_COMPOSITION_MEMBERS( value_type, equality_tol );
244 
248 
251 
295  void initialize(
296  const VectorSpace::space_ptr_t &space_d_eta
297  ,value_type etaL
298  ,const Vector *dL
299  ,const Vector *dU
300  ,const MatrixOp *E
301  ,BLAS_Cpp::Transp trans_E
302  ,const Vector *b
303  ,const Vector *eL
304  ,const Vector *eU
305  ,const MatrixOp *F
306  ,BLAS_Cpp::Transp trans_F
307  ,const Vector *f
308  ,size_type m_undecomp
309  ,const size_type j_f_undecomp[]
310  ,VectorMutable *Ed
311  ,bool check_F = true
312  ,value_type bounds_tol = 1e-10
313  ,value_type inequality_tol = 1e-10
314  ,value_type equality_tol = 1e-10
315  );
316 
318  const MatrixConstraints& A_bar_relaxed() const;
319 
321 
324 
326  size_type n() const;
328  size_type m_breve() const;
337  const MatrixOp& A_bar() const;
339  void pick_violated_policy( EPickPolicy pick_policy );
382  void pick_violated(
383  const DVectorSlice& x, size_type* j_viol, value_type* constr_val
384  ,value_type* viol_bnd_val, value_type* norm_2_constr, EBounds* bnd, bool* can_ignore
385  ) const;
387  void ignore( size_type j );
389  value_type get_bnd( size_type j, EBounds bnd ) const;
390 
392 
393 private:
394 
395  // //////////////////////////////
396  // Private types
397 
398  typedef std::list<size_type> passed_over_equalities_t;
399 
400  // //////////////////////////////
401  // Private data members
402 
403  MatrixConstraints A_bar_;
404  value_type etaL_;
405  const Vector *dL_; // If NULL then no simple bounds
406  const Vector *dU_;
407  const Vector *eL_;
408  const Vector *eU_;
409  VectorMutable *Ed_;
410  bool check_F_;
411  mutable size_type last_added_j_; // Remember the last bound added so that
412  mutable value_type last_added_bound_; // we can save our selfs some work.
413  mutable EBounds last_added_bound_type_; // ...
414  mutable size_type next_undecomp_f_k_;
415  // Determines the next constraint [P_u'*op(F)*d + (1 - eta) * P_u'*f](next_undecomp_f_k)
416  // to be checked to see if it is violated. If next_undecomp_f_k > P_u.nz() then all
417  // of the constriants have been checked.
418  mutable passed_over_equalities_t passed_over_equalities_;
419  // This is a list that keeps track of those equality constraints that were checked
420  // for being violated but were within tolerance and therefore passed over and not added.
421  // This list can be traversed again and again to check these constraints. Specifically, the
422  // indexes of f(k) are sorted, not the indexes in P_u'.
423 
424  // //////////////////////////////
425  // Private member functions
426 
428  void cache_last_added(
429  size_type last_added_j, value_type last_added_bound
430  ,EBounds last_added_bound_type
431  ) const;
432 
433 }; // end class ConstraintsRelaxedStd
434 
435 } // end namespace QPSchurPack
436 } // end namespace ConstrainedOptPack
437 
438 #endif // QP_SCHUR_CONSTRAINTS_RELAXED_STD_H
void Vp_StPtMtV(VectorMutable *vs_lhs, value_type alpha, const GenPermMatrixSlice &P_rhs1, BLAS_Cpp::Transp P_rhs1_trans, BLAS_Cpp::Transp M_rhs2_trans, const SpVectorSlice &sv_rhs3, value_type beta) const
void pick_violated(const DVectorSlice &x, size_type *j_viol, value_type *constr_val, value_type *viol_bnd_val, value_type *norm_2_constr, EBounds *bnd, bool *can_ignore) const
Here the next violated constraint to add to the active set is selected.
void initialize(const VectorSpace::space_ptr_t &space_d_eta, const size_type m_in, const size_type m_eq, const MatrixOp *E, BLAS_Cpp::Transp trans_E, const Vector *b, const MatrixOp *F, BLAS_Cpp::Transp trans_F, const Vector *f, size_type m_undecomp, const size_type j_f_undecomp[])
Initialize.
size_t size_type
const MatrixOp & A_bar() const
Represents the constraints matrix.
void Vp_StMtV(VectorMutable *vs_lhs, value_type alpha, BLAS_Cpp::Transp trans_rhs1, const Vector &vs_rhs2, value_type beta) const
void initialize(const VectorSpace::space_ptr_t &space_d_eta, value_type etaL, const Vector *dL, const Vector *dU, const MatrixOp *E, BLAS_Cpp::Transp trans_E, const Vector *b, const Vector *eL, const Vector *eU, const MatrixOp *F, BLAS_Cpp::Transp trans_F, const Vector *f, size_type m_undecomp, const size_type j_f_undecomp[], VectorMutable *Ed, bool check_F=true, value_type bounds_tol=1e-10, value_type inequality_tol=1e-10, value_type equality_tol=1e-10)
Initialize constriants.
Constraints subclass that is used to represent generic varaible bounds, and general inequality and eq...
STANDARD_MEMBER_COMPOSITION_MEMBERS(value_type, bounds_tol)
<<std comp>="">> members for feasibility tolerance for the bound constriants.
Represents the extra constraints in the QP to be satisfied by the schur complement QP solver QPSchur ...
Transp