[Math] Minimizing sum of functions implies minimizing their squares, maximizing the sum of the inverses

optimization

I have $n$ functions (Say $f_1\space to \space f_n$) of $k$ variables (Say $x_1\space to\space x_k$) each. The functions are all positive, as well as the variables $xi's$. I do not have explicit expressions for these functions.
The objective is to minimize
$$\sum_{i=1}^n{f_i} \ \ \ \ \ \ \ subject \space to \ \ \ \ \sum_{i=1}^k{x_i^2} = P$$ where P is a known constant.

In which case(s) we can assume that this is equivalent to minimizing the sum of the squares of these functions ?
i.e:$$min\sum_{i=1}^n{f_i^2} \ \ \ \ \ \ \ subject \space to \ \ \ \ \sum_{i=1}^k{x_i^2} = P$$
Also, in which case(s) we can assume that this is equivalent to MAXIMIZING the sum of the inverses of these functions ?
i.e:$$max\sum_{i=1}^n{ {1\over f_i}} \ \ \ \ \ \ \ subject \space to \ \ \ \ \sum_{i=1}^k{x_i^2} = P$$
Assuming that the functions are nicely behaved, continuous, differentiable and everything.

Best Answer

$x^{4/3}+y^{4/3}$ subject to $x^2+y^2=2$ is minimized at $(0,\sqrt2)$.

$x^{8/3}+y^{8/3}$ subject to $x^2+y^2=2$ is minimized at $(1,1)$.

So, in answer to the question in the title, minimizing the sum of functions does not necessarily minimize the sum of their squares.

The Projection onto The Constrain

Let's define a vector $ z = \left[ {{x}_{1}}^{T}, {{x}_{2}}^{T}, \ldots, {{x}_{K}}^{T} \right]^{T} $.
The constrains is equivalent of:

$$ S * z = \boldsymbol{1}_{n}, \; S = \underset{\times K}{\left [ \underbrace{{I}_{n}, {I}_{n}, \ldots, {I}_{n}} \right ]} $$

Basically the matrix $ S $ sum over the $ i $ -th element of all $ x $ vectors.

Now, given a vector $ y \in \mathbb{R}^{nk} $, its projection onto the set $ \mathcal{S} = \left\{ x \mid S * x = \boldsymbol{1}_{n} \right\} $ is given by:

$$ \arg \min_{x \in \mathcal{S}} \frac{1}{2} \left\| x - y \right\|_{2}^{2} = y - {S}^{T} \left( S {S}^{T} \right)^{-1} \left( S y - \boldsymbol{1}_{n} \right) $$

Due to the special structure of $ S $ one could see it is equivalent to:

$$ {x}_{i} - \frac{\sum_{i = 1}^{K} {x}_{i} - \boldsymbol{1}_{n}}{K}, \: i = 1, 2, \ldots, k $$

Namely spread the deviation equally on all elements.

Here is the code:

%% Solution by Projected Gradient Descent

mX = zeros([numRows, numCols]);

for ii = 1:numIterations
    for jj = 1:numCols
        mX(:, jj) = mX(:, jj) - (stepSize * ((2 * tA(:, :, jj) * mX(:, jj)) + (paramLambda * mC(:, jj))));
    end
    mX = hProjEquality(mX);
end

objVal = 0;
for ii = 1:numCols
    objVal = objVal + (mX(:, ii).' * tA(:, :, ii) * mX(:, ii)) + (paramLambda * mC(:, ii).' * mX(:, ii));
end

disp([' ']);
disp(['Projected Gradient Solution Summary']);
disp(['The Optimal Value Is Given By - ', num2str(objVal)]);
disp(['The Optimal Argument Is Given By - [ ', num2str(mX(:).'), ' ]']);
disp([' ']);

The full code is in my Mathematics Q2199546 GitHub Repository (Specifically in Q2199546.m).
The code is validated using CVX.

Best Answer

Related Solutions

[Math] Proving that maximizing a sum of functions of different independent variables is equivalent to maximizing each function

[Math] Minimizing the Sum of Quadratic Form with Equality Constraint

The Projection onto The Constrain

Related Question