[proglin] formulate max |x|..

[Jose Coelho de Pina <coelho@ime.usp.br>]

A seguinte troca de mensagens apareceu recentemente
na lista ORCS-L. 

Paulo.

-----------------------------------------------------------

Date: Mon, 02 Apr 2001 11:57:03 -0400
From: "Paul A. Rubin" <rubin@msu.edu>
Subject: formulate max |x|..
To: Wil <sunmoon210b@netscape.net>

The answer to the question is "yes and no".  There are three possibilities:

1)  The constraint system is inconsistent (i.e., the problem is
infeasible).  An LP can detect this.  The objective function in this case
is irrelevant, so you might as well just maximize 0.

2)  The feasible region contains a single point.  Again, you can find it by
solving an LP with any objective.  *Recognizing* that the feasible region
is a singleton is another matter.  You could try alternately maximizing and
minimizing each component of x.  If the max and min of each component are
equal, that proves it's a singleton (to within numerical precision limits,
anyway).

3) The feasible region has affine dimension >= 1.  This happens if the
constraints are consistent and A has nullity >= 1.  In this case, the
problem is automatically unbounded (in any norm), so the problem is
unbounded, and you don't have to worry about concavity (or lack thereof) in
the objective.

-- Paul

Wil wrote:

> hi,
>
> I have a problem:
> max |x|
> st
>      Ax = b
>      x free
> Is it possible to model it as some LP?
> if it's min |x|, then, I know at least two ways to solve it. 
> However, it seems max |x| is different.
> If possible, do not use the "either" "or" IP formulation to solve this.
> Please give me some help. Thanks.

--
***************************************************************************

Paul A. Rubin                                    Phone:    (517) 432-3509
Department of Management                         Fax:      (517) 432-1111
The Eli Broad Graduate School of Management      E-mail:   rubin@msu.edu
Michigan State University                        http://www.msu.edu/~rubin/

East Lansing, MI  48824-1122  (USA)
***************************************************************************