# nonlinear programming with support constraint

I want to solve a nonlinear optimization problem $$\underset{\mathbf{x}\in \mathbb{R}^n}{\operatorname{argmin}} f(\mathbf{x})$$ subject to a support constraint $$\mathbf{x}=[x_1,\cdots,x_n]^T, \quad x_1=x_2=\cdots=x_i=0,\quad x_j=x_{j+1}=\cdots=x_n=0 \quad (1<i<j<n)$$

Is there any algorithm or library able to solve this kind of problem?

-

If $i$ and $j$ are known, then the resulting constraints on $x_{1}, \ldots, x_{i}$ and $x_{j}, \ldots, x_{n}$ are all linear, and easy to implement in nonlinear programming solvers.

However, if $i$ and $j$ are actually decision variables, then the problem should be formulated as a mixed-integer nonlinear program (MINLP) and solved using an MINLP solver.

Perhaps I'm misunderstanding the question?

-
Hi Geoff, you're right, i and j are known in my case. Could you elaborate how to incorporate the constrain? Right now, I'm using nonlinear conjugate gradient method, and I include the constraint by set $x_1, \cdots, x_i$ and $x_j,\cdots,x_n$ to be zero right after each update of $\mathbf{x}$. But I am not sure if this is reasonable. –  chaohuang Feb 23 '13 at 3:34
I haven't programmed nonlinear CG; I tend to use high-level nonlinear optimization libraries that accept nonlinear programs as arguments, in which case these constraints are just additional arguments to a solver call. In terms of matrix operations, the simplest way to implement your constraints is to treat $f$ as a function of the variables $x_{i+1}, \ldots, x_{j-1}$ only, and set the remaining variables to zero. The resulting function can be treated as an unconstrained problem (because in those variables, it is). Using nonlinear CG on this problem will make matrix operations more efficient. –  Geoff Oxberry Feb 23 '13 at 8:45
It would be overkill (and perhaps harmful) to consider your problem as a constrained optimization problem. Simply eliminate the variables $x_1, \ldots, x_i$ and $x_j, \ldots, x_n$. You are left with an unconstrained problem in the variables $x_{i+1}, \ldots, x_{j-1}$. You can use any unconstrained method (Newton if you have second derivatives, (L-)BFGS, nonlinear CG, etc.) –  Dominique Feb 23 '13 at 21:17
@Dominique: I just said that. –  Geoff Oxberry Feb 23 '13 at 22:17
@GeoffOxberry Sorry I must have missed your comment, but it's worth stressing that the OP's problem is inherently unconstrained. –  Dominique Feb 24 '13 at 4:09

As Geoff Oxberry points out in his comment, if you know a priori that $x_k=0$ for $k\leq i$ and $k\geq j$, then there's nothing to optimize with respect to these variables and you can just solve the (smaller) reduced unconstrained problem $\min_{x\in\mathbb{R}^{j-i-1}}\hat f(x)$, where $\hat f$ takes only the nonzero variables as input.

If this is not feasible for some reason, you might want to update your question to include this in order to get concrete advice. But to address the question in your comment: One possible approach to solve a constrained optimization problem of the form $\min_{x\in C} f(x)$ for some (convex) set $C\subset\mathbb{R}^n$ (in your case, $C=\{x\in\mathbb{R}^n: x_k=0,\ k\leq i \text{ or }k\geq j\}$) is projected gradient descent (which is a special instance of proximal gradient methods), defined by the iteration $$x^{k+1} = P_C \left(x^k - \alpha_k f'(x^k)\right)$$ where $P_C$ is the projection onto the convex set $C$ (in your case, simply setting the corresponding $x_k$ to zero) and $\alpha_k$ is a suitable step size (e.g., of Armijo type). If $f$ is smooth, this iteration converges to a stationary point (which is a minimizer if $f$ is convex); see, e.g., PH Calamai, JJ Moré: Projected gradient methods for linearly constrained problems, Mathematical Programming 39, 93-116.

In principle, this is what you are doing, except you are using the conjugate gradient as a search direction instead of the gradient. I haven't checked the proofs, but I'd assume that your version should still work as long as you have a descent direction. Whether it is reasonable, though, depends on your definition (it is a bit of a sledgehammer approach...)

-

Even if $i$ and $j$ are known, this is hard if the object function is nonconvex. Therefore, if only the object function is convex or concave, you find exact solution of this problem. if the object function is nonconvex, you will find approximate solution of this problem by DC Programming.

-
Welcome to SciComp.SE! I've removed your greetings from the post, see the guidelines. I've also added LaTeX markup (using \$). –  Florian Brucker Jun 21 '13 at 11:57