We propose a new approach to portfolio optimization by separating asset return distributions into positive and negative half-spaces. The approach minimizes a newly-defined Partitioned Value-at-Risk (PVaR) risk measure by using half-space statistical information. Using simulated data, the PVaR approach always generates better risk-return tradeoffs in the optimal portfolios when compared to traditional Markowitz mean-variance approach. When using real financial data, our approach also outperforms the Markowitz approach in the risk-return tradeoff. Given that the PVaR measure is also a robust risk measure, our new approach can be very useful for optimal portfolio allocations when asset return distributions are asymmetrical.