Prediction-correction alternating direction method for a class of constrained min-max problems

Abstract

The problems concerned in this paper are a class of constrained min-max problems. By introducing the Lagrange multipliers to the linear constraints, such problems can be solved by some projection type prediction-correction methods. However, to obtain components of the predictor one by one, we use an alternating direction method. And then the new iterate is generated by a minor correction. Global convergence of the proposed method is proved. Finally, numerical results for a constrained single-facility location problem are provided to verify that the new method is effective for some practical problems.

Keywords

nonlinear programming / constrained minimum distance problem / linear variational inequality / projection and contraction methods

References

[1] Christiansen E. Ciarlet P. G., Lions J. L. Limit analysis of collapse states. Handbook of Numerical Analysis, 4, 1996, Amsterdam: North-Holland, 193-312.

[2] Eckstein J. Some saddle-function splitting methods for convex programming. Optim Methods Softw, 1994, 4: 75-83.

[3] Glowinski R. Numerical Methods for Nonlinear Variational Problems, 1984, New York: Springer-Verlag.

[4] Glowinski R., Tallec P. L. Augmented Lagrangian and Operator-splitting Methods in Nonlinear Mechanics. SIAM Studies in Applied Mathematics, 1989, Philadelphia: SIAM.

[5] He B. S., Liao L.-Z., Han D. R. A new inexact alternating directions method for monotone variational inequalities. Math Program, 2002, 92: 103-118.

[6] He B. S., Yang H., Wang S. L. Alternating directions method with self-adaptive penalty parameters for monotone variational inequalities. J Optim Theory Appl, 2000, 106: 349-368.

[7] Kontogiorgis S., Meyer R. R. A variable-penalty alternating directions method for convex optimization. Math Program, 1998, 83: 29-53.

[8] Rockafellar R. T. Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math Oper Res, 1976, 1: 97-116.

[9] Bertsekas D. P., Tsitsiklis J. N. Parallel and Distributed Computation, Numerical Methods, 1989, Englewood Cliffs: Prentice-Hall.

[10] He B. S., Yang Z. H., Yuan X. M. An approximate proximal-extragradient type method for monotone variational inequalities. J Math Anal Appl, 2004, 300: 362-374.

[11] Andersen K. D., Christiansen E. Minimizing a sum of norms subject to linear equality constraints. Comput Optim Appl, 1998, 11: 65-79.

[12] Drezner Z. Facility Location: A Survey of Applications and Methods, 1995, New York: Springer-Verlag.

[13] Klamroth K. Single-facility Location Problems with Barriers, 2002, New York: Springer-Verlag.

[14] Andersen K. D. An efficient Newton barrier method for minimizing a sum of Euclidean norms. SIAM J Optim, 1996, 6(1): 74-95.

[15] Conn A. R. Constrained optimization using a nondifferentiable penalty functions. SIAM J Numer Anal, 1973, 10: 760-784.

[16] Pietrzykowski T. An exact potential method for constrained maxima. SIAM J Numer Anal, 1969, 6: 299-304.