Nonlinear optimization problem with different types of constraints ?

[Horman]

Hello everyone,

I have a problem that involves different types of constraints: nonlinear, linear, logic. So the problem is like this:

---------------------
Minimize f(X)

S.t

Gi(X) <= 0 , i = 1,..,n (nonlinear/linear constraints)

Hj(X) = 1, j = 1,...,m (logic constraints)

The feasible set for X (lower bound/upper bound) can be discrete set ( X ∈ Bx ) or continuous ranges ( Xl <= X <= Xu)
----------------------

problems that have only NL/Linear constraints Gi(X) can be solved with existing tools.

But in my problem, I have to take into account the logic constraints Hj(X). These constraints cannot be expressed in analytical formula (here I just write those constraints in this way for easy understanding)
e.g., to compute Hj(X) at a given X, I have to perform a routine to check some logic conditions to ensure Hj(X) = 1 or 0.

Right now, the method I'm solving this problem is in two steps:
1. Find all possible feasible ranges/set for X that satisfy Hj(X), let call the set B
2. Solve classical problem with only constraints Gi(X) for X ∈ B

sometimes I find this way is not really the best way since it may overlook many cases.
So I've tried to look for similar form as mixed integer programming problems... but still not found something really clear to my problem.

Can anyone suggest me a better solution ? or known any optimization tool that might solve my problem efficiently ?

Thanks,
Horman

 

[JeffM]

Hello everyone,

I have a problem that involves different types of constraints: nonlinear, linear, logic. So the problem is like this:

---------------------
Minimize f(X)

S.t

Gi(X) <= 0 , i = 1,..,n (nonlinear/linear constraints)

Hj(X) = 1, j = 1,...,m (logic constraints)

The feasible set for X (lower bound/upper bound) can be discrete set ( X ∈ Bx ) or continuous ranges ( Xl <= X <= Xu)
----------------------

problems that have only NL/Linear constraints Gi(X) can be solved with existing tools.

But in my problem, I have to take into account the logic constraints Hj(X). These constraints cannot be expressed in analytical formula (here I just write those constraints in this way for easy understanding)
e.g., to compute Hj(X) at a given X, I have to perform a routine to check some logic conditions to ensure Hj(X) = 1 or 0.

Right now, the method I'm solving this problem is in two steps:
1. Find all possible feasible ranges/set for X that satisfy Hj(X), let call the set B
2. Solve classical problem with only constraints Gi(X) for X ∈ B

sometimes I find this way is not really the best way since it may overlook many cases.
So I've tried to look for similar form as mixed integer programming problems... but still not found something really clear to my problem.

Can anyone suggest me a better solution ? or known any optimization tool that might solve my problem efficiently ?

Thanks,
Horman

I do not understand the problem if X is a number rather than an ordered n-tuple of numbers.

Assume X is a real number and the objective is to maximize (minimize) $\displaystyle \Omega (X)$ subject to

(m + n) constraints represented by m differentiable functions of X and n logical constraints on X.

What domains within the real numbers satisfy all (m + n) constraints simultaneously. If the number of domains is finite (and I presume it is), determine with respect to each domain the local maxima (local minima) within that domain and choose the greatest (least) of them. Then choose greatest (least) among the domains' greatest (least).

If X is a vector rather than a scalar, doesn't the same process work, at least if you can define functions that delimit the domains that satisfy all constraints.

Perhaps, however, I do not understand the problem.

 

[Horman]

I do not understand the problem if X is a number

In my problem, X is a vector contains p elements (which are the deciding variables)

The problem is that, in my NLP, there are the n logic constraints that cannot be formulated in term of an analytic form of X so I cannot use classical optimization tools to solve my problem.

So I try to find a domain of X that satisfies n logic constraints first by an algorithm. Then I apply the classical opt tools to solve my problem with m nonlinear constraints. However in this way, I probably overlook many cases because the solution from the second step will depend on the domain found from the first step.

I try to look for a mix logic constraint/integer programming tools to solve my problem, but haven't found anytool yet.

 

[JeffM]

Your problem is almost certainly beyond me as a general matter. I'll drop on you what thoughts I have, but they may be silly.

The first thing I would do is to find the local optima satisfying the already analytic constraints and test whether the optimum of the optima meets the non-analytic constraints. If not, I would eliminate that and test the remaining optima. That's a nice finite iteration (if the number of local optima is finite).

However, there is no guarantee that the process above will work, and I am far from having the skills required to create a general process to move forward. Moreover, there may be no general way to move forward. It is hard for me to imagine a logical algorithm for finding whether a particular vector satisfies a specific constraint that can't be replicated by one or more bounding functions, but finding those functions may be very hard. That will depend on the nature of the constraints, but there is no reason to suppose a priori that the constraints that are actually rather than potentially binding will be hard to deal with analytically.

The reason for saying "potentially binding" is that an analysis of the logical constraints may find that any vector satisfying constraint A also satisfies other constraints. If you can determine that some of the constraints are effectively redundant, then the problem obviously becomes less complex (although it may still be intractable).

Sorry I could not be more help.