[en] We present a general and systematic treatment of multi-trace deformations in the AdS/CFT correspondence in the large N limit, pointing out and clarifying subtleties relating to the formulation of the boundary value problem on a conformal boundary. We then apply this method to study multi-trace deformations in the presence of a scalar VEV, which requires the coupling to gravity to be taken into account. We show that supergravity solutions subject to 'mixed' boundary conditions are in one-to-one correspondence with critical points of the holographic effective action of the dual theory in the presence of a multi-trace deformation, and we find a number of new exact analytic solutions involving a minimally or conformally coupled scalar field satisfying 'mixed' boundary conditions. These include the generalization to any dimension of the instanton solution recently found in hep-th/0611315. Finally, we provide a systematic method for computing the holographic effective action in the presence of a multi-trace deformation in a derivative expansion away from the conformal vacuum using Hamilton-Jacobi theory. Requiring that this effective action exists and is bounded from below reproduces recent results on the stability of the AdS vacuum in the presence of 'mixed' boundary conditions. (orig.)