Top

Numerical Algorithms

Published in:

20-05-2019 | Original Paper

An augmented Lagrangian proximal alternating method for sparse discrete optimization problems

Authors: Yue Teng, Li Yang, Xiaoliang Song, Bo Yu

Published in: Numerical Algorithms | Issue 3/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, we propose an augmented Lagrangian proximal alternating (ALPA) method for solving two classes of large-scale sparse discrete constrained optimization problems. Specifically, the ALPA method generates a sequence of augmented Lagrangian (AL) subproblems in the out iterations and utilizes a proximal alternating linearized minimization method and sparse projection techniques to solve these AL subproblems. And we study the first-order optimality conditions for these two classes of problems. Under some suitable assumptions, we show that any accumulation point of the sequence generated by the ALPA method satisfies the necessary first-order optimality conditions of these problems or is a local minimizer of these problems. The computational results with practical problems demonstrate that our method can find the suboptimal solutions of the problems efficiently and is competitive with some other local solution methods.

next article A Picard-type iterative algorithm for general variational inequalities and nonexpansive mappings

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Bertsimas, D., Shioda, R.: Algorithm for cardinality-constrained quadratic optimization. Comput. Optim. Appl. 43, 1–22 (2009)MathSciNetCrossRef

Bonami, P., Lejeune, M.: An exact solution approach for portfolio optimization problems under stochastic and integer constraints. Oper. Res. 57, 650–670 (2009)MathSciNetCrossRef

Cesarone, F., Scozzari, A., Tardella, F.: Efficient algorithms for mean-variance portfolio optimization with hard real-world constraints. G. Ist. Ital. Attuari 72, 37–56 (2009)

Cui, X.T., Zheng, X.J., Zhu, S.S., Sun, X.L.: Convex relaxations and MIQCQP reformulations for a class of cardinality-constrained portfolio selection problems. J. Glob. Optim. (2012)

Li, D., Sun, X., Wang, J.: Optimal lot solution to cardinality constrained mean-variance formulation for portfolio selection. Math. Finance 16, 83–101 (2006)MathSciNetCrossRef

Gao, J., Li, D.: Optimal cardinality constrained portfolio selection. Oper. Res. 61(3), 745–761 (2013)MathSciNetCrossRef

Shaw, D., Liu, S., Kopman, L.: Lagrangian relaxation procedure for cardinality-constrained portfolio optimization. Optim. Methods Softw. 23, 411–420 (2008)MathSciNetCrossRef

Bruckstein, A.M., Donoho, D.L., Elad, M.: From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev. 51, 34–81 (2009)MathSciNetCrossRef

Bienstock, D.: Computational study of a family of mixed-integer quadratic programming problems. Math. Program. 74(2, Ser. A), 121–140 (1996)MathSciNetCrossRef

10.

Miller, A.: Subset Selection in Regression, 2nd edn. Chapman & Hall, London (2002)CrossRef

11.

Günlük, O., Linderoth, J.: Perspective reformulations of mixed integer nonlinear programs with indicator variables. Math. Program. 124, 183–205 (2010)MathSciNetCrossRef

12.

Feizollahi, M.J., Ahmed, S., Sun, A.: Exact augmented Lagrangian duality for mixed integer linear programming. Math. Program. 161(1–2), 365–387 (2017)MathSciNetCrossRef

13.

Frangioni, A., Gentile, C.: Perspective cuts for a class of convex 0-1 mixed integer programs. Math. Program. 106, 225–236 (2006)MathSciNetCrossRef

14.

Frangioni, A., Gentile, C.: SDP diagonalizations and perspective cuts for a class of nonseparable MIQP. Oper. Res. Lett. 35, 181–185 (2007)MathSciNetCrossRef

15.

Frangioni, A., Gentile, C.: A computational comparison of reformulations of the perspective relaxation: SOCP vs. cutting planes. Oper. Res. Lett. 37, 206–210 (2009)MathSciNetCrossRef

16.

Tawarmalani, M., Sahinidis, N.: Semidefinite relaxations of fractional programs via novel convexification techniques. J. Glob. Optim. 20, 133–154 (2001)MathSciNetCrossRef

17.

Chang, T., Meade, N., Beasley, J., Sharaiha, Y.: Heuristics for cardinality constrained portfolio optimisation. Comput. Oper. Res. 27, 1271–1302 (2000)CrossRef

18.

Crama, Y., Schyns, M.: Simulated annealing for complex portfolio selection problems. Eur. J. Oper. Res. 150, 546–571 (2003)CrossRef

19.

Maringer, D., Kellerer, H.: Optimization of cardinality constrained portfolios with a hybrid local search algorithm. IEEE Spectr. 25, 481–495 (2003)MathSciNetMATH

20.

Schaerf, A.: Local search techniques for constrained portfolio selection problems. Comput. Econ. 20, 177–190 (2002)CrossRef

21.

Gulpinar, N., An, L.T.H., Moeini, M.: Robust investment strategies with discrete asset choice constraints using DC programming. Optimization 59(1), 45–62 (2010)MathSciNetCrossRef

22.

Zheng, X., Sun, X., Li, D., Sun, J.: Successive convex approximations to cardinality-constrained convex programs: a piecewise-linear DC approach. Comput. Optim. Appl. 59(1–2), 379–397 (2014)MathSciNetCrossRef

23.

Burdakov, O.P., Kanzow, C., Schwartz, A.: Mathematical programs with cardinality constraints: Reformulation by complementarity-type conditions and a regularization method. SIAM J. Optim. 26(1), 397–425 (2016)MathSciNetCrossRef

24.

Červinka, M, Kanzow, C, Schwartz, A.: Constraint qualifications and optimality conditions for optimization problems with cardinality constraints. Math. Program. 160(1-2), 353–377 (2016)MathSciNetCrossRef

25.

Lu, Z., Zhang, Y.: Sparse approximation via penalty decomposition methods. SIAM J. Optim. 23(4), 2448–2478 (2013)MathSciNetCrossRef

26.

Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program. 146(1-2), 459–494 (2014)MathSciNetCrossRef

27.

Xu, Y., Yin, W.: A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion. SIAM J. Imag. Sci. 6(3), 1758–1789 (2013)MathSciNetCrossRef

28.

Xu, Y., Yin, W.: A globally convergent algorithm for nonconvex optimization based on block coordinate update. J. Sci. Comput. 72(2), 700–734 (2017)MathSciNetCrossRef

29.

Lu, Z., Zhang, Y.: An augmented Lagrangian approach for sparse principal component analysis. Math. Program. 135, 149–193 (2012)MathSciNetCrossRef

30.

Chen, X., Guo, L., Lu, Z., Ye, J.: An augmented Lagrangian method for non-Lipschitz nonconvex programming. SIAM J. Numer. Anal. 55, 168–193 (2017)MathSciNetCrossRef

31.

Attouch, H., Bolte, J.: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program. 116, 5–16 (2009)MathSciNetCrossRef

32.

Teng, Y., Yang, L., Yu, B., Song, X.L.: A penalty PALM method for sparse portfolio selection problems. Optim. Methods Softw. 32(1), 126–147 (2017)MathSciNetCrossRef

33.

Bai, Y., Liang, R., Yang, Z.: Splitting augmented Lagrangian method for optimization problems with a cardinality constraint and semicontinuous variables. Optim. Methods Softw. 31(5), 1089–1109 (2016)MathSciNetCrossRef

34.

Rockafellar, R.T., Wets, R.: Variational Analysis. Grundlehren der Mathematis-chen Wissenschaften, pp. 317. Springer (1998)

35.

Bolte, J., Daniilidis, A., Ley, O., Mazet, L.: Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity. Trans. Am. Math. Soc., 362 (2010)

36.

Bolte, J., Daniilidis, A., Lewis, A.: The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17(4), 1205–1223 (2007)CrossRef

37.

Beasley, J.E.: OR-Library: Distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11), 1069–1072 (1990)CrossRef

Title: An augmented Lagrangian proximal alternating method for sparse discrete optimization problems
Authors: Yue Teng
Li Yang
Xiaoliang Song
Bo Yu
Publication date: 20-05-2019
Publisher: Springer US
Published in: Numerical Algorithms / Issue 3/2020
Print ISSN: 1017-1398
Electronic ISSN: 1572-9265
DOI: https://doi.org/10.1007/s11075-019-00705-x

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 3/2020

Error bounds for linear complementarity problems of S-QN matrices

The dynamical analysis of a uniparametric family of three-point optimal eighth-order multiple-root finders under the Möbius conjugacy map on the Riemann sphere

A class of upwind methods based on generalized eigenvectors for weakly hyperbolic systems

Strong convergence of extragradient methods for solving bilevel pseudo-monotone variational inequality problems

A Picard-type iterative algorithm for general variational inequalities and nonexpansive mappings

Optimal inverse projection of floating-point addition

Premium Partner