• تعریف تابع هدف محدب

یک مسأله بهینه‌سازی چند‌هدفی محدب است، اگر همه توابع هدف و فضای شدنی آن محدب باشد. براساس این تعریف، یک مساله برنامه‌ریزی خطی چند‌هدفی، یک مسأله محدب است. چون یک مسأله بهینه‌سازی دارای دو فضا (فضای هدف و فضای متغیر تصمیم)، است، تحدب در هر فضا برای یک الگوریتم بهینه‌سازی چند‌هدفی مهم است. هم‌چنین، این امکان وجود دارد که فضای جستجو نامحدب باشد، در حالی که فضای بهینه-پارتو محدب است.

• تفاوت بهینه‌سازی چند‌هدفی با بهینه‌سازی تک‌هدفی

به غیر از داشتن اهداف چندگانه، تفاوت‌های بنیادی دیگری بین بهینه‌سازی تک‌هدفی و چند‌هدفی به صورت زیر وجود دارند.

• چند هدف به جای یک هدف
• مواجهه با دو فضای جستجو
• فقدان حدود ساختگی

الف- چند هدف به‌جای یک هدف

در بهینه‌سازی تک‌هدفی، یک هدف وجود دارد (جستجو برای یک جواب بهینه). اگرچه فضای جستجو، ممکن است دربرگیرنده چندین جواب بهینه موضعی باشد، هدف همیشه یافتن جواب بهینه سراسری است. در مجموع، هدف اغلب الگوریتم‌های بهینه‌سازی تک‌هدفی یافتن جواب یگانه‌ای است، حتی هنگامی که چند جواب بهینه وجود دارند. در یک الگوریتم بهینه‌سازی تک‌هدفی، هرگاه یک جواب جدید مقدار تابع هدف بهتری از یک جواب قبلی داشته باشد، جواب جدید پذیرفته ‌می‌شود.

در بهینه‌سازی چند‌هدفی، پیشرفت در جهت طرح بهینه پارتو، هدف بسیار مهمی است. ضمناً، داشتن مجموعه جواب‌های گوناگون در طرح نامغلوب نیز حیاتی است. الگوریتمی که مجموعه محدودی از جواب‌ها را از طرح بهینه پارتو برمی‌گزیند، هدف اول یعنی همگرایی در طرح بهینه پارتو را برآورده‌می‌سازد، لیکن موجب فراهم آمدن چگالی و تنوع در مجموعه حاصل نمی‌شود. از آن‌جا که در یک بهینه‌سازی چند‌هدفی، همه اهداف با اهمیت هستند، مجموعه گوناگونی از جواب‌ها بدست آمده که مربوط به طرح بهینه-پارتو هستند، تنوعی را در جواب‌های بهینه ایجاد می‌کنند که هریک، اهداف را به طور متفاوتی برآورده می‌سازند.

ب- مواجهه با دو فضای جستجو

پیچیدگی دیگر این است که بهینه‌سازی چند‌هدفی به جای یک فضای جستجو، دو فضای جستجو دارد. در یک بهینه‌سازی تک‌هدفی تنها یک فضای جستجو (فضای متغیر تصمیم) وجود دارد. در این فضا، یک الگوریتم، با پذیرش یا رد جواب‌ها بر حسب مقدار تابع هدف آن‌ ها عمل‌می‌کند. در بهینه‌سازی چند‌هدفی، علاوه بر فضای متغیر تصمیم، فضای هدف یا معیار نیز وجود دارد. اگرچه این دو فضا با یک نگاشت یگانه با یک‌دیگر مرتبط هستند، این نگاشت در اغلب موارد، غیر‌خطی است و ویژگی‌های جستجو شبیه به‌هم نیستند. برای مثال مجاورت دو جواب در یک فضا به معنی مجاورت آنها در فضای دیگر نیست. بنابراین، اگرچه نیل به هدف دوم، برقراری پراکندگی در مجموعه جواب‌های بدست آمده است، تصمیم گیری در خصوص اینکه پراکندگی در کدام فضا ایجاد شود نیز اهمیت شایانی دارد.

در هر الگوریتم بهینه‌سازی، جستجو در فضای متغیر تصمیم صورت می‌گیرد. به هر حال جریان پیشروی یک الگوریتم در فضای متغیر تصمیم می‌تواند به فضای هدف، کشانده ‌شود. در بعضی از الگوریتم‌ها، از پیش‌روی‌های حاصل در فضای هدف می‌تواند برای هدایت جستجو در فضای متغیر تصمیم مورد استفاده شود. هنگامی که چنین چیزی اتفاق‌می‌افتد، پیش‌روی‌ها در هر دو فضا باید به طریقی هماهنگ شوند، که ایجاد جواب‌هایی جدید در فضای متغیر تصمیم، معرف پراکندگی مورد نیاز در فضای هدف باشند. این امر، به هیچ وجه، کار ساده ای نیست و مهم‌تر این‌که به نگاشت بین متغیرهای تصمیم و مقادیر تابع هدف بستگی دارد.