Strong duality and coordniate transform

[lementin]

Hello all,

Assume we have an optimization problem and that strong duality holds. Will it also hold for another optimization problem obtained from the initial by a bijective coordinates transform?

Thank you in advance.

 

[chiro]

Hey lementin and welcome to the forums.

I'm going to base this reply on three things: topology, orientation and curvature differences of the co-ordinate transformations.

The questions relate to if these things remain constant between co-ordinate system transformations: i.e. does the topology of both spaces, the orientation of both spaces, and the curvature of both spaces remain the same?

 

[lementin]

Hi, chiro. Thank you for your reply.
The original domain is a simplex and the transformed problem is obtained by incorporating the linear condition and, thus reducing the dimensionality to n-1. That being said the topologies of two domains are different. For curvature and orientation, I'm not sure if they can be applied to the second domain (only to its border). Anyways, I think we can say, that they are different from the primary domain.

The original problem was to find the projection of an arbitrary vector onto n-dimensional simplex. I wanted to prove the equivalence since in the derived problem we can easily prove Slater condition, whereas the original problem is computationally easier to tackle .

 

[chiro]

One suggestion I have is to look up the invariance principle for a simple optimization problem (as in the basic Lagrange multiplier formulation) and see what the constraints are for the simplest problems (or even the ones you can find). If you have to do this yourself, the thing you will have to show is to prove that under a specific transformation: minimums in one space will be minimums in another and maximums in one space will be maximums in another.

You have a simplex so it's not like having a spherical or hyperbolic geometry which will make things more palateable.

I can't think right now of any other way other than to do it from first principles and I don't actually know much optimization in depth, but if I was faced with this problem that's what I would do.

In terms of the projection though, I'd imagine if you have a co-ordinate transform that this would be a lot more straightforward since you can define a projection operator in one space and then use the bijective nature to map the transform in one space to one in another. I'm assuming your projection is a linear one (i.e. using a matrix) so if you can map the projection matrix from one space to the next, then you're done.

I'd this by mapping the basis vectors the right way and then taking the basis and transforming the projection operator to work on those new basis vectors since the operator is just going to be performed on a vector with respect to its elements that represent basis transformations.

In other words you have your operator P, and it has column vectors corresponding to the bases used to transform your vector v when you apply Pv, and transforming these basis vectors to your new space and taking into account the geometry should give you a new operator in the new space, as long as the topology is consistent (i.e. maintain specific continuity, no non-simple regions, etc).

What do you think?

 

[lementin]

I actually found a walkaround and solved my problem by a completely different method.

Concerning the original problem: I did a little research comparing the duals of the original and the derived problems, and they seem to be equivalent (in particular, minumums do coincide). Thus, the answer to my question in this particular settings seems to be positive.

The projection in my case is not a linear operator (it is defined as a minimization of the distance from a point to the simplex).

Thank you very much for your help, chiro.