Improved　focusing　of　laser　beams　using　high　numerical　aperture　systems　is　an　efficient　route　to　increasing　intensities　in　the　ultrafast　regime　to　relativistic　levels.　We　experimentally　demonstrate　a　new　method　of　optimizing　the　focus　of　a　high-power　laser,　using　second　harmonic　generation　at　full　intensity　in　a　low-pressure　gas　to　provide　a　figure　of　merit　for　optimizing　the　shape　of　a　deformable　mirror　via　a　genetic　algorithm.　Nonlinear　and　thermal　aberrations　are　corrected,　and　aberrations　introduced　by　filters　are　avoided.　The　method　is　applied　to　focus　a　millijoule,　short　pulse　(30　fs),　high　repetition　rate　laser　system　to　relativistic　intensity　in　both　near　IR　and　mid　IR　regimes.