source: branches/dev/Algorithm/IpRestoMinC_1Nrm.cpp @ 546

Last change on this file since 546 was 546, checked in by andreasw, 15 years ago
  • added missing svn:keyword for a few files
  • increased factor for theta reduction in restoration convergence check from 1e1 to 1e2
  • trigger restoration phase in expect_infeasible_problem mode if multipliers become larger than 1e8
  • revert to regular restoration phase if more than max_soft_resto_iters (new option) iterations are taken in soft restoration phase
  • made quality_function default for adaptive barrier strategy
  • added new print level to avoid one line of output per iteration
  • fixed TNLPAdapter, so that only some parts of the problem (objective, constraints, variables) are scaled if desired
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 12.7 KB
Line 
1// Copyright (C) 2004, 2005 International Business Machines and others.
2// All Rights Reserved.
3// This code is published under the Common Public License.
4//
5// $Id: IpRestoMinC_1Nrm.cpp 546 2005-10-20 22:40:15Z andreasw $
6//
7// Authors:  Carl Laird, Andreas Waechter     IBM    2004-08-13
8
9#include "IpRestoMinC_1Nrm.hpp"
10#include "IpCompoundVector.hpp"
11#include "IpRestoIpoptNLP.hpp"
12#include "IpDefaultIterateInitializer.hpp"
13
14namespace Ipopt
15{
16#ifdef IP_DEBUG
17  static const Index dbg_verbosity = 0;
18#endif
19
20  MinC_1NrmRestorationPhase::MinC_1NrmRestorationPhase
21  (IpoptAlgorithm& resto_alg,
22   const SmartPtr<EqMultiplierCalculator>& eq_mult_calculator)
23      :
24      resto_alg_(&resto_alg),
25      eq_mult_calculator_(eq_mult_calculator),
26      resto_options_(NULL)
27  {
28    DBG_ASSERT(IsValid(resto_alg_));
29  }
30
31  MinC_1NrmRestorationPhase::~MinC_1NrmRestorationPhase()
32  {}
33
34  void MinC_1NrmRestorationPhase::RegisterOptions(SmartPtr<RegisteredOptions> roptions)
35  {
36    roptions->AddLowerBoundedNumberOption(
37      "bound_mult_reset_threshold",
38      "Threshold for resetting bound multipliers after the restoration phase.",
39      0.0, false,
40      1e3,
41      "After returning from the restoration phase, the bound multipliers are "
42      "updated with a Newton step for complementarity.  Here, the "
43      "change in the primal variables during the entire restoration "
44      "phase is taken to be the corresponding primal Newton step. "
45      "However, if after the update the largest bound multiplier "
46      "exceeds the threshold specified by this option, the multipliers "
47      "are all reset to 1.");
48    roptions->AddLowerBoundedNumberOption(
49      "constr_mult_reset_threshold",
50      "Threshold for resetting equality and inequality multipliers after restoration phase.",
51      0.0, false,
52      0e3,
53      "After returning from the restoration phase, the constraint multipliers "
54      "are recomputed by a least square estimate.  This option triggers when "
55      "those least-square esimates should be ignored.");
56  }
57
58  bool MinC_1NrmRestorationPhase::InitializeImpl(const OptionsList& options,
59      const std::string& prefix)
60  {
61    // keep a copy of these options to use when setting up the
62    // restoration phase
63    resto_options_ = new OptionsList(options);
64
65    options.GetNumericValue("constr_mult_reset_threshold",
66                            constr_mult_reset_threshold_,
67                            prefix);
68    options.GetNumericValue("bound_mult_reset_threshold",
69                            bound_mult_reset_threshold_,
70                            prefix);
71    options.GetBoolValue("expect_infeasible_problem",
72                         expect_infeasible_problem_,
73                         prefix);
74
75    // Avoid that the restoration phase is trigged by user option in
76    // first iteration of the restoration phase
77    resto_options_->SetStringValue("resto.start_with_resto", "no");
78
79    // We want the default for the theta_max_fact in the restoration
80    // phase higher than for the regular phase
81    Number theta_max_fact;
82    if (!options.GetNumericValue("resto.theta_max_fact",
83                                 theta_max_fact, "")) {
84      resto_options_->SetNumericValue("resto.theta_max_fact", 1e8);
85    }
86
87    count_restorations_ = 0;
88
89    bool retvalue = true;
90    if (IsValid(eq_mult_calculator_)) {
91      retvalue = eq_mult_calculator_->Initialize(Jnlst(), IpNLP(), IpData(),
92                 IpCq(), options, prefix);
93    }
94    return retvalue;
95  }
96
97  bool
98  MinC_1NrmRestorationPhase::PerformRestoration()
99  {
100    DBG_START_METH("MinC_1NrmRestorationPhase::PerformRestoration",
101                   dbg_verbosity);
102
103    // Increase counter for restoration phase calls
104    count_restorations_++;
105    Jnlst().Printf(J_DETAILED, J_MAIN,
106                   "Starting Restoration Phase for the %d. time\n",
107                   count_restorations_);
108
109    DBG_ASSERT(IpCq().curr_constraint_violation()>0.);
110
111    // ToDo set those up during initialize?
112    // Create the restoration phase NLP etc objects
113    SmartPtr<IpoptData> resto_ip_data = new IpoptData();
114    SmartPtr<IpoptNLP> resto_ip_nlp =
115      new RestoIpoptNLP(IpNLP(), IpData(), IpCq());
116    SmartPtr<IpoptCalculatedQuantities> resto_ip_cq =
117      new IpoptCalculatedQuantities(resto_ip_nlp, resto_ip_data);
118
119    // Determine if this is a square problem
120    bool square_problem = IpCq().IsSquareProblem();
121
122    // Decide if we want to use the original option or want to make
123    // some changes
124    SmartPtr<OptionsList> actual_resto_options = resto_options_;
125    if(square_problem) {
126      actual_resto_options = new OptionsList(*resto_options_);
127      // If this is a square problem, the want the restoration phase
128      // never to be left until the problem is converged
129      actual_resto_options->SetNumericValue("resto.required_infeasibility_reduction", 0.);
130    }
131    else if (expect_infeasible_problem_ && count_restorations_==1) {
132      if (IpCq().curr_constraint_violation()>1e-3) {
133        actual_resto_options = new OptionsList(*resto_options_);
134        // Ask for significant reduction of infeasibility, in the hope
135        // that we do not return from the restoration phase is the
136        // problem is infeasible
137        actual_resto_options->SetNumericValue("resto.required_infeasibility_reduction", 1e-3);
138      }
139    }
140
141    // Initialize the restoration phase algorithm
142    resto_alg_->Initialize(Jnlst(), *resto_ip_nlp, *resto_ip_data,
143                           *resto_ip_cq, *actual_resto_options, "resto.");
144
145    // Set iteration counter and info field for the restoration phase
146    resto_ip_data->Set_iter_count(IpData().iter_count()+1);
147    resto_ip_data->Set_info_regu_x(IpData().info_regu_x());
148    resto_ip_data->Set_info_alpha_primal(IpData().info_alpha_primal());
149    resto_ip_data->Set_info_alpha_primal_char(IpData().info_alpha_primal_char());
150    resto_ip_data->Set_info_alpha_dual(IpData().info_alpha_dual());
151    resto_ip_data->Set_info_ls_count(IpData().info_ls_count());
152
153    // Call the optimization algorithm to solve the restoration phase
154    // problem
155    SolverReturn resto_status   = resto_alg_->Optimize();
156
157    int retval=-1;
158
159    if (resto_status == SUCCESS) {
160      if (Jnlst().ProduceOutput(J_DETAILED, J_LINE_SEARCH)) {
161        Jnlst().Printf(J_DETAILED, J_LINE_SEARCH,
162                       "\nRESTORATION PHASE RESULTS\n");
163        Jnlst().Printf(J_DETAILED, J_LINE_SEARCH,
164                       "\n\nOptimal solution found! \n");
165        Jnlst().Printf(J_DETAILED, J_LINE_SEARCH,
166                       "Optimal Objective Value = %.16E\n", resto_ip_cq->curr_f());
167        Jnlst().Printf(J_DETAILED, J_LINE_SEARCH,
168                       "Number of Iterations = %d\n", resto_ip_data->iter_count());
169      }
170      if (Jnlst().ProduceOutput(J_VECTOR, J_LINE_SEARCH)) {
171        resto_ip_data->curr()->Print(Jnlst(), J_VECTOR, J_LINE_SEARCH, "curr");
172      }
173
174      retval = 0;
175    }
176    else if (resto_status == STOP_AT_TINY_STEP ||
177             resto_status == STOP_AT_ACCEPTABLE_POINT) {
178      Number orig_primal_inf =
179        IpCq().curr_primal_infeasibility(NORM_MAX);
180      // ToDo make the factor in following line an option
181      if (orig_primal_inf <= 1e2*IpData().tol()) {
182        THROW_EXCEPTION(RESTORATION_CONVERGED_TO_FEASIBLE_POINT,
183                        "Restoration phase converged to a point with small primal infeasibility");
184      }
185      else {
186        THROW_EXCEPTION(LOCALLY_INFEASIBLE,
187                        "Restoration phase converged to a point of local infeasibility");
188      }
189    }
190    else if (resto_status == MAXITER_EXCEEDED) {
191      THROW_EXCEPTION(IpoptException, "Maximal number of iterations exceeded in restoration phase.");
192      retval = 1;
193    }
194    else if (resto_status == LOCAL_INFEASIBILITY) {
195      // converged to locally infeasible point - pass this on to the outer algorithm...
196      THROW_EXCEPTION(LOCALLY_INFEASIBLE, "Restoration phase converged to a point of local infeasibility");
197    }
198    else if (resto_status == RESTORATION_FAILURE) {
199      THROW_EXCEPTION(RESTORATION_FAILED, "Restoration phase in the restoration phase failed.");
200    }
201    else {
202      Jnlst().Printf(J_ERROR, J_MAIN, "Sorry, things failed ?!?!\n");
203      retval = 1;
204    }
205
206    if (retval == 0) {
207      // Copy the results into the trial fields;. They will be
208      // accepted later in the full algorithm
209      SmartPtr<const CompoundVector> cx =
210        dynamic_cast<const CompoundVector*>(GetRawPtr(resto_ip_data->curr()->x()));
211      DBG_ASSERT(IsValid(cx));
212      SmartPtr<IteratesVector> trial = IpData().trial()->MakeNewContainer();
213      trial->Set_primal(*cx->GetComp(0), *resto_ip_data->curr()->s());
214      IpData().set_trial(trial);
215
216      // If this is a square problem, we are done because a
217      // sufficiently feasible point has been found
218      if (square_problem) {
219        Jnlst().Printf(J_DETAILED, J_LINE_SEARCH,
220                       "Recursive restoration phase algorithm termined successfully for square problem.\n");
221        IpData().AcceptTrialPoint();
222        THROW_EXCEPTION(FEASIBILITY_PROBLEM_SOLVED, "Restoration phase converged to sufficiently feasible point of original square problem.");
223      }
224
225      // Update the bound multiplers, pretending that the entire
226      // progress in x and s in the restoration phase has been one
227      // [rimal-dual Newton step (and therefore the result of solving
228      // an augmented system)
229      SmartPtr<IteratesVector> delta = IpData().curr()->MakeNewIteratesVector(true);
230      delta->Set(0.0);
231      ComputeBoundMultiplierStep(*delta->z_L_NonConst(), *IpData().curr()->z_L(),
232                                 *IpCq().curr_slack_x_L(),
233                                 *IpCq().trial_slack_x_L());
234      ComputeBoundMultiplierStep(*delta->z_U_NonConst(), *IpData().curr()->z_U(),
235                                 *IpCq().curr_slack_x_U(),
236                                 *IpCq().trial_slack_x_U());
237      ComputeBoundMultiplierStep(*delta->v_L_NonConst(), *IpData().curr()->v_L(),
238                                 *IpCq().curr_slack_s_L(),
239                                 *IpCq().trial_slack_s_L());
240      ComputeBoundMultiplierStep(*delta->v_U_NonConst(), *IpData().curr()->v_U(),
241                                 *IpCq().curr_slack_s_U(),
242                                 *IpCq().trial_slack_s_U());
243
244      DBG_PRINT_VECTOR(1, "delta_z_L", *delta->z_L());
245      DBG_PRINT_VECTOR(1, "delta_z_U", *delta->z_U());
246      DBG_PRINT_VECTOR(1, "delta_v_L", *delta->v_L());
247      DBG_PRINT_VECTOR(1, "delta_v_U", *delta->v_U());
248
249      Number alpha_dual = IpCq().dual_frac_to_the_bound(IpData().curr_tau(),
250                          *delta->z_L_NonConst(),
251                          *delta->z_U_NonConst(),
252                          *delta->v_L_NonConst(),
253                          *delta->v_U_NonConst());
254      Jnlst().Printf(J_DETAILED, J_LINE_SEARCH,
255                     "Step size for bound multipliers: %8.2e\n", alpha_dual);
256
257      IpData().SetTrialBoundMultipliersFromStep(alpha_dual, *delta->z_L(), *delta->z_U(), *delta->v_L(), *delta->v_U() );
258
259      // ToDo: Check what to do here:
260      Number bound_mult_max = Max(IpData().trial()->z_L()->Amax(),
261                                  IpData().trial()->z_U()->Amax(),
262                                  IpData().trial()->v_L()->Amax(),
263                                  IpData().trial()->v_U()->Amax());
264      if (bound_mult_max > bound_mult_reset_threshold_) {
265        trial = IpData().trial()->MakeNewContainer();
266        Jnlst().Printf(J_DETAILED, J_LINE_SEARCH,
267                       "Bound multipliers after restoration phase too large (max=%8.2e). Set all to 1.\n",
268                       bound_mult_max);
269        trial->create_new_z_L();
270        trial->create_new_z_U();
271        trial->create_new_v_L();
272        trial->create_new_v_U();
273        trial->z_L_NonConst()->Set(1.0);
274        trial->z_U_NonConst()->Set(1.0);
275        trial->v_L_NonConst()->Set(1.0);
276        trial->v_U_NonConst()->Set(1.0);
277        IpData().set_trial(trial);
278
279      }
280
281      DefaultIterateInitializer::least_square_mults(
282        Jnlst(), IpNLP(), IpData(), IpCq(),
283        eq_mult_calculator_, constr_mult_reset_threshold_);
284
285      DBG_PRINT_VECTOR(2, "y_c", *IpData().curr()->y_c());
286      DBG_PRINT_VECTOR(2, "y_d", *IpData().curr()->y_d());
287
288      IpData().Set_iter_count(resto_ip_data->iter_count()-1);
289      // Skip the next line, because it would just replicate the first
290      // on during the restoration phase.
291      IpData().Set_info_skip_output(true);
292    }
293
294    return (retval == 0);
295  }
296
297  void MinC_1NrmRestorationPhase::ComputeBoundMultiplierStep(Vector& delta_z,
298      const Vector& curr_z,
299      const Vector& curr_slack,
300      const Vector& trial_slack)
301  {
302    Number mu = IpData().curr_mu();
303
304    delta_z.Copy(curr_slack);
305    delta_z.Axpy(-1., trial_slack);
306    delta_z.ElementWiseMultiply(curr_z);
307    delta_z.AddScalar(mu);
308    delta_z.ElementWiseDivide(curr_slack);
309    delta_z.Axpy(-1., curr_z);
310  }
311
312} // namespace Ipopt
Note: See TracBrowser for help on using the repository browser.