Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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?

share|improve this question
add comment

3 Answers 3

up vote 2 down vote accepted

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?

share|improve this answer
    
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
1  
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
add comment

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...)

share|improve this answer
add comment

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.

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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