1

I have reduced a certain engineering problem to a few components,

  • A fixed vector $\mathbf{k}^{3\times 1}$,
  • Three fixed matrices $\mathbf{M}_1^{6\times 3}$, $\mathbf{M}_2^{6\times 3}$, $\mathbf{N}^{6\times 3}$
  • A freely chosen 'input' vector $\mathbf{e}^{3\times 1}$.

Furthermore, I have two 'output' vectors $\mathbf{V}^{6\times 1}$ and $\mathbf{W}^{6 \times 1}$, where

$$ \mathbf{V} = \mathbf{M}_1 \mathbf{k} + \mathbf{N} \mathbf{e}$$ $$ \mathbf{W} = \mathbf{V} - \mathbf{M}_2 \mathbf{k} $$

My goal is to minimize the element with the maximum absolute value encountered in either $\mathbf{V}$ or $\mathbf{W}$

$$ \min_{\mathbf{e}\in \mathbb{R}^3}\ \max\ \{|V_i|,|W_i|\}$$

Right now, I'm solving this with a rather brute-forced fminimax call in MATLAB, with varying degrees of success. However, given how simple the problem formulation is, I cannot help but feel that there should be some way to find a solution in a more elegant way.

Is there a way to solve this minimax problem; either in a closed-form solution, or if that's not possible, rewrite it in a way that is more suitable for numerical optimization?

Sanchises
  • 536

2 Answers2

1

You can linearize the problem as follows. Introduce a decision variable $z$ to represent the $\max$. The problem is to minimize $z$ subject to your original equations and: \begin{align} z &\ge V_i &\text{for all $i$}\\ z &\ge -V_i &\text{for all $i$}\\ z &\ge W_i &\text{for all $i$}\\ z &\ge -W_i &\text{for all $i$} \end{align} Now use a linear programming solver.

RobPratt
  • 45,619
1

Not a complete answer, but I hope it may give an idea. Notation: repeated indexes are summed. You have,

$$ V_i = M^1_{ij}k_j + N_{ij} e_j \qquad W_i = V_i- M^2_{ij}k_j $$

which implies

$$ V_i = a_j + N_{ij} e_j \qquad W_i = b_i + N_{ij} e_j $$

where $a = M^1 k $ and $b = M^1 k-M^2 k $ are fixed input vectors you can calculate at the beginning of your algorithm.

Now,

$$ \frac{\partial}{\partial e_l} \max{(|V|,|W|)} = \frac{1+sign(|V|-|W|)}{2|V|} (N_{ls}e_s+a_l) + \frac{1+sign(|W|-|V|)}{2 |W|} (N_{ls}e_s+b_l) $$

or, using $if(x)$ as a function that gives $1/0$ when $x$ is $true/false$,

$$ |V||W|\frac{\partial}{\partial e_l} \max{(|V|,|W|)} = |W|(N_{ls}e_s+a_l)\, if(|V|>|W|) + |V|(N_{ls}e_s+b_l) \, if(|W|>|V|) $$

Now that you have the gradient of the function you want to minimize you can apply some technique based on the gradient descent (https://en.wikipedia.org/wiki/Gradient_descent).

Quillo
  • 2,083