Для задач евклідової комбінаторної оптимізації виділені класи вершинно розташованих і поліедральносферичних множин, для яких узагальнено результати теорії опуклих продовжень. З використанням тео- рем про існування диференційованих опуклих продовжень для вершинно розташованих множин сформульовано еквівалентну задачу дискретної оптимізації опуклої функції при опуклих функціональних обме-женнях. Описано властивості релаксаційних задач опуклого програмування, що виникають.