Decomposition of Large Scale Problems

In many problems of large size encountered in applications, the constraints are linear, while the objective function is a sum of two parts: a linear part involving most of the variables of the problem, and a concave part involving only a relatively small number of variables. More precisely, these problems have the form P % MathType!MTEF!2!1!+- % feaagCart1ev2aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn % hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr % 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9 % vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x % fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaaeaaaaaaaaa8 % qacaqGTbGaaeyAaiaab6gacaqGPbGaaeyBaiaabMgacaqG6bGaaeyz % aiaabccacaWGMbGaaiikaiaadIhacaGGPaGaey4kaSIaamizaiaadM % hapaGaaGzbV-qacaqGZbGaaeyDaiaabkgacaqGQbGaaeyzaiaaboga % caqG0bGaaeiiaiaabshacaqGVbGaaeiiaiaacIcacaWG4bGaaiilai % aadMhacaGGPaGaeyicI4SaeuyQdCLaeyOGIW8efv3ySLgznfgDOjda % ryqr1ngBPrginfgDObcv39gaiuaapaGae8xhHi1aaWbaaSqabeaape % GaamOBaaaakiabgEna0+aacqWFDeIudaahaaWcbeqaa8qacaWGObaa % aaaa!6914! $$ {\text{minimize }}f(x) + dy\quad {\text{subject to }}(x,y) \in \Omega \subset {R^n} \times {R^h} $$ where f: ℝn → ℝ is a concave function, Ω is a polyhedron, d and y are vectors in ℝh, and n is generally much smaller than h.