Mercurial > octave

comparison scripts/optimization/sqp.m @ 18255:f58a6cd3f909

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
sqp.m: Fix return values in sqp (bug #32008). sqp.m: Create new return value 104 for the situation where the algorithm has not converged but is no longer making progress (stepsize is too small).
author Arun Giridhar <arungiridhar@gmail.com>
date Thu, 19 Dec 2013 19:10:32 -0500
parents d63878346099
children 0e1f5a750d00
comparison
equal deleted inserted replaced
18254:79dc730b92ae 18255:f58a6cd3f909
1 ## Copyright (C) 2005-2013 John W. Eaton 1 ## Copyright (C) 2005-2013 John W. Eaton
2 ## Copyright (C) 2013 Arun Giridhar
2 ## 3 ##
3 ## This file is part of Octave. 4 ## This file is part of Octave.
4 ## 5 ##
5 ## Octave is free software; you can redistribute it and/or modify it 6 ## Octave is free software; you can redistribute it and/or modify it
6 ## under the terms of the GNU General Public License as published by 7 ## under the terms of the GNU General Public License as published by
126 ## 127 ##
127 ## The value returned in @var{info} may be one of the following: 128 ## The value returned in @var{info} may be one of the following:
128 ## 129 ##
129 ## @table @asis 130 ## @table @asis
130 ## @item 101 131 ## @item 101
131 ## The algorithm terminated normally. 132 ## The algorithm terminated normally.
132 ## Either all constraints meet the requested tolerance, or the stepsize, 133 ## All constraints meet the specified tolerance.
134 ##
135 ## @item 102
136 ## The BFGS update failed.
137 ##
138 ## @item 103
139 ## The maximum number of iterations was reached.
140 ##
141 ## @item 104
142 ## The stepsize has become too small, i.e.,
133 ## @tex 143 ## @tex
134 ## $\Delta x,$ 144 ## $\Delta x,$
135 ## @end tex 145 ## @end tex
136 ## @ifnottex 146 ## @ifnottex
137 ## delta @var{x}, 147 ## delta @var{x},
138 ## @end ifnottex 148 ## @end ifnottex
139 ## is less than @code{@var{tol} * norm (x)}. 149 ## is less than @code{@var{tol} * norm (x)}.
140 ##
141 ## @item 102
142 ## The BFGS update failed.
143 ##
144 ## @item 103
145 ## The maximum number of iterations was reached.
146 ## @end table 150 ## @end table
147 ## 151 ##
148 ## An example of calling @code{sqp}: 152 ## An example of calling @code{sqp}:
149 ## 153 ##
150 ## @example 154 ## @example
392 t1 = norm (ce); 396 t1 = norm (ce);
393 t2 = all (ci >= 0); 397 t2 = all (ci >= 0);
394 t3 = all (lambda_i >= 0); 398 t3 = all (lambda_i >= 0);
395 t4 = norm (lambda .* con); 399 t4 = norm (lambda .* con);
396 400
401 ## Normal convergence. All constraints are satisfied
402 ## and objective has converged.
397 if (t2 && t3 && max ([t0; t1; t4]) < tol) 403 if (t2 && t3 && max ([t0; t1; t4]) < tol)
398 info = 101; 404 info = 101;
399 break; 405 break;
400 endif 406 endif
401 407
406 [p, obj_qp, INFO, lambda] = qp (x, B, c, F, g, [], [], d, C, 412 [p, obj_qp, INFO, lambda] = qp (x, B, c, F, g, [], [], d, C,
407 Inf (size (d))); 413 Inf (size (d)));
408 414
409 info = INFO.info; 415 info = INFO.info;
410 416
411 ## FIXME -- check QP solution and attempt to recover if it has 417 ## FIXME: check QP solution and attempt to recover if it has failed.
412 ## failed. For now, just warn about possible problems. 418 ## For now, just warn about possible problems.
413 419
414 id = "Octave:SQP-QP-subproblem"; 420 id = "Octave:SQP-QP-subproblem";
415 switch (info) 421 switch (info)
416 case 2 422 case 2
417 warning (id, "sqp: QP subproblem is non-convex and unbounded"); 423 warning (id, "sqp: QP subproblem is non-convex and unbounded");
451 y -= t; 457 y -= t;
452 endif 458 endif
453 459
454 delx = x_new - x; 460 delx = x_new - x;
455 461
462 ## Check if step size has become too small (indicates lack of progress).
456 if (norm (delx) < tol * norm (x)) 463 if (norm (delx) < tol * norm (x))
457 info = 101; 464 info = 104;
458 break; 465 break;
459 endif 466 endif
460 467
461 if (have_hess) 468 if (have_hess)
462 469
481 488
482 r = theta*y + (1-theta)*B*delx; 489 r = theta*y + (1-theta)*B*delx;
483 490
484 d2 = delxt*r; 491 d2 = delxt*r;
485 492
493 ## Check if the next BFGS update will work properly.
494 ## If d1 or d2 vanish, the BFGS update will fail.
486 if (d1 == 0 || d2 == 0) 495 if (d1 == 0 || d2 == 0)
487 info = 102; 496 info = 102;
488 break; 497 break;
489 endif 498 endif
490 499
508 517
509 # report (iter, qp_iter, alpha, __sqp_nfun__, obj); 518 # report (iter, qp_iter, alpha, __sqp_nfun__, obj);
510 519
511 endwhile 520 endwhile
512 521
522 ## Check if we've spent too many iterations without converging.
513 if (iter >= iter_max) 523 if (iter >= iter_max)
514 info = 103; 524 info = 103;
515 endif 525 endif
516 526
517 nf = globals.nfun; 527 nf = globals.nfun;