4
$\begingroup$

So I have the following function, which I want to maximize: $$f(x_1,...,x_n) = \sum_{i=1}^n\alpha_i\sqrt{x_i}$$ (where all $\alpha_i$ are positive), subjected to the following equality and inequality constraints: $$\sum_{i=1}^nx_i = B$$ $$l_i \leq x_i \leq u_i$$

for $l_i,u_i,B$ all positive.

I want to say that there's a nice geometric way to think about this. In particular, invoking the coordinate transformation $$x_i\mapsto {v_i\over \alpha_i^2} $$, we have $$f(v_1,...,v_n) = \sum_{i=1}^n\sqrt{v_i}$$ and constraints $$\sum_{i=1}^n{v_i\over \alpha_i^2}$$ $$l_i \leq {v_i \over \alpha_i^2} \leq u_i$$

In a global sense, given a fixed sum, $S$, of all the $v_i$ we know from the triangle inequality that the optimal solution is $v_i = {S\over n}$ for all $i$. Is there a way to apply this knowledge of the global solution to finding one within our constraint region (which is the intersection of a hyperplane and a polytope). If there's no easy way to divine a closed form solution, might there be an algorithm suited to this kind of optimization?

Gradient ascent is applicable, but it seems to be too ignorant of what I want to call the nice-ness of the objective function and constraint region.

I don't have much background by way of numerical analysis, so I'd really appreciate any insight.

Edit: I should probably point out that I will eventually be attempting to code this algorithm, so solutions of exponential or worse order are scary to me.

Edit2: I realize this question isn't the most interesting numerical exercise in the world, so I've attached a modest bounty.

$\endgroup$
  • $\begingroup$ Putting $v_i=w_i^2$ this is also the optimisation of a linear function on the intersection of a hyperellipsoid and a block. $\endgroup$ – Justpassingby Dec 29 '15 at 23:43
  • $\begingroup$ @Justpassingby...uhhh...go on... $\endgroup$ – AsinglePANCAKE Dec 30 '15 at 4:20
1
$\begingroup$

If we substitute $v_i=w_i^2$ then the constraints define the intersection of a hyperellipsoid (which is an $(n-1)$-dimensional convex surface in $n$-space) with a rectangular block, and the function to optimise is $\sum_iw_i.$ The hyperellipsoid is centered at the origin and its axes are parallel to the coordinate axes.

Since we are only interested in positive $w_i$ the intersection of the $(n-1)$-dimensional hyperellipsoid and the block is a single curved cell bounded by hyperellipsoids of lower dimensions. In order to find the optimum we need to try each dimension in turn, starting with the highest $n-1$ (the interior of the cell).

The direction of the normal to the hyperellipsoid defined by the equation

$$\sum_i\frac{w_i^2}{\alpha_i^2}=B$$

is defined by the coordinates $(w_1/\alpha_1^2,\ldots,w_n/\alpha_n^2).$ The unique point (with positive coordinates) where this coincides with the gradient of the function $\sum_iw_i$ is at the point with coordinates

$$\frac B n(\alpha_1^2,\ldots,\alpha_n^2)$$

If this point lies in the cell or on its boundary (i.e., if its satisfies the constraints defined by the constants $l_i, u_i$) then it defines the maximum of $f$ and we are done.

If this point lies outside the boundary of the cell (i.e., if its violates at least one of the inequalities) then we need to reformulate the problem $2n$ times in one dimension lower: once for every $i=1,\ldots,n$ using the lower bound $\frac{w_i^2}{\alpha_i^2}=l_i$ and again for the upper bound $u_i.$ In this reformulated problem, the block constraint for the $i$-th coordinate is dropped and $w_i$ is otherwise treated as a constant (to be absorbed in the constant $B$ and in the computation of $f$). The constant $\alpha_i^2$ no longer occurs in the solution for the optimum of $f$ on the lower-dimensional hyperellipsoid.

This process is repeated recursively to build a tree of hyperellipsoid segments of ever lower dimension. A node in the tree is a leaf (i.e., has no children) if and only if $f$ reaches a local maximum in that segment.

The global optimum of $f$ is the largest local maximum reached on all the leaves of the tree.

The tree is guaranteed to be finite because $0$-dimensional hyperellipsoids are single points.

The 'worst case' maximum number of nodes in the tree is $2^{n}n!$

$\endgroup$
  • $\begingroup$ Appreciate the answer. So in the event that its maximum constrained to the equality constraint violates one or more of the inequalities (very likely in practice), why is it that the dimension reduction sets each inequality constraint to its lower and upper bound? Also, aren't O(2^nn!) algorithms pretty universally frowned upon? $\endgroup$ – AsinglePANCAKE Dec 30 '15 at 15:38
  • $\begingroup$ 1. If the maximum over the entire ellipsoid is reached within the bounds of our block then such maximum can be found by differential analysis (i.e., the trick with the normal). If it is not then the maximum subject to the constraints will be reached on the boundary of the cell, which is defined by equality of at least one of the $x_i$ with $l_i$ or $u_i$. $\endgroup$ – Justpassingby Dec 30 '15 at 16:25
  • $\begingroup$ 2. I have to admit that I was not aiming for low computational complexity. Computer programmers might frown where mathematicians happily apply transfinite induction:-) Having said that, one could probably do a lot of pruning with some extra analysis. For example, it might be that we only need to consider those $i$ where the $i$-th constraint is actually violated, and in that case only one of the two bounds. I can't do that off the top of my head though. $\endgroup$ – Justpassingby Dec 30 '15 at 16:33
  • $\begingroup$ on 1. Is there a theorem that says it has to be on the boundary? I'm assuming that optimizing a linear function on a convex constraint set implies that the optimum appears on the boundary, but is our constraint space actually convex? Apologies if the question is ill-posed, I'm just a bit confused by the dimensionality reduction in the algorithm you suggested. In particular, how it takes advantage of the linearity of our objective function. $\endgroup$ – AsinglePANCAKE Dec 30 '15 at 17:05
  • $\begingroup$ 2bis. The algorithm is doing redundant work because many of the lower dimensional hyperellipsoids serve as boundaries to multiple hyperellipsoids of one dimension higher. The actual maximum number of nodes in the tree is the number of simplices of all dimensions combined that make up an $n$-dimensional hypercube, i.e., $3^n$ (exactly $2^{n-k}C^n_k$ at dimension $k$). $\endgroup$ – Justpassingby Dec 30 '15 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.