Constrained optimization: equality constraint

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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.