Prev: MatLab Kmeans and large data set
Next: want to make linear filter to a video
From: Mauricio Varela on 17 Apr 2010 17:35
Hi. I'm trying to run a problem of the type min f(x) s.t. g(x)=0 . And I would like to optimization routine to honor g(x)=0 at each iteration. I've set the options to run with the interior-point method and the honor constraints option. Nevertheless the optimizer violates the constraint (feasibility error is not 0). And it does so by not a small amount (the violation gets to numbers larger than 1). And of course the optimizer doesn't converge since it drifts off into numbers that make no sense.

I cannot supply a gradient because the constraint is highly non-linear - I guess I could program a finite differences gradient myself and supply that vector, but that shouldn't be any different then the finite difference gradient fmincon generates by itself-. Any ideas on why this is happening, and what can I do about it? I tried using Knitro but I get the same problem. Thanks, Mauricio
From: Alan Weiss on 19 Apr 2010 08:18
Honoring bounds means satisfying an inequality of the type
x <= a
where x is the variable that can change and a is a constant. In your
problem you are asking that a nonlinear equation be satisfied at each
iteration. fmincon does not promise to do that.

You might be able to help fmincon keep closer to the constraint region
by changing g so that it is a factor of, say, 1000 larger.

Alan Weiss
MATLAB mathematical toolbox documentation

On 4/17/2010 5:35 PM, Mauricio Varela wrote:
> Hi. I'm trying to run a problem of the type min f(x) s.t. g(x)=0 . And I
> would like to optimization routine to honor g(x)=0 at each iteration.
> I've set the options to run with the interior-point method and the honor
> constraints option. Nevertheless the optimizer violates the constraint
> (feasibility error is not 0). And it does so by not a small amount (the
> violation gets to numbers larger than 1). And of course the optimizer
> doesn't converge since it drifts off into numbers that make no sense.
>
> I cannot supply a gradient because the constraint is highly non-linear -
> I guess I could program a finite differences gradient myself and supply
> that vector, but that shouldn't be any different then the finite
> difference gradient fmincon generates by itself-. Any ideas on why this
> is happening, and what can I do about it? I tried using Knitro but I get
> the same problem. Thanks, Mauricio

From: James Allison on 20 Apr 2010 16:38
Perhaps you could try a nested approach with an equation solver. For
example, if x has length 5, and g(x) has length 3, then you really have
two degrees of freedom in the optimization problem. Choose two variables
as optimization variables, and the remaining three can be determined at
each optimization iteration using a nonlinear equation solver, such as
fsolve. In other words, the formulation might be something like:

minimize f2([x1 x2])
with respect to [x1 x2]

where f2([x1 x2]) is the value of your original objective function f(x),
where x1 and x2 are specified input arguments, and [x3 x4 x5] are given
by the solution to:

g2([x3 x4 x5]) = 0

where g2([x3 x4 x5]) is defined as the original nonlinear equality
constraint g([x1 x2 x3 x4 x5]), but with fixed values for x1 and x2. To
clarify, for every iteration of the optimization algorithm, values for
x1 and x2 are passed to the equation solver as fixed parameters, which
then solves for [x3 x4 x5].

The trick is to choose an appropriate partition, i.e., which variables
should be optimization variables, and which should be obtained using an
equation solver. Also note that the top-level optimization problem may
be an unconstrained problem in this case if there are no variable
bounds, so fminunc may be what you need to solve the optimization problem.

What I described is in essence an implementation of the
multidisciplinary feasible formulation (MDF), which historically has
used fixed-point iteration to solve the inner system of equations
problem. Your g(x) is like the constraint given in equation 1, or h_aux
in equation 3, of:

http://ode.engin.umich.edu/publications/PapalambrosPapers/2007/232.pdf

except the problems discussed in this paper also have additional
equality and inequality constraints. In this paper x are the
optimization variables, and y are the variables solved by the inner
equation solver (at least in the MDF case).

The individual disciplinary feasible (IDF) formulation allows for
inconsistency during the solution process, which is what you and Alan
described. Meeting the equality constraints in this case is only assured
at convergence. In many cases IDF, i.e., allowing the optimization
algorithm solve the equality constraints directly, is more efficient
than MDF; IDF is free to trace a more efficient path through the
optimization space.

-James

Mauricio Varela wrote:
> Hi. I'm trying to run a problem of the type min f(x) s.t. g(x)=0 . And I
> would like to optimization routine to honor g(x)=0 at each iteration.
> I've set the options to run with the interior-point method and the honor
> constraints option. Nevertheless the optimizer violates the constraint
> (feasibility error is not 0). And it does so by not a small amount (the
> violation gets to numbers larger than 1). And of course the optimizer
> doesn't converge since it drifts off into numbers that make no sense.
>
> I cannot supply a gradient because the constraint is highly non-linear -
> I guess I could program a finite differences gradient myself and supply
> that vector, but that shouldn't be any different then the finite
> difference gradient fmincon generates by itself-. Any ideas on why this
> is happening, and what can I do about it? I tried using Knitro but I get
> the same problem. Thanks, Mauricio
From: Mauricio Varela on 20 Apr 2010 17:21
Thanks. What I ended up doing is realizing that g(x) is a smooth function that is (weakly) positive. Thus, I changed the optimization problem to solve: min f(x) + mu*g(x) where mu is large. I guess this is something that is built into fmincon, since it is a variant of the l1 penalty method. I say a variant because smoothness of g(x) and the fact that it is weakly positive everywhere guarantees that the extended penalty function is smooth; so no corrections are needed for non-smoothness.
 | 
Pages: 1
Prev: MatLab Kmeans and large data set
Next: want to make linear filter to a video