Highly redundant robots, such as humanoids, possess vast industrial and commercial potential. Unfortunately, producing useful behaviors on complex robots is a challenging undertaking, particularly when the robot must interact with the environment. Model-based whole-body control alleviates some of this difficulty by allowing complex whole-body motions to be broken up into multiple atomic tasks, which are performed simultaneously on the robot. However, tasks are generally planned without close consideration for the underlying controller and robot being used, or the other tasks being executed, resulting in infeasible and/or incompatible task combinations when executed on the robot. Consequently, there is no guarantee that the prescribed tasks will be accomplished, resulting in unpredictable, and most likely, unsafe whole-body motions. The adverse side-effects of simultaneous task combinations have been well known to the robotics community since the inception of redundant robots. Typically, these effects are managed by prioritizing between tasks and tuning their gains and parameters, but never is their root cause eliminated. Planning techniques can account for additional tasks to improve whole-body motions prior to execution. Nevertheless, because of modeling errors, there are always differences between what is planned and what is executed on a real robot. On the other end of the spectrum, model-free learning methods attempt to bypass modeling errors by using reinforcement learning and policy search to incrementally improve task(s) through trial-and-error. Regrettably, these tasks must often be demonstrated kinesthetically to the robot beforehand, and require many trials to improve --- this is no small feat on robots such as humanoids. Regardless of the technique used to generate the tasks, either the tasks themselves or their parameters need to be tuned on the real robot and this can be both time consuming and costly. The objective of this work is to better understand what makes tasks infeasible or incompatible, and develop automatic methods of improving on these two issues so that the overall whole-body motions may be accomplished as planned. We start by building a concrete analytical formalism of what it means for tasks to be feasible with the control constraints and compatible with one another. By studying the underlying convex optimization problem produced by the model-based whole-body controller, we develop metrics for analyzing and quantifying these two phenomena. Using the model-based feasibility and compatibility metrics, we demonstrate how the tasks can be optimized using non-linear model predictive control, while also detailing the shortcomings of this model-based approach. In order to overcome these weaknesses, we then develop a model-free approach to quantify task feasibility and compatibility through simple controller and robot agnostic cost functions. Using these measures, an optimization loop is designed, which automatically improves task feasibility and compatibility using model-free policy search in conjunction with model-based whole-body control. Through a series of simulated and real-world experiments, we demonstrate the effects of infeasible and incompatible task sets, and show that by simply optimizing the tasks to improve both feasibility and compatibility, complex and useful whole-body motions can be realized. By endowing robots with an automated mechanism for correcting poorly designed tasks, we not only reduce the need for fine tuning of task priorities and parameters, but also open the door to more complex, robust, and useful whole-body behaviors.