4
$\begingroup$

This is a more generalized form of a previous unanswered question, from which I've removed all the content that wasn't relevant to the actual problem.

I have a minimization problem of the form

$$ \min_{\vec d \in U} c - \vec a^\intercal \vec d, $$

where

$$ c \in \mathbb{R} \\ \vec a, \vec d \in \mathbb{R}^{3n} \\ U = \{(\vec d_1, ..., \vec d_n) \in \mathbb{R}^{3n}:\|\vec{d_i}\| = r_i\} \\ \vec r \in \mathbb{R}^n $$

In other words, $\vec{d}$ is an agregate vector consisting of $n$ three-dimensional vectors in series, each of which has the length of the corresponding element of $\vec{r}$. The goal is the find of the orientation of these vectors which minimizes the original function. My understanding of optimization isn't terribly robust, and I'm not sure how to approach this; the function to be minimized is linear, but none of the constraints are. The original constraint $\vec{d} \in U$ could also be expressed as a set of constraints of the form

$$ d_{3i-2}^2 + d_{3i-1}^2 + d_{3i}^2 = r_i^2, $$

but now I just have a bunch of independent spheres as constraints. I feel like I'm missing something here that should be obvious.

$\endgroup$

1 Answer 1

3
$\begingroup$

One can apply the method of Lagrange Multipliers. Defining the objective function $f(\vec x) = c - \vec a^T \vec x$ and the constraint functions $g_i(\vec x) = x_{3i-2}^2 + x_{3i-1}^2 + x_{3i}^2 - r_i^2$, our problem is to solve

$$\frac{df}{d\vec x} + \sum_{i=1}^n \lambda_i \frac{dg_i}{d\vec x} = \vec 0^T$$

where $\frac{d}{d\vec x}$ indicates the row-vector gradient $\left(\frac{d}{dx_1},\ldots,\frac{d}{dx_{3n}}\right)$, subject to the constraints

$$g_i(\vec x) = 0, \qquad i \in \{1,\ldots,n\}$$

First, some computation: we have that $\frac{df}{d\vec x} = -\vec a^T$ and that $$\frac{dg_i}{d\vec x} = (0_1, \ldots, 0_{3i-3}, 2x_{3i-2}, 2x_{3i-1},2x_{3i},0_{3i+1},\ldots,0_{3n})$$

(i.e. all the entries except for $3i-2, 3i-1, 3i$ are zero). Thus we have that

$$\sum_{i=1}^n \lambda_i \frac{dg_i}{d\vec x} = \left(\lambda_1x_1, \lambda_1x_2, \lambda_1x_3, \lambda_2x_4, \ldots, \lambda_nx_{3n-1},\lambda_nx_{3n}\right) = - \frac{df}{d\vec x} = \vec a^T$$

This vector equaction breaks down into the separate equations

$$\lambda_i(x_{3i-2},x_{3i-1},x_{3i}) = (a_{3i-2},a_{3i-1},a_{3i}) \qquad i \in \{1,\ldots,n\}$$

What this means is that we are really solving the problem of optimizing the direction of each vector independently. Taking the dot product of those equations with themselves we obtain

$$\lambda_i^2 (x_{3i-2}^2 + x_{3i-1}^2 + x_{3i}^2) = \lambda_i^2r_i^2 = a_{3i-2}^2 + a_{3i-1}^2 + a_{3i}^2$$

Defining the quantity $A_i = \sqrt{a_{3i-2}^2 + a_{3i-1}^2 + a_{3i}^2}$ we then have the solutions

$$\lambda_i = \pm \frac{A_i}{r_i}$$ $$(x_{3i-2},x_{3i-1},x_{3i}) = \frac{1}{\lambda_i}(a_{3i-2},a_{3i-1},a_{3i})$$

It's not hard to see intuitively that the minimum will be when $\lambda_i > 0$ for all $i\in \{1,\ldots,n\}$, and in the interest of brevity, I won't go through proving it using second-order conditions, but this is doable. We thus obtain the solution

$$\vec x = \left(\frac{r_1}{A_1}a_1, \frac{r_1}{A_1}a_2, \frac{r_1}{A_1}a_3, \frac{r_2}{A_2}a_4, \ldots, \frac{r_n}{A_n}a_{3n-1}, \frac{r_n}{A_n}a_{3n}\right)^T$$

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .