Re: optimization problem help

In article <1120450736.865299.252870@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
John <weekender_ny@xxxxxxxxx> wrote:
>I need to solve the following optimization problem
>for a given y. b1,b2,b3 are vectors of dimension n x 1.
>wi's are scalar.
>
>min || y - yy ||^2
>
>st
>
> w1 * b1^T.yy = 0
> w2 * b2^T.yy = 0
> w3 * b3^T.yy = 0
> w1+w2+w3 = 1
> w1 > 0 w2 >0 w3 >0

Are you sure you're stating the problem correctly?
Surely you must mean wi >= 0, not > 0. Otherwise the wi seem to
be irrelevant.
Also, I assume the variables are the vector yy and the scalars
w1, w2, w3, while b1, b2 and b3 are given as well as y.

>Anyone can tell me if this problem is convex?
>Seems to me because the constraints are all convex and the
>objective function too. What is a good way to solve the problem
>in practice? Any libraries that could solve this in c/c++.

The constraints wi * bi^T.yy = 0 are not convex: they are equivalent
to wi = 0 _or_ bi^T.yy = 0. If you take one solution where wi = 0
but bi^T.yy <> 0, and another where bi^T.yy = 0 and wi <> 0, the
midpoint of these will not satisfy the constraint.

The only thing requiring any of the wi to be nonzero is w1+w2+w3=1.
And since all you really care about is which wi are nonzero, you
may as well take one wi = 1 and the others 0. Thus you are requiring
one of the three constraints b1^T.yy = 0, b2^T.yy = 0, b3^T.yy = 0.
The simplest thing to do is to solve the three linear least-squares
problems

min ||y - yy||^2 st bi^T.yy = 0

and take the one whose objective value is least.

Robert Israel israel@xxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
.

Relevant Pages

  • Re: fmincon
    ... >>> I am using 'fmincon' from the optimization toolboox of Matlab ... >> and produces a scalar result. ... >> f, subject to the constraints. ... > The constraints do use the same vector x as the objective function. ...
    (comp.soft-sys.matlab)
  • Re: Using fmincon to optimise vectors?
    ... > I've now replaced the scalar x values with vectors of the form you ... > think I may have to review my constraints. ... If you have multiple objectives that you wish to ... The best material model of a cat is another, or preferably the same, cat. ...
    (comp.soft-sys.matlab)
  • 0-1 Quadratic programming
    ... vector, d is scalar) ... I have found on wikipedia, that 'If there are only equality ... constraints, then the QP can be solved by a linear system'. ...
    (sci.math)
  • Re: Handling a scalar along with a matrix varible in fmincon
    ... there is also a scalar variable that I wish to minimize ... simultaneously while optimizing the matrix. ... constraint functions, reshape the first n*m elements of the vector into the ... % Assuming your objective function is called myobjective ...
    (sci.math.num-analysis)
Loading