×

zbMATH — the first resource for mathematics

Inverse semidefinite quadratic programming problem with \(l_1\) norm measure. (English) Zbl 07189433
Summary: We consider an inverse problem arising from a semidefinite quadratic programming (SDQP) problem, which is a minimization problem involving \(l_1\) vector norm with positive semidefinite cone constraint. By using convex optimization theory, the first order optimality condition of the problem can be formulated as a semismooth equation. Under two assumptions, we prove that any element of the generalized Jacobian of the equation at its solution is nonsingular. Based on this, a smoothing approximation operator is given and a smoothing Newton method is proposed for solving the solution of the semismooth equation. We need to compute the directional derivative of the smoothing operator at the corresponding point and to solve one linear system per iteration in the Newton method and its global convergence is demonstrated. Finally, we give the numerical results to show the effectiveness and stability of the smoothing Newton method for this inverse problem.
Reviewer: Reviewer (Berlin)
MSC:
90C20 Quadratic programming
90C22 Semidefinite programming
90C25 Convex programming
Software:
CGS
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Das, R.; Mishra, S. C.; Kumar, T. B.P.; Uppaluri, R., An inverse analysis for parameter estimation applied to a non-fourier conduction-radiation problem, Heat Transfer Eng., 32, 6, 455-466 (2011)
[2] Das, R.; Mishra, S. C.; Ajith, M.; Uppaluri, R., An inverse analysis of a transient 2-d conduction-radiation problem using the lattice boltzmann method and the finite volume method coupled with the genetic algorithm, J. Quant. Spectrosc. Radiat., 109, 11, 2060-2077 (2008)
[3] Das, R.; Mishra, S. C.; Uppaluri, R., Inverse analysis applied to retrieval of parameters and reconstruction of temperature field in a transient conduction-radiation heat transfer problem involving mixed boundary conditions, Int. Commun. Heat. Mass, 37, 1, 52-57 (2010)
[4] Das, R., Inverse analysis of navier-stokes equations using simplex search method, Inverse Probl. Sci. Eng., 20, 445-462 (2012) · Zbl 1426.76464
[5] Das, R., A simulated annealing-based inverse computational fluid dynamics model for unknown parameter estimation in fluid flow problem, Int. J. Comput. Fluid Dyn., 26, 499-513 (2012)
[6] Burton, R.; Toint, P. L., On an instance of the inverse shortest paths problem, Math. Prog., 53, 45-61 (1992) · Zbl 0756.90089
[7] Heuberger, C., Inverse combinatorial optimization: A survey on problems, methods and results, J. Comb. Optim., 8, 329-361 (2004) · Zbl 1084.90035
[8] Ahuja, R. K.; Orlin, J. B., Inverse optimization, Oper. Res., 49, 771-783 (2001) · Zbl 1163.90764
[9] Ahuja, R. K.; Orlin, J. B., Combinatorial algorithms for inverse network flow problems, Networks, 40, 181-187 (2002) · Zbl 1026.90089
[10] 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
[11] Zhang, J.; Ma, Z., Solution structure of some inverse combinatorial optimization problems, J. Comb. Optim., 3, 127-139 (1999) · Zbl 0932.90034
[12] Burkard, R. E.; Lin, Y.; Zhang, J., Weight reduction problems with certain bottleneck objectives, European J. Oper. Res., 153, 191-199 (2004) · Zbl 1137.90689
[13] Zhang, J.; Liu, Z., Calculating some inverse linear programming problems, J. Comput. Appl. Math., 72, 261-273 (1996) · Zbl 0856.65069
[14] Zhang, J.; Liu, Z., A further study on inverse linear programming problems, J. Comput. Appl. Math., 106, 345-359 (1999) · Zbl 0971.90051
[15] Jiang, Y.; Xiao, X.; Zhang, L.; Zhang, J., A perturbation approach for a type of inverse linear programming problems, Int. J. Comput. Math., 88, 3, 508-516 (2011) · Zbl 1211.65071
[16] Iyengar, G.; Kang, W., Inverse conic programming with applications, Oper. Res. Lett., 33, 319-330 (2005) · Zbl 1140.90465
[17] Zhang, J.; Zhang, L., An augmented lagrangian method for a class of inverse quadratic programming problems, Appl. Math. Optim., 61, 57-83 (2010) · Zbl 1201.90152
[18] Xiao, X.; Zhang, L.; Zhang, J., On convergence of augmented lagrangian method for inverse semi-definite quadratic programming problems, Optim. J. Ind. Manag. Optim., 5, 2, 319-339 (2009) · Zbl 1196.90093
[19] Xiao, X.; Zhang, L.; Zhang, J., A smoothing newton method for a type of inverse semi-definite quadratic programming problem, J. Comput. Appl. Math., 223, 485-498 (2009) · Zbl 1155.65051
[20] Wu, J.; Zhang, Y.; Zhang, L.; Lu, Y., A sequential convex program approach to an inverse linear semidefinite programming problem, Asia Pac. J. Oper. Res., 33, Article 1650025 pp. (2016) · Zbl 1346.90660
[21] Clarke, F. H., Optimization and Nonsmooth Analysis (1983), John Wiley and Sons: John Wiley and Sons New York · Zbl 0582.49001
[22] Mifflin, R., Semismooth and semiconvex functions in constrained optimization, SIAM J. Control Optim., 15, 6, 959-972 (1977) · Zbl 0376.90081
[23] Qi, L.; Sun, J., A nonsmooth version of newton’s method, Math. Prog., 58, 353-367 (1993) · Zbl 0780.90090
[24] Sun, D., A Short Summer School Course on Modern Optimization Theory:Optimality Conditions and Perturbation Analysis, Part I, Part II, Part IIITech. Rep. (2006), National University of Singapore: National University of Singapore Singapore
[25] Zarantonello, E. H., Projections on convex sets in hilbert space and spectral theory: I and II, (Zarantonello, E. H., Contributions to Nonlinear Functional Analysis (1971), Academic Press: Academic Press New York), 237-424
[26] Meng, F.; Sun, D.; Zhao, G., Semismoothness of solutions to generalized equations and the moreau-yosida regularization, Math. Prog., 104, 561-581 (2005) · Zbl 1093.90059
[27] Bonnans, J.; Shapiro, A., Perturbation Analysis of Optimization Problems (2000), Springer: Springer New York · Zbl 0966.49001
[28] Sun, D.; Sun, J., Semismooth matrix valued functions, Math. Oper. Res., 27, 150-169 (2002) · Zbl 1082.49501
[29] Sun, D.; Sun, J.; Zhang, L., The rate of convergence of the augmented lagrangian method for nonlinear semidefinite proguamming, Math. Prog., 114, 349-391 (2008) · Zbl 1190.90117
[30] Sun, J.; Sun, D.; Qi, L., A squared smoothing newton method for nonsmooth matrix equations and its applications in semidefinite optimization problems, SIAM J. Optimiz., 14, 3, 783-806 (2004) · Zbl 1079.90094
[31] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3, 1-122 (2011) · Zbl 1229.90122
[32] Rockafellar, R. T.; Wets, R. J.B., Variational Analysis, Vol. 317 (1998), Springer: Springer New York
[33] Chen, B.; Harker, P., A non-interior-point continuation method for linear complementarity problems, SIAM J. Matrix Anal. Appl., 14, 4, 1168-1190 (1993) · Zbl 0788.65073
[34] Kanzow, C., Some Tools Allowing Interior-Point Methods to Become NoninteriorTechnical Report (1994), Institute of Applied Mathematics, University of Hamburg: Institute of Applied Mathematics, University of Hamburg Germany
[35] Smale, S., Algorithms for solving equations, (Proceedings of the International Congress of Mathematicians (1987), Ameri. Math. Sot. Providence), 172-195
[36] Qi, L.; Sun, D.; Zhou, G., A new look at smoothing newton methods for nonlinear complementarity problems and box constrained variational inequalities, Math. Prog., 87, 1-35 (2000) · Zbl 0989.90124
[37] Sonneveld, P., Cgs, a fast lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 10, 1, 36-52 (1989) · Zbl 0666.65029
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.