Commit messages are crucial in software development, supporting maintenance tasks and communication among developers. While Large Language Models (LLMs) have advanced Commit Message Generation (CMG) using various software contexts, some contexts developers consider are often missed by CMG techniques and can't be easily retrieved or even retrieved at all by automated tools. To address this, we propose Commit Message Optimization (CMO), which enhances human-written messages by leveraging LLMs and search-based optimization. CMO starts with human-written messages and iteratively improves them by integrating key contexts and feedback from external evaluators. Our extensive evaluation shows CMO generates commit messages that are significantly more Rational, Comprehensive, and Expressive while outperforming state-of-the-art CMG methods and human messages 88.2%-95.4% of the time.