On the coupled continuous knapsack problems: projection onto the volume constrained Gibbs N-simplex

详细信息    查看全文

• 作者：Rouhollah Tavakoli
• 关键词：Knapsack problem ; Convex optimization ; Linearly constrained optimization ; Time ; linear algorithm
• 刊名：Optimization Letters
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：10
• 期：1
• 页码：137-158
• 全文大小：813 KB
• 参考文献：1.Baldo, S.: Minimal interface criterion for phase transitions in mixtures of cahn-hilliard fluids. Ann. Inst H. Poincaré (C) Anal. Non Linéaire 7(2), 67–90 (1990)MATH MathSciNet
  2.Bertsekas, D.P.: Constrained optimization and lagrange multiplier methods. Computer Science and Applied Mathematics, vol 1. Academic Press, Boston (1982)
  3.Birgin, E., Martínez, J.M., Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim. 10(4), 1196–1211 (2000)MATH MathSciNet CrossRef
  4.Birgin, E., Martınez, J.M., Raydan, M.: Spectral projected gradient methods: review and perspectives. J. Stat. Softw. 60(3) (2014)
  5.Blank, L., Garcke, H., Sarbu, L., Srisupattarawanit, T., Styles, V., Voigt, A.: Phase-field approaches to structural topology optimization. In: Constrained Optimization and Optimal Control for Partial Differential Equations, pp. 245–256. Springer, Berlin (2012)
  6.Boyd, S., Dattorro, J.: Alternating projections (online note) (2003)
  7.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), 1–122 (2011)CrossRef
  8.Boyd, S.P., Vandenberghe, L.: Convex optimization. Cambridge University Press (2004)
  9.Brown, E., Chan, T., Bresson, X.: Completely convex formulation of the chan-vese image segmentation model. Int. J. Comput. Vision 98(1), 103–121 (2012)MATH MathSciNet CrossRef
  10.Chambolle, A., Cremers, D., Pock, T.: A convex approach to minimal partitions. SIAM J. Imaging Sci. 5(4), 1113–1158 (2012)MATH MathSciNet CrossRef
  11.Chan, T., Vese, L.: Active contours without edges. IEEE Trans. Image Process. 10(2), 266–277 (2001)MATH CrossRef
  12.Dai, Y., Fletcher, R.: New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds. Math. Program. 106(3), 403–421 (2006)MATH MathSciNet CrossRef
  13.Escalante, R., Raydan, M.: Alternating projection methods, vol. 8. SIAM (2011)
  14.Garcke, H., Nestler, B., Stinner, B., Wendler, F.: Allen-cahn systems with volume constraints. Math. Models Methods Appl. Sci. 18(08), 1347–1381 (2008)MATH MathSciNet CrossRef
  15.Garcke, H., Nestler, B., Stoth, B.: A multiphase field concept: numerical simulations of moving phase boundaries and multiple junctions. SIAM J. Appl. Math. 60(1), 295–315 (1999)MATH MathSciNet CrossRef
  16.Gibbs, J.W.: On the equilibrium of heterogeneous substances. Connecticut Academy of Arts and Sciences (1877)
  17.Hager, W., Zhang, H.: A new active set algorithm for box constrained optimization. SIAM J. Optim. 17(2), 526–557 (2006)MATH MathSciNet CrossRef
  18.Kiwiel, K.: On linear-time algorithms for the continuous quadratic knapsack problem. J. Optim. Theory Appl. 134(3), 549–554 (2007)MATH MathSciNet CrossRef
  19.Kiwiel, K.: Breakpoint searching algorithms for the continuous quadratic knapsack problem. Math. Program. 112(2), 473–491 (2008)MATH MathSciNet CrossRef
  20.Kiwiel, K.: Variable fixing algorithms for the continuous quadratic knapsack problem. J. Optim. Theory Appl. 136(3), 445–458 (2008)MATH MathSciNet CrossRef
  21.Lellmann, J., Schnörr, C.: Continuous multiclass labeling approaches and algorithms. SIAM J. Imaging Sci. 4(4), 1049–1096 (2011)MATH MathSciNet CrossRef
  22.Nesterov, Y., Nemirovskii, A.: Interior-point polynomial algorithms in convex programming, vol. 13. SIAM (1994)
  23.Nestler, B., Wendler, F., Selzer, M., Stinner, B., Garcke, H.: Phase-field model for multiphase systems with preserved volume fractions. Phys. Rev. E 78(1), 011604 (2008)CrossRef
  24.Nocedal, J., Wright, S.: Numerical optimization. Springer (2006)
  25.Pardalos, P.M., Kovoor, N.: An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds. Math. Program. 46(1–3), 321–328 (1990)MATH MathSciNet CrossRef
  26.Robinson, A.G., Jiang, N., Lerme, C.S.: On the continuous quadratic knapsack problem. Math. Program. 55(1–3), 99–108 (1992)MATH MathSciNet CrossRef
  27.Rosen, J.B.: The gradient projection method for nonlinear programming. Part i. Linear constraints. J. Soc. Ind. Appl. Math. 8(1), 181–217 1960
  28.Steinbach, I., Pezzolla, F., Nestler, B., Seeßelberg, M., Prieler, R., Schmitz, G.J., Rezende, J.L.L.: A phase field concept for multiphase systems. Physica D Nonlin Phenomena 94(3), 135–147 (1996)MATH CrossRef
  29.Tavakoli, R.: Multimaterial topology optimization by volume constrained allen-cahn system and regularized projected steepest descent method. Comput. Methods Appl. Mech. Eng. 276, 534–565 (2014)MathSciNet CrossRef
  30.Tavakoli, R., Mohseni, S.M.: Alternating active-phase algorithm for multimaterial topology optimization problems: a 115-line matlab implementation. Struct. Multidiscip. Optim. 49, 621–642 (2013)MathSciNet CrossRef
  31.Tavakoli, R., Zhang, H.: A nonmonotone spectral projected gradient method for large-scale topology optimization problems. Numer. Algebra Control Optim. 2(2), 395–412 (2012)MATH MathSciNet CrossRef
  32.Wright, S.J.: Primal-dual interior-point methods, vol. 54. SIAM (1997)
  33.Zhen, L., Wei, G., Chongmin, S.: Design of multi-phase piezoelectric actuators. J. Int. Mater. Syst. Struct. 21(8), 1851–1865 (2010)
  34.Zhou, S., Wang, M.Y.: Multimaterial structural topology optimization with a generalized cahn-hilliard model of multiphase transition. Struct. Multidiscip. Optim. 33(2), 89–111 (2007)MATH MathSciNet CrossRef
  
• 作者单位：Rouhollah Tavakoli (1)
  
  1. Department of Materials Science and Engineering, Sharif University of Technology, P.O. Box 11365-9466, Tehran, Iran
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Optimization
  Operation Research and Decision Theory
  Numerical and Computational Methods in Engineering
  Numerical and Computational Methods
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1862-4480

文摘

Coupled continuous quadratic knapsack problems (CCK) are introduced in the present study. The solution of a CCK problem is equivalent to the projection of an arbitrary point onto the volume constrained Gibbs N-simplex, which has a wide range of applications in computational science and engineering. Three algorithms have been developed in the present study to solve large scale CCK problems. According to the numerical experiments of this study, the computational costs of presented algorithms scale linearly with the problem size, when it is sufficiently large. Moreover, they show competitive or even superior computational performance compared to the advanced QP solvers. The ease of implementation and linear scaling of memory usage with the problem size are the other benefits of the presented algorithms.