In problem 4.55 of Boyd & Vandenberghe's Convex Optimization, the authors ask the following.

Show that in a multicriterion optimization problem, a unique solution of the scalar optimization problem

$$ \min. \max._{i =1,2\cdots q}F_i (x) $$ $$\text{s.t. } f_i(x)\leq 0 $$ $$ h_i(x)=0 $$ is Pareto optimal.

I know that, in a multicriterion optimization problem a solution is pareto optimal point if we can not find a better point. I assume that $x^*$ is the solution of the above scalar optimization problem. Now I have to show that for every feasible $y\neq x^*$ we have $$[F_1(x^*),~F_2(x^*), \cdots F_q(x^*)]\preceq [F_1(y),~F_2(y), \cdots F_q(y)].$$ I think the only other information that I have is that one of the $F_i(x^*)$ is greater than all of the rest of $F_j(x^*)'s$ for $j\neq i$. How to solve this problem? Thanks in advance.

  • 1
    $\begingroup$ Assume such a solution is not pareto optimal. Show a contradiction. $\endgroup$ – Mark L. Stone Aug 3 '19 at 22:53
  • $\begingroup$ You don't know that one of the $F_i(x^*)$ values is greater than all $F_j(x^*)$'s for $j \neq i$. For example, we might have $x^*=(3,3,3,3)$. What "unique solution" means here is that there is only one $x^*$ that solves the constrained min/max problem. $\endgroup$ – Michael Aug 4 '19 at 2:46
  • $\begingroup$ Keep in mind that the vectors might not always be ordered with respect to $\succeq$. Your definition of Pareto optimal is off. $\endgroup$ – Brian Borchers Aug 4 '19 at 4:53

Assume $x^*$ is not Pareto optimal then wlog there exists $y \neq x^*$ such that $F_1(y) < F_1(x^*)$ and $F_i(y) \leq F_i(x^*)$ for all $i =2\cdots q$. Now, this implies $$ \max_{i =1,2\cdots q}F_i (y) \leq \max_{i =1,2\cdots q}F_i (x^*) = \min_{x} \max_{i =1,2\cdots q}F_i (x),$$ by definition of $x^*$. Therefore, $y$ is also a minimum to the original scalar optimization problem. By assumption, this minimum is unique, therefore $y = x^*$, a contradiction. Therefore, $x^*$ is Pareto optimal.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.