3
$\begingroup$

I have this very general problem (for $n>2$):

$$ \begin{align} & \max Z = f(x_1,\ldots ,x_n) \\[10pt] \text{s.t. } & \sum_{i=1}^{n} x_i = B \\[10pt] & x_i \geq 0 \end{align} $$

Assume that the function $f(x_1,\ldots,x_n)$ is not a "nice" function, non-linear, non-convex, hardly differentiable. Therefore, in general I cannot use the Lagrangian multipliers method. For finding the $x_i$'s, I am thinking to numerical optimization approaches.

My questions are:

1) Is there a common, smart and effective way to deal with such an equality constraint in numerical optimization?

2) Am I missing something? Do you have any other direction to suggest?

Thanks

$\endgroup$
1
  • $\begingroup$ (Years later) see the Softmax function: "squashes" $x \in R^n \to \, \ge 0, \sum 1$ . $\endgroup$
    – denis
    Sep 15, 2018 at 14:54

3 Answers 3

3
$\begingroup$

The methods to be used will be highly dependent on the character of $f$. If it is non-convex, there are many such algorithms; see this MO post for instance.

You might also wish to look into evolutionary algorithms, such as genetic algorithms and simulated annealing. These algorithms are often much slower, but have the feature that they can sometimes "bump" you out of local extrema. They are also fairly easy to implement.

You can also hybridize approaches: combine an evolutionary algorithm with a standard convex optimization approach on a locally convex subdomain.

Finally, with an equality constraint, you essentially reduce the dimensionality of your problem by 1. That is, one variable is completely determined by the others.

$$x_k = B - \sum_{i=1,\ i\neq k}^n x_i.$$

And then, depending on the character of your function, you might be able to use any sort of algorithm.

But to answer your questions, 1.) there are many common and smart ways, but they depend on your function $f$. I would start with the most simple, conventional approach, and then see whether it is effective. 2.) I don't think you're missing anything. Numerical optimization is a big topic and there are many ways to go about it.

$\endgroup$
2
  • $\begingroup$ The issue with the dimensionality reduction approach is to recover from solutions where $x_k <0$. I can think to several "repair" strategies, while it seems harder to encode the solutions in such a way that $x_k <0$ is automatically excluded. Any suggestion/reference in this respect? Thanks $\endgroup$
    – Libra
    Aug 12, 2012 at 13:55
  • 1
    $\begingroup$ @Libra It's fairly straightforward. Since $x_i \ge 0$ for all $i$, then simply replace $x_k$ with $B - \left(\sum_{i=1,\ i\neq k}^n x_i\right)$ everywhere in your function $f$. Then, you necessarily have the condition that $\sum_{i=1,\ i\neq k}^n x_i \le B$, and you have turned your equality constraint into an inequality constraint. $\endgroup$
    – Emily
    Aug 12, 2012 at 14:16
2
$\begingroup$

if $B > 0$ by dividing on B you can bring all your constraint, both equality and inequalities, to single "unit simplex constraint" There are a lot of papers for optimization on unit simplex. Some of them are using solving unconstrained problem and projecting it projection on unit simplex each iteration (projected gradient for example, google for it if interested) For projection on simplex algo check wiki:

http://en.wikipedia.org/wiki/Simplex#Projection_onto_the_standard_simplex

If cost function is non-convex you will have to use some form of trust region for those method to work.

Also most(or even all) of the method for optimization on $L_1$ ball are using methods which are also working for unit simplex constraint. You can google on that subject too.

Another (though it could be combined with first) approach is alternating direction method - separate you cost function into smooth and nonsmooth part

$F_0(x) = f(x) + g(x)$

and split them with new variables, after taht descend by x and u intermittengly

$F(x, u) = f(x) + g(u) + (x-u)^2$

and you can add simplex constraint here as well

$F(x, u, v) = f(x) + g(u) + \delta_\Delta^-(v) + (x-u)^2 + (x-v)^2$

It usually used in the form of augmented Lagrangian or ADMM -Alternating Direction Method of Multipliers

All this assume g is convex and and f can be approximated by convex at least locally

$\endgroup$
1
$\begingroup$

I would not be worried about the equality constraint since it can be handled in almost all optimization packages. This is because $g(x) = a$ can always be written as two inequality constraints: $g(x) \leq a$ and $g(x) \geq a$. You can also remove one optimization variable using this constraint, as mentioned by Ed Gorcenski.

The troubling part seems to be the objective. Particularly, non-differentiability is a cause of concern. I suggest putting a "nice" lower bound on $f$ and maximizing it instead. A suitable class of algorithms to look into is "Majorization-Minimization" (or "Minorization-Maximization" for your case). The idea is to solve a sequence of simpler optimization problems. At the $k^{th}$ iteration:

  1. Construct a lower bound on $f(x)$ by finding a function $g(x;x_{t-1})$ such that: $f(x_{t-1}) = g(x_{t-1};x_{t-1})$ and $g(x;x_{t-1}) \leq f(x) \forall x$. This bound is parameterized by $x_{t-1}$, and is said to minorize $f(x)$.
  2. Solve an easier optimization problem by replacing $f(x)$ by $g(x;x_{t-1})$ in the original problem. The solution to this problem is $x_t$.

The conditions in (1) ensure that $f(x_t) \geq f(x_{t-1})$, i.e. your objective is always monotonically non-decreasing. You will ultimately converge to a local maxima.

Some common tricks for finding nice bounds on unwieldy objective functions are given in: D. R. Hunter, K. Lange, A tutorial on MM algorithms, The American Statistician, vol. 58, no. 1, pp. 30-37, 2004.

$\endgroup$

You must log in to answer this question.

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