Actual source code: bqnk.c
petsc-main 2021-02-26
1: #include <../src/tao/bound/impls/bqnk/bqnk.h>
2: #include <petscksp.h>
4: static const char *BQNK_INIT[64] = {"constant", "direction"};
5: static const char *BNK_UPDATE[64] = {"step", "reduction", "interpolation"};
6: static const char *BNK_AS[64] = {"none", "bertsekas"};
8: static PetscErrorCode TaoBQNKComputeHessian(Tao tao)
9: {
10: TAO_BNK *bnk = (TAO_BNK *)tao->data;
11: TAO_BQNK *bqnk = (TAO_BQNK*)bnk->ctx;
13: PetscReal gnorm2, delta;
16: /* Alias the LMVM matrix into the TAO hessian */
17: if (tao->hessian) {
18: MatDestroy(&tao->hessian);
19: }
20: if (tao->hessian_pre) {
21: MatDestroy(&tao->hessian_pre);
22: }
23: PetscObjectReference((PetscObject)bqnk->B);
24: tao->hessian = bqnk->B;
25: PetscObjectReference((PetscObject)bqnk->B);
26: tao->hessian_pre = bqnk->B;
27: /* Update the Hessian with the latest solution */
28: if (bqnk->is_spd) {
29: gnorm2 = bnk->gnorm*bnk->gnorm;
30: if (gnorm2 == 0.0) gnorm2 = PETSC_MACHINE_EPSILON;
31: if (bnk->f == 0.0) {
32: delta = 2.0 / gnorm2;
33: } else {
34: delta = 2.0 * PetscAbsScalar(bnk->f) / gnorm2;
35: }
36: MatLMVMSymBroydenSetDelta(bqnk->B, delta);
37: }
38: MatLMVMUpdate(tao->hessian, tao->solution, bnk->unprojected_gradient);
39: MatLMVMResetShift(tao->hessian);
40: /* Prepare the reduced sub-matrices for the inactive set */
41: MatDestroy(&bnk->H_inactive);
42: if (bnk->active_idx) {
43: MatCreateSubMatrixVirtual(tao->hessian, bnk->inactive_idx, bnk->inactive_idx, &bnk->H_inactive);
44: PCLMVMSetIS(bqnk->pc, bnk->inactive_idx);
45: } else {
46: PetscObjectReference((PetscObject)tao->hessian);
47: bnk->H_inactive = tao->hessian;
48: PCLMVMClearIS(bqnk->pc);
49: }
50: MatDestroy(&bnk->Hpre_inactive);
51: PetscObjectReference((PetscObject)bnk->H_inactive);
52: bnk->Hpre_inactive = bnk->H_inactive;
53: return(0);
54: }
56: static PetscErrorCode TaoBQNKComputeStep(Tao tao, PetscBool shift, KSPConvergedReason *ksp_reason, PetscInt *step_type)
57: {
58: TAO_BNK *bnk = (TAO_BNK *)tao->data;
59: TAO_BQNK *bqnk = (TAO_BQNK*)bnk->ctx;
63: TaoBNKComputeStep(tao, shift, ksp_reason, step_type);
64: if (*ksp_reason < 0) {
65: /* Krylov solver failed to converge so reset the LMVM matrix */
66: MatLMVMReset(bqnk->B, PETSC_FALSE);
67: MatLMVMUpdate(bqnk->B, tao->solution, bnk->unprojected_gradient);
68: }
69: return(0);
70: }
72: PetscErrorCode TaoSolve_BQNK(Tao tao)
73: {
74: TAO_BNK *bnk = (TAO_BNK *)tao->data;
75: TAO_BQNK *bqnk = (TAO_BQNK*)bnk->ctx;
76: Mat_LMVM *lmvm = (Mat_LMVM*)bqnk->B->data;
77: Mat_LMVM *J0;
78: Mat_SymBrdn *diag_ctx;
79: PetscBool flg = PETSC_FALSE;
83: if (!tao->recycle) {
84: MatLMVMReset(bqnk->B, PETSC_FALSE);
85: lmvm->nresets = 0;
86: if (lmvm->J0) {
87: PetscObjectBaseTypeCompare((PetscObject)lmvm->J0, MATLMVM, &flg);
88: if (flg) {
89: J0 = (Mat_LMVM*)lmvm->J0->data;
90: J0->nresets = 0;
91: }
92: }
93: flg = PETSC_FALSE;
94: PetscObjectTypeCompareAny((PetscObject)bqnk->B, &flg, MATLMVMSYMBROYDEN, MATLMVMSYMBADBROYDEN, MATLMVMBFGS, MATLMVMDFP, "");
95: if (flg) {
96: diag_ctx = (Mat_SymBrdn*)lmvm->ctx;
97: J0 = (Mat_LMVM*)diag_ctx->D->data;
98: J0->nresets = 0;
99: }
100: }
101: (*bqnk->solve)(tao);
102: return(0);
103: }
105: PetscErrorCode TaoSetUp_BQNK(Tao tao)
106: {
107: TAO_BNK *bnk = (TAO_BNK *)tao->data;
108: TAO_BQNK *bqnk = (TAO_BQNK*)bnk->ctx;
110: PetscInt n, N;
111: PetscBool is_lmvm, is_sym, is_spd;
114: TaoSetUp_BNK(tao);
115: VecGetLocalSize(tao->solution,&n);
116: VecGetSize(tao->solution,&N);
117: MatSetSizes(bqnk->B, n, n, N, N);
118: MatLMVMAllocate(bqnk->B,tao->solution,bnk->unprojected_gradient);
119: PetscObjectBaseTypeCompare((PetscObject)bqnk->B, MATLMVM, &is_lmvm);
120: if (!is_lmvm) SETERRQ(PetscObjectComm((PetscObject)tao), PETSC_ERR_ARG_INCOMP, "Matrix must be an LMVM-type");
121: MatGetOption(bqnk->B, MAT_SYMMETRIC, &is_sym);
122: if (!is_sym) SETERRQ(PetscObjectComm((PetscObject)tao), PETSC_ERR_ARG_INCOMP, "LMVM matrix must be symmetric");
123: MatGetOption(bqnk->B, MAT_SPD, &is_spd);
124: KSPGetPC(tao->ksp, &bqnk->pc);
125: PCSetType(bqnk->pc, PCLMVM);
126: PCLMVMSetMatLMVM(bqnk->pc, bqnk->B);
127: return(0);
128: }
130: static PetscErrorCode TaoSetFromOptions_BQNK(PetscOptionItems *PetscOptionsObject,Tao tao)
131: {
132: TAO_BNK *bnk = (TAO_BNK *)tao->data;
133: TAO_BQNK *bqnk = (TAO_BQNK*)bnk->ctx;
135: KSPType ksp_type;
138: PetscOptionsHead(PetscOptionsObject,"Quasi-Newton-Krylov method for bound constrained optimization");
139: PetscOptionsEList("-tao_bqnk_init_type", "radius initialization type", "", BQNK_INIT, BQNK_INIT_TYPES, BQNK_INIT[bnk->init_type], &bnk->init_type, NULL);
140: PetscOptionsEList("-tao_bqnk_update_type", "radius update type", "", BNK_UPDATE, BNK_UPDATE_TYPES, BNK_UPDATE[bnk->update_type], &bnk->update_type, NULL);
141: PetscOptionsEList("-tao_bqnk_as_type", "active set estimation method", "", BNK_AS, BNK_AS_TYPES, BNK_AS[bnk->as_type], &bnk->as_type, NULL);
142: PetscOptionsReal("-tao_bqnk_sval", "(developer) Hessian perturbation starting value", "", bnk->sval, &bnk->sval,NULL);
143: PetscOptionsReal("-tao_bqnk_imin", "(developer) minimum initial Hessian perturbation", "", bnk->imin, &bnk->imin,NULL);
144: PetscOptionsReal("-tao_bqnk_imax", "(developer) maximum initial Hessian perturbation", "", bnk->imax, &bnk->imax,NULL);
145: PetscOptionsReal("-tao_bqnk_imfac", "(developer) initial merit factor for Hessian perturbation", "", bnk->imfac, &bnk->imfac,NULL);
146: PetscOptionsReal("-tao_bqnk_pmin", "(developer) minimum Hessian perturbation", "", bnk->pmin, &bnk->pmin,NULL);
147: PetscOptionsReal("-tao_bqnk_pmax", "(developer) maximum Hessian perturbation", "", bnk->pmax, &bnk->pmax,NULL);
148: PetscOptionsReal("-tao_bqnk_pgfac", "(developer) Hessian perturbation growth factor", "", bnk->pgfac, &bnk->pgfac,NULL);
149: PetscOptionsReal("-tao_bqnk_psfac", "(developer) Hessian perturbation shrink factor", "", bnk->psfac, &bnk->psfac,NULL);
150: PetscOptionsReal("-tao_bqnk_pmgfac", "(developer) merit growth factor for Hessian perturbation", "", bnk->pmgfac, &bnk->pmgfac,NULL);
151: PetscOptionsReal("-tao_bqnk_pmsfac", "(developer) merit shrink factor for Hessian perturbation", "", bnk->pmsfac, &bnk->pmsfac,NULL);
152: PetscOptionsReal("-tao_bqnk_eta1", "(developer) threshold for rejecting step (-tao_bqnk_update_type reduction)", "", bnk->eta1, &bnk->eta1,NULL);
153: PetscOptionsReal("-tao_bqnk_eta2", "(developer) threshold for accepting marginal step (-tao_bqnk_update_type reduction)", "", bnk->eta2, &bnk->eta2,NULL);
154: PetscOptionsReal("-tao_bqnk_eta3", "(developer) threshold for accepting reasonable step (-tao_bqnk_update_type reduction)", "", bnk->eta3, &bnk->eta3,NULL);
155: PetscOptionsReal("-tao_bqnk_eta4", "(developer) threshold for accepting good step (-tao_bqnk_update_type reduction)", "", bnk->eta4, &bnk->eta4,NULL);
156: PetscOptionsReal("-tao_bqnk_alpha1", "(developer) radius reduction factor for rejected step (-tao_bqnk_update_type reduction)", "", bnk->alpha1, &bnk->alpha1,NULL);
157: PetscOptionsReal("-tao_bqnk_alpha2", "(developer) radius reduction factor for marginally accepted bad step (-tao_bqnk_update_type reduction)", "", bnk->alpha2, &bnk->alpha2,NULL);
158: PetscOptionsReal("-tao_bqnk_alpha3", "(developer) radius increase factor for reasonable accepted step (-tao_bqnk_update_type reduction)", "", bnk->alpha3, &bnk->alpha3,NULL);
159: PetscOptionsReal("-tao_bqnk_alpha4", "(developer) radius increase factor for good accepted step (-tao_bqnk_update_type reduction)", "", bnk->alpha4, &bnk->alpha4,NULL);
160: PetscOptionsReal("-tao_bqnk_alpha5", "(developer) radius increase factor for very good accepted step (-tao_bqnk_update_type reduction)", "", bnk->alpha5, &bnk->alpha5,NULL);
161: PetscOptionsReal("-tao_bqnk_nu1", "(developer) threshold for small line-search step length (-tao_bqnk_update_type step)", "", bnk->nu1, &bnk->nu1,NULL);
162: PetscOptionsReal("-tao_bqnk_nu2", "(developer) threshold for reasonable line-search step length (-tao_bqnk_update_type step)", "", bnk->nu2, &bnk->nu2,NULL);
163: PetscOptionsReal("-tao_bqnk_nu3", "(developer) threshold for large line-search step length (-tao_bqnk_update_type step)", "", bnk->nu3, &bnk->nu3,NULL);
164: PetscOptionsReal("-tao_bqnk_nu4", "(developer) threshold for very large line-search step length (-tao_bqnk_update_type step)", "", bnk->nu4, &bnk->nu4,NULL);
165: PetscOptionsReal("-tao_bqnk_omega1", "(developer) radius reduction factor for very small line-search step length (-tao_bqnk_update_type step)", "", bnk->omega1, &bnk->omega1,NULL);
166: PetscOptionsReal("-tao_bqnk_omega2", "(developer) radius reduction factor for small line-search step length (-tao_bqnk_update_type step)", "", bnk->omega2, &bnk->omega2,NULL);
167: PetscOptionsReal("-tao_bqnk_omega3", "(developer) radius factor for decent line-search step length (-tao_bqnk_update_type step)", "", bnk->omega3, &bnk->omega3,NULL);
168: PetscOptionsReal("-tao_bqnk_omega4", "(developer) radius increase factor for large line-search step length (-tao_bqnk_update_type step)", "", bnk->omega4, &bnk->omega4,NULL);
169: PetscOptionsReal("-tao_bqnk_omega5", "(developer) radius increase factor for very large line-search step length (-tao_bqnk_update_type step)", "", bnk->omega5, &bnk->omega5,NULL);
170: PetscOptionsReal("-tao_bqnk_mu1", "(developer) threshold for accepting very good step (-tao_bqnk_update_type interpolation)", "", bnk->mu1, &bnk->mu1,NULL);
171: PetscOptionsReal("-tao_bqnk_mu2", "(developer) threshold for accepting good step (-tao_bqnk_update_type interpolation)", "", bnk->mu2, &bnk->mu2,NULL);
172: PetscOptionsReal("-tao_bqnk_gamma1", "(developer) radius reduction factor for rejected very bad step (-tao_bqnk_update_type interpolation)", "", bnk->gamma1, &bnk->gamma1,NULL);
173: PetscOptionsReal("-tao_bqnk_gamma2", "(developer) radius reduction factor for rejected bad step (-tao_bqnk_update_type interpolation)", "", bnk->gamma2, &bnk->gamma2,NULL);
174: PetscOptionsReal("-tao_bqnk_gamma3", "(developer) radius increase factor for accepted good step (-tao_bqnk_update_type interpolation)", "", bnk->gamma3, &bnk->gamma3,NULL);
175: PetscOptionsReal("-tao_bqnk_gamma4", "(developer) radius increase factor for accepted very good step (-tao_bqnk_update_type interpolation)", "", bnk->gamma4, &bnk->gamma4,NULL);
176: PetscOptionsReal("-tao_bqnk_theta", "(developer) trust region interpolation factor (-tao_bqnk_update_type interpolation)", "", bnk->theta, &bnk->theta,NULL);
177: PetscOptionsReal("-tao_bqnk_min_radius", "(developer) lower bound on initial radius", "", bnk->min_radius, &bnk->min_radius,NULL);
178: PetscOptionsReal("-tao_bqnk_max_radius", "(developer) upper bound on radius", "", bnk->max_radius, &bnk->max_radius,NULL);
179: PetscOptionsReal("-tao_bqnk_epsilon", "(developer) tolerance used when computing actual and predicted reduction", "", bnk->epsilon, &bnk->epsilon,NULL);
180: PetscOptionsReal("-tao_bqnk_as_tol", "(developer) initial tolerance used when estimating actively bounded variables", "", bnk->as_tol, &bnk->as_tol,NULL);
181: PetscOptionsReal("-tao_bqnk_as_step", "(developer) step length used when estimating actively bounded variables", "", bnk->as_step, &bnk->as_step,NULL);
182: PetscOptionsInt("-tao_bqnk_max_cg_its", "number of BNCG iterations to take for each Newton step", "", bnk->max_cg_its, &bnk->max_cg_its,NULL);
183: PetscOptionsTail();
184: TaoSetFromOptions(bnk->bncg);
185: TaoLineSearchSetFromOptions(tao->linesearch);
186: KSPSetFromOptions(tao->ksp);
187: KSPGetType(tao->ksp,&ksp_type);
188: PetscStrcmp(ksp_type,KSPNASH,&bnk->is_nash);
189: PetscStrcmp(ksp_type,KSPSTCG,&bnk->is_stcg);
190: PetscStrcmp(ksp_type,KSPGLTR,&bnk->is_gltr);
191: if (bnk->init_type == BNK_INIT_INTERPOLATION) bnk->init_type = BNK_INIT_DIRECTION;
192: MatSetFromOptions(bqnk->B);
193: MatGetOption(bqnk->B, MAT_SPD, &bqnk->is_spd);
194: return(0);
195: }
197: static PetscErrorCode TaoView_BQNK(Tao tao, PetscViewer viewer)
198: {
199: TAO_BNK *bnk = (TAO_BNK*)tao->data;
200: TAO_BQNK *bqnk = (TAO_BQNK*)bnk->ctx;
202: PetscBool isascii;
205: TaoView_BNK(tao, viewer);
206: PetscObjectTypeCompare((PetscObject)viewer,PETSCVIEWERASCII,&isascii);
207: if (isascii) {
208: PetscViewerPushFormat(viewer, PETSC_VIEWER_ASCII_INFO);
209: MatView(bqnk->B, viewer);
210: PetscViewerPopFormat(viewer);
211: }
212: return(0);
213: }
215: static PetscErrorCode TaoDestroy_BQNK(Tao tao)
216: {
217: TAO_BNK *bnk = (TAO_BNK*)tao->data;
218: TAO_BQNK *bqnk = (TAO_BQNK*)bnk->ctx;
222: MatDestroy(&bnk->Hpre_inactive);
223: MatDestroy(&bnk->H_inactive);
224: MatDestroy(&bqnk->B);
225: PetscFree(bnk->ctx);
226: TaoDestroy_BNK(tao);
227: return(0);
228: }
230: PETSC_INTERN PetscErrorCode TaoCreate_BQNK(Tao tao)
231: {
232: TAO_BNK *bnk;
233: TAO_BQNK *bqnk;
237: TaoCreate_BNK(tao);
238: KSPSetOptionsPrefix(tao->ksp, "tao_bqnk_");
239: tao->ops->solve = TaoSolve_BQNK;
240: tao->ops->setfromoptions = TaoSetFromOptions_BQNK;
241: tao->ops->destroy = TaoDestroy_BQNK;
242: tao->ops->view = TaoView_BQNK;
243: tao->ops->setup = TaoSetUp_BQNK;
245: bnk = (TAO_BNK *)tao->data;
246: bnk->computehessian = TaoBQNKComputeHessian;
247: bnk->computestep = TaoBQNKComputeStep;
248: bnk->init_type = BNK_INIT_DIRECTION;
250: PetscNewLog(tao,&bqnk);
251: bnk->ctx = (void*)bqnk;
252: bqnk->is_spd = PETSC_TRUE;
254: MatCreate(PetscObjectComm((PetscObject)tao), &bqnk->B);
255: PetscObjectIncrementTabLevel((PetscObject)bqnk->B, (PetscObject)tao, 1);
256: MatSetOptionsPrefix(bqnk->B, "tao_bqnk_");
257: MatSetType(bqnk->B, MATLMVMSR1);
258: return(0);
259: }
261: /*@
262: TaoGetLMVMMatrix - Returns a pointer to the internal LMVM matrix. Valid
263: only for quasi-Newton family of methods.
265: Input Parameters:
266: . tao - Tao solver context
268: Output Parameters:
269: . B - LMVM matrix
271: Level: advanced
273: .seealso: TAOBQNLS, TAOBQNKLS, TAOBQNKTL, TAOBQNKTR, MATLMVM, TaoSetLMVMMatrix()
274: @*/
275: PetscErrorCode TaoGetLMVMMatrix(Tao tao, Mat *B)
276: {
277: TAO_BNK *bnk = (TAO_BNK*)tao->data;
278: TAO_BQNK *bqnk = (TAO_BQNK*)bnk->ctx;
280: PetscBool flg = PETSC_FALSE;
283: PetscObjectTypeCompareAny((PetscObject)tao, &flg, TAOBQNLS, TAOBQNKLS, TAOBQNKTR, TAOBQNKTL, "");
284: if (!flg) SETERRQ(PetscObjectComm((PetscObject)tao), PETSC_ERR_ARG_INCOMP, "LMVM Matrix only exists for quasi-Newton algorithms");
285: *B = bqnk->B;
286: return(0);
287: }
289: /*@
290: TaoSetLMVMMatrix - Sets an external LMVM matrix into the Tao solver. Valid
291: only for quasi-Newton family of methods.
293: QN family of methods create their own LMVM matrices and users who wish to
294: manipulate this matrix should use TaoGetLMVMMatrix() instead.
296: Input Parameters:
297: + tao - Tao solver context
298: - B - LMVM matrix
300: Level: advanced
302: .seealso: TAOBQNLS, TAOBQNKLS, TAOBQNKTL, TAOBQNKTR, MATLMVM, TaoGetLMVMMatrix()
303: @*/
304: PetscErrorCode TaoSetLMVMMatrix(Tao tao, Mat B)
305: {
306: TAO_BNK *bnk = (TAO_BNK*)tao->data;
307: TAO_BQNK *bqnk = (TAO_BQNK*)bnk->ctx;
309: PetscBool flg = PETSC_FALSE;
312: PetscObjectTypeCompareAny((PetscObject)tao, &flg, TAOBQNLS, TAOBQNKLS, TAOBQNKTR, TAOBQNKTL, "");
313: if (!flg) SETERRQ(PetscObjectComm((PetscObject)tao), PETSC_ERR_ARG_INCOMP, "LMVM Matrix only exists for quasi-Newton algorithms");
314: PetscObjectBaseTypeCompare((PetscObject)B, MATLMVM, &flg);
315: if (!flg) SETERRQ(PetscObjectComm((PetscObject)tao), PETSC_ERR_ARG_INCOMP, "Given matrix is not an LMVM matrix");
316: if (bqnk->B) {
317: MatDestroy(&bqnk->B);
318: }
319: PetscObjectReference((PetscObject)B);
320: bqnk->B = B;
321: return(0);
322: }