Es posible usando las librerias GD (
www.php.net/gd)
En principio podrías generar una imagen jpg y ahí jugar con el "ratio" de compresión de JPG para quedarte con algo que ronde ese peso en Kbytes vs calidad que resulte. Realmente esto es bastante "subjetivo" y más si dices que cualquier usuario llegará y podrá su imagen como buenamente la tenga.
Es necesario que se conserve el tamaño en pixels original de la imagen? ..Podrías empezar por ahí en la optimización: si son imagenes para ver en "pantalla" .. no necesitamos esas imagenes de "2272x1704 " que sale de una fotografía digital de una camara de unos "4 Megapixels". Lo más probable es que con "800x600" o incluso mucho menos .. nos sirva para presentar en el sitio. Con esa optimización de tamaño .. ya reduciras mucho el peso del archivo (imagen) .. luego puedes seguir aplicando la compresión en JPG para dejarlo todavía con menos "peso" a costa de calidad por supuesto.
Un saludo,