how analytically (or with matlab) can i find the solution to the following algebraic problem?

Question

Here is the problem: find $x_k$'s ($x_k\in R$) such that

$\max_{i} \{|c_i+\sum_k x_k d_{ki}| \}=\gamma$,

where $c_i$ and $d_{ki}$ are constant numbers in $R$.

I'm looking for the set of $x_k$ that satisfies the above condition.

For example

$\max\{|2-3x_1+x_2|,|1+2x_1+x_2|\}=1$,

---

Edited: to make the example more clear.

Consider this one

$\max\{|2-3x_1+x_2|,|1+2x_1+x_2|, |1-x_1-x_2|\}=1$,

That is, the number of equations is not equal to the number of variables.

Answer 1

EDIT: The answer below gives one and all solutions for the problem of finding a $x_k\in\mathbb{R}$ such that

$\max_i\{\lvert c_i+\sum_k x_k d_{ki}\rvert\}=\gamma$

where $c_i$ and $d_{ki}$ are constant numbers in $\mathbb{R}$.

The solution for the problem of finding all the possibles $x_k$ that satisfies the equation above is given after the approach that finds one solution.

For one solution:

I've found the following solution method, verify if it fits your requirements. I focused on the solution of the example but it might work for any problem.

Note that any solution for you problem lies on the border of the following region

\begin{gather} -1 \leq 2 - 3x_1 + x_2 \leq 1\\ -1 \leq 1 +2x_1 +2x_2 \leq 1 \end{gather}

Therefore solving the optimization problem \begin{align} \max\quad &c^Tx\\ \textrm{s.t.:}\quad&-1 \leq 2 - 3x_1 + x_2 \leq 1\\ &-1 \leq 1 +2x_1 +2x_2 \leq 1 \end{align} where $c$ is a nonzero vector, will result in a solution that satisfies your conditions.

The feasible region is shown in the following plot

For all solutions:

For all solutions you can do a similar approach, create a polyhedron given by the convex relaxation of the problem. The equations are given by \begin{align} -\gamma \leq c_i+\sum_k x_k d_{ki}\leq \gamma \end{align} for all $i$.

Then use a vertex enumeration algorithm to obtain all the vertex of the polyhedron. Suggested links

• 2 - related question in the mathoverflow,
• 3 - Avis-Fukuda Algorithm for Vertex Enumeration Problems (A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra),
• 4 - Old paper about the subject might be interesting option.

You can find more over internet over the keyword "Vertex enumeration problem".

Answer 2

If we are given $m$ linear functions $$\phi_i:\quad{\mathbb R}^n\to{\mathbb R}, \qquad x\mapsto \phi_i(x):=\langle d_i,x\rangle +c_i\qquad(1\leq i\leq m)$$ and a real $\gamma>0$ the $2m$ inequalities $$-\gamma\leq \phi_i(x)\leq \gamma\qquad(1\leq i\leq m)$$ define a convex polytope $P\subset{\mathbb R}^n$ (which may be empty, and need not be bounded). The set you are interested in is the boundary $\partial P$ of this polytope. This boundary can have a complicated combinatorial structure. The possible numbers of vertices, edges, $\ldots$, facets form an intensive area of research. This is to say that your problem is computationally hard as soon as $m$ and $n$ get larger.

A simple case is treated in the following first version of this answer:

Assume that the matrix $D=[d_{ki}]$ is square and nonsingular, and consider the affine map $$A:\quad x\mapsto y:=D'x+c\ .$$ (Your indexing of the $d_{ki}$ is somewhat unfortunate, therefore the $'\>$) You are interested in the set $$S:=\{x\in{\mathbb R}^n\>|\>\max_i|y_i|=\gamma\}\ .$$ Now the set $\{y\in {\mathbb R}^n\>|\>\max_i|y_i|=\gamma\}$ is the surface $\partial C$ of the $n$-dimensional cube $$C:=\{y\in {\mathbb R}^n\>|\>-\gamma\leq y_i\leq\gamma \ (1\leq i\leq n)\}\ ,$$ and is the union of $2n$ such cubes of one dimension less (an ordinary $3$-dimensional cube has $6$ two-dimensional square faces).

It follows that $$S=A^{-1}(\partial C)=(D')^{-1}(\partial C -c)\ .$$