How to combine minimum and maximum objectives into one optimization problem?

Question

I want to solve the following optimization problem $$\min_x \| y-Ax\|_2^2 \\ while \\ \max_x \lambda \| z-Bx\|_2^2 \\ $$ In which y,z and x are vectors and A and B are matrices.

I'm not sure how is the best easy to combine them into one optimization problem?

is the best way to add the negative of the maximization to the minimization?

Answer 1

This is what is known as a multi-objective (particularly bi-objective) optimization problem There is a large literature on solving such problems.

It's conventional to flip the sign of maximization objectives so that you're simultaneously trying to minimize two objectives. So, you've got

$\min_{x} \| y-Ax \|_{2}^{2}$

and simultaneously

$\min_{x} -\lambda \| z-Bx \|_{2}^{2}$

The first difficulty to deal with is defining "optimal" for such a problem. One commonly used approach is to consider "Pareto optimal" solutions. A particular solution is Pareto optimal if we can't improve on either of the objective values without worsening the other objective value. There will typically be many Pareto optimal solutions, along a curve called the Pareto frontier.

For your biobjective problem, you can construct the Pareto frontier by solving a sequence of problems:

$\min -\lambda \| z-Bx \|_{2}^{2} $

subject to

$\| y-Ax \|_{2}^{2} \leq b_{i}$

Where $b_{i}$ is a sequence of equally spaced values that reasonably discretize the curve. Something like $b_{0}=0$, $b_{1}=0.01$, $b_{2}=0.02$, $\ldots$. After solving the $i$th problem, plot a point at coordinates given by the two objective values, and move on.

An alternative to solving these constrained optimization problems is called scalarization. In the scalarization approach, we construct a weighted sum of the two objective functions and adjust the weighting parameter:

$\min_{x} \| y-Ax \|_{2}^{2} + \alpha (-\lambda) \| z-Bx \|_{2}^{2}$

Once you've traced out the Pareto frontier, you have a choice to make- which of the available trade-offs between the two objectives do you prefer?

With either of these approaches, it's important to understand that your optimization problems will be nonconvex (because you're maximizing the convex function $\|z-Bx\|_{2}^{2}$.) Thus you'll need to use some sort of global optimization method. Because stochastic methods aren't completely reliable, you'll be much better off if you use a deterministic global optimization method such as branch and bound.