Two decomposition algorithms for nonconvex optimization problems with global variables

A feature common to many optimization problems is a weak connectivity between component systems. Decomposition algorithms exploit this feature by breaking the problem into a set of smaller independent problems. One type of connectivity occurs when only a few of the variables, known as global variables, are relevant to all systems, while the remainder are local to a single component. We term these problems Optimization Problems with Global Variables. Examples arise in the design of complex systems such as an aircraft or automobile and in the solution of stochastic problems such as portfolio management.; Collaborative Optimization (CO) is a promising decomposition algorithm that transforms an Optimization Problem with Global Variables into an equivalent master problem and a set of subproblems. Unfortunately, both the CO master problem and the subproblems are degenerate. Nondegeneracy is a common assumption when proving convergence for most optimization algorithms. Not surprisingly, CO fails to solve some simple test problems.; We propose two novel decomposition algorithms that circumvent some of the difficulties associated with CO. The first algorithm, named Inexact Penalty Decomposition (IPD), uses an inexact penalty function. The second algorithm, termed Exact Penalty Decomposition (EPD), employs an exact penalty function and a barrier function. The main advantage is that these new approaches result in nondegenerate problems. Consequently, there exist algorithms that are fast locally convergent for both the master problem and the subproblems.; To test the new algorithms we present a new quadratic programming test-problem set. The user can choose problem size, convexity, degeneracy, and degree of coupling. All test-problem minimizers are known a priori. Both IPD and EPD successfully solve the test set for a wide variety of circumstances.