# How to solve the following problem from convex optimization book?

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.

• Assume such a solution is not pareto optimal. Show a contradiction. – Mark L. Stone Aug 3 '19 at 22:53
• 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. – Michael Aug 4 '19 at 2:46
• Keep in mind that the vectors might not always be ordered with respect to $\succeq$. Your definition of Pareto optimal is off. – 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.