Re: maximum function


Hi,

Chip is correct, I would like to have as manystrict inequalities as
possible.
As I wrote before, A1*Xm,1+A2*Xm,2+....+An*Xm,n>0, or <=0. No >=
allowed.

I am looking for the set {A1,..,An} which will satisfy as many
inequalities as possible.

Thanks,
Asi


On Jan 30, 7:16 pm, "Chip Eastham" <hardm...@xxxxxxxxx> wrote:
On Jan 30, 11:29 am, "C...@xxxxxxx" <C...@xxxxxxx> wrote:





On Jan 29, 9:07 am, "g_asi2" <g_a...@xxxxxxxxx> wrote:

Hi,

I am looking for some kind of function, but I don't know if such
exist.

The requirement is as followed:

I got a list of m inequalities with n parameters.

A1*Xm,1+A2*Xm,2+....+An*Xm,n>0 (or <0),
Where Xi,j equal to 1 or -1.This can be formulated a a standard mixed-integer programming problem.
I will assume you actually mean >=0 and <=0, rather than strict
inequalities (just on the basis of many years of experience with
students' mis-use of terminology). By changing signs, if necessary, we
can assume all inequalities are of <= type. Let f_i = sum
(x_{i,j}*A_j :j=1..n) for i = 1..m. Here (confusingly) the x_{i,j} are
known parameters in {-1,1} and the A_j are variables. If, for some
{A_j} a collection I satisfies f_i <= 0 for all i in I, then this
remains true by re-acaling the A_j. Therefore, we may assume -1 <= A_j
<= 1 for all j. Therefore, for any such {A_j} we always have -n <= f_i
<= n.

Now introduce binary variables z_i for i = 1,...,m. We want to have
z_i = 1 if f_i <= 0 and z_i = 0 if f_i > 0. We want to maximize
sum(z_i: i=1..m). To do this, it is enough to impose the constraints
f_i <= n*(1-z_i).

If z_i = 1 this forces f_i <= 0, while if z_i = 0 it says f_i <= n,
which is redundant. Note that a _feasible_ solution could have z_i = 0
and f_i <=0, but this will not happen in an *optimal* solution. The
final formulation is

max sum(z_i:i=1..m)
st.
sum(x_{i,j}*A_j :j=1..n) <= n*(1-z_i) for i=1...m,
-1 <= A_j <= 1 for j=1...n
z_i = 0,1 for i=1...m

R.G. VicksonAs I read your problem formulation, we could take
all z_i = 1 and all A_j = 0, thereby max'ing out the
objective function.

It seems likely to me that the OP wants to
attain strict inequality in as many constraints
as possible.

--c- Hide quoted text -- Show quoted text -

.

Relevant Pages

  • Re: Optimizing using KKT...
    ... The constraints are: ... us two inequalities on k1, k2 and k3 that must hold. ... inequalities, we get two inequalities in k1 and k2 alone; ... and k2 be continuous and then deal with the continuous problem. ...
    (sci.math)
  • Re: Lagrange mutlipliers and solution methods
    ... >there is no inequalities. ... where the equality constraints (a set of linear equalities) are expressed as ...
    (sci.math.num-analysis)
  • Re: Constraints function for nonlinear program
    ... I have omitted to say that constraints inequalities ... (If you had nonlinear inequalities and absolutely ... by passing in a cell array of anonymous functions.) ...
    (comp.soft-sys.matlab)
  • Re: maximum function
    ... Where Xi,j equal to 1 or -1.This can be formulated a a standard mixed-integer programming problem. ... inequalities (just on the basis of many years of experience with ... it is enough to impose the constraints ... As I read your problem formulation, ...
    (sci.math)
  • Re: How do we convert inequalities constraints using lagrange multipliers?
    ... I'm interested in solving constained-minimization problems where my ... constraints are inequalities, I want to know how to express them using ...
    (sci.math)