×

zbMATH — the first resource for mathematics

An augmented Lagrangian method for a class of Inverse quadratic programming problems. (English) Zbl 1201.90152
The article considers an inverse quadratic optimization problem in which the coefficients of a quadratic objective function are adjusted as little as possible so that a known feasible solution becomes optimal. The problem is formulated as a minimization problem with a positive semidefinite cone constraint. Its dual is a linearly constrained semismoothly differentiable convex optimization problem with fewer variables than the original one.
Global convergence of the augmented Lagrangian method for the dual problem is demonstrated, and convergence rates for primal and dual iterates are established. As the objective function of the dual problem is only semismoothly differentiable, the analysis requires extensive tools. The semismooth Newton method with Armijo line search is applied to solve the subproblems in the augmented Lagrange approach, which is proven to have global convergence and local quadratic rate. Numerical results illustrate the performance of the proposed method.

MSC:
90C22 Semidefinite programming
90C31 Sensitivity, stability, parametric optimization
90C20 Quadratic programming
49M29 Numerical methods involving duality
PDF BibTeX Cite
Full Text: DOI
References:
[1] Ahuja, R.K., Orlin, J.B.: Inverse optimization. Oper. Res. 49, 771–183 (2001) · Zbl 1163.90764
[2] Ahuja, R.K., Orlin, J.B.: Combinatorial algorithms for inverse network flow problems. Networks 40, 181–187 (2002) · Zbl 1026.90089
[3] Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Academic Press, New York (1982) · Zbl 0572.90067
[4] Burkard, R.E., Lin, Y., Zhang, J.: Weight reduction problems with certain bottleneck objectives. Eur. J. Oper. Res. 153, 191–199 (2004) · Zbl 1137.90689
[5] Burton, W.R., Toint, Ph.L.: On an instance of the inverse shortest paths problem. Math. Program. 53, 45–61 (1992) · Zbl 0756.90089
[6] Cai, M.C., Yang, X.G., Zhang, J.: The complexity analysis of the inverse center location problem. J. Global Optim. 15, 213–218 (1999) · Zbl 0978.90065
[7] Carr, S., Lovejoy, W.: The inverse newsvendor problem: choosing an optimal demand portfolio for capacitated resources. Manag. Sci. 46, 912–927 (2000) · Zbl 1231.90015
[8] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983) · Zbl 0582.49001
[9] Dembo, R., Rosen, D.: The practice of portfolio replication: a practical overview of forward and inverse problems. Ann. Oper. Res. 85, 267–284 (1999) · Zbl 0920.90006
[10] Facchinei, F.: Minimization of SC 1 functions and the Maratos effect. Oper. Res. Lett. 17, 131–137 (1995) · Zbl 0843.90108
[11] Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. I. Springer, New York (2003) · Zbl 1062.90002
[12] Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vol. II. Springer, New York (2003) · Zbl 1062.90002
[13] Golshtein, E.G., Tretyakov, N.V.: Modified Lagrangians and Monotone Maps in Optimization. Wiley, New York (1989) · Zbl 0848.49001
[14] Hartley, M.J., Bakshi, G.S.: Markowitz models of portfolio selection: the inverse problem. (October 1998)
[15] Heuberger, C.: Inverse combinatorial optimization: a survey on problems, methods and results. J. Comb. Optim. 8, 329–361 (2004) · Zbl 1084.90035
[16] Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms. Springer, Berlin (1993)
[17] Hiriart-Urruty, J.-B., Strodiot, J.J., Nguyen, V.H.: Generalized Hessian matrix and second-order optimality conditions for problems with C1,1 data. Appl. Math. Optim. 11, 43–56 (1984) · Zbl 0542.49011
[18] Iyengar, G., Kang, W.: Inverse conic programming and applications. Oper. Res. Lett. 33, 319–330 (2005) · Zbl 1140.90465
[19] Malick, J.: A dual approach to semidefinite least-squares problems. SIAM J. Matrix Anal. Appl. 26(1), 272–284 (2004) · Zbl 1080.65027
[20] Mifflin, R.: Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim. 15, 957–972 (1977) · Zbl 0376.90081
[21] Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353–367 (1993) · Zbl 0780.90090
[22] Rockafellar, R.T.: A dual approach to solving nonlinear programming problems by unconstrained optimization. Math. Program. 5, 354–373 (1973) · Zbl 0279.90035
[23] Rockafellar, R.T.: The multiplier method of Hestenes and Powell applied to convex programming. J. Optim. Theory Appl. 12, 555–562 (1973) · Zbl 0254.90045
[24] Rockafellar, R.T.: Conjugate Duality and Optimization. SIAM, Philadelphia (1974) · Zbl 0296.90036
[25] Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, New York (1998)
[26] Shapiro, A.: On concepts of directional differentiability. J. Optim. Theory Appl. 66, 477–487 (1990) · Zbl 0682.49015
[27] Sun, D., Sun, J.: Semismooth matrix valued functions. Math. Oper. Res. 27, 150–169 (2002) · Zbl 1082.49501
[28] Sun, D., Sun, J., Zhang, L.: The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming. Math. Program. 114, 349–391 (2008) · Zbl 1190.90117
[29] Zhang, J., Liu, Z.: Calculating some inverse linear programming problems. J. Comput. Appl. Math. 72, 261–273 (1996) · Zbl 0856.65069
[30] Zhang, J., Liu, Z.: A further study on inverse linear programming problems. J. Comput. Appl. Math. 106, 345–359 (1999) · Zbl 0971.90051
[31] Zhang, J., Ma, Z.: Solution structure of some inverse combinatorial optimization problems. J. Comb. Optim. 3, 127–139 (1999) · Zbl 0932.90034
[32] Zhao, X., Sun, D.F., Toh, K.-C.: A Newton-CG augmented Lagrangian method for semidefinite programming. Optimization (Online) (2008) · Zbl 1213.90175
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.