# optimization of a separable function

Hello everyone,

this is a optimization problem whose objective function is separable:

$$F(x)=\sum_{i=1}^n\frac{\theta_i^2}{4}\sum_{j=1}^m\left(1+\rho x_ik_j+\sqrt{(x_ik_j+\rho)^2+1-\rho^2}-\frac{2\alpha_i^j}{\theta_i}\right)^2$$

where $x=(x_1,x_2,...,x_n)$ and $\rho$, $\theta_i$, $k_i$, $\alpha_i^j$ are given constants with $-1\leq\rho\leq 1$.

subject to

$$x_1\geq x_2\geq\cdots\geq x_n$$

$$\theta_1 x_1\leq\theta_2 x_2\leq\cdots\leq\theta_n x_n$$

$$0\leq x_i\leq X_i$$

where $X_i$ are also given constants.

For every component function

$$\left(1+\rho x_ik_j+\sqrt{(x_ik_j+\rho)^2+1-\rho^2}-\frac{2\alpha_i^j}{\theta_i}\right)^2$$

is not necessarily convex, we can not apply directly the Lagrangian multiplier. Another way is to solve this problem conditionally:

for $x_1,...,x_{n-1}$ fixed, consider the problem

$$F(x)=F(x_n)$$

subject to

$$x_n\leq x_{n-1}$$

$$\theta_{n-1}x_{n-1}\leq \theta_nx_n$$

$$0\leq x_n\leq X_n$$

Then we repeat by recurrence.

Because the form to optimize is not very complicated. From the computationall viewpoint or analytical viewpoint, does someone have an idea for this optimization problem?

Thanks a lot!

-
You can either solve this to a local optima using nonlinear programming (fast), solve to global optima using global optimization code (potentially computationally expensive), or solve a separable programming problem using piecewise-linear approximation of the [possibly] nonconvex objective function using SOS2 constraints--which is designed for problems like this--or simply using MIP constraints. Your method of minimizing $x$'s one-by-one (essentially solving $n$ univariate problems) may not give you a global solution unless a global solver is used in each instance. –  Gilead Jul 17 '12 at 21:31
Thank you for your reply. Could you please specify the numerical methods that you mentioned? For example nonlinear programming, piecewise-linear approximation, SOS2, MIP? Thanks a lot! –  Higgs88 Jul 31 '12 at 12:13
Hello Gilead, I have alos an idea which maybe costs so much. If we inherit the previous notations, then we denote $$f_i(x_i)=\left(1+\rho x_ik_j+\sqrt{(x_ik_j+\rho)^2+1-\rho^2}-\frac{2\alpha_i^j}{\theta_i}\right)^2$$ and define $$G_1(d,u)=\max_{d\leq x_1\leq \min(u,X_1)}f_1(x_1)$$ Then for $0<d\leq u$, $G_1(d,u)$ can be computed explicitly. We can then construct $G_i(d,u)$ by induction. Assume that we know $G_{i-1}(d,u)$, $\forall i\geq 2$ $$G_i(d,u)=\max_{d\leq x_i\leq \min(u,X_i)}G_{i-1}(x_i,\frac{\theta_{i-1}}{\theta_i}x_i)+f_i(x_i)$$ Could you give some comments? –  Higgs88 Jul 31 '12 at 12:40