Hi all,

I'm trying to solve the problem exposed at the end of section 2 of this paper. For simplicity I reproduce it here:

\[ \begin{matrix} \min & \sum_{i} u_i & + & v_i\\ \text{s.t.} & \sum_j a_j x_{ij} & + & u_i - v_i & \leq & c, & \quad i=1,\ldots, n\\ & & & v_i, ~u_i & \geq & 0, & \quad i=1,\ldots, n\\ & & & \prod_j a_j & = & \pm{1} \end{matrix} \]

the last constraint is the one i have a problem with (note that the \(a_j\)s are not constrained to be positive).

The author claims this problem is convex (because of the fact that the \(a_j\)s are not constrained positive this is not obvious to me).

At any rate, would you know of an academic friendly solver (either open-source or CPLEX) that could solve this type of problems? Or maybe this problem can be rewritten in standard form?

Thanks in advance

asked 04 Jan '12, 08:38

vak's gravatar image

vak
3314
accept rate: 0%

closed 16 Jan '14, 07:14

fbahr's gravatar image

fbahr ♦
4.6k716

The question has been closed for the following reason "The question is answered, right answer was accepted" by fbahr 16 Jan '14, 07:14


Are the \(x_{ij}\) parameters? If not, the inequality constraints are quadratic (and nonconvex).

If the \(a_j\) are unrestricted in sign, then your feasible region is clearly nonconvex because it omits any point with any \(a_j = 0\) but includes neighborhoods around those points.

The formulation looks "off" to me in any case. Let's assume the \(x_{ij}\) are sample data and the \(a_j\) are regression coefficients (to be determined). Now suppose that we change the signs of all observed values. I would expect that changing the signs of all the coefficients of the previous optimal fit would be the new optimal fit; but if the number of regression variables (dimension of \(a\)) is odd, this won't work, because the product will be -1 rather than 1.

link

answered 04 Jan '12, 13:42

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

edited 16 Jan '14, 07:10

fbahr's gravatar image

fbahr ♦
4.6k716

The paper at hand is on curve fitting in m-dimensional space. (It's by Chris Tofallis, thus: I only understand half of it - since he uses 's' as if it was a 'z'.) The \(x_{i,j}\)s are data points (\(i=1,..,n; j=1,..,m\)), so the only non-linear constraint is last one, \(\prod \limits_{j} a_j = \mathbf{\pm} 1\).

(04 Jan '12, 14:42) fbahr ♦
1

If they specify \(\prod_j a_j=\pm 1\) then I'm less skeptical about the formulation (but the feasible region is still nonconvex).

(04 Jan '12, 14:52) Paul Rubin ♦♦

No clue whether it's true or not, but here's what the paper actually states: "For fitted functions that are linear in the coefficients[,] the optimisation method for their estimation can be shown to be a convex fractional programme so that any optimum is both unique and global." [No proof or reference given.] And: "Whilst there are solution algorithms for fractional programmes, the unique global property implies that general convex solution methods can be used."

(04 Jan '12, 15:02) fbahr ♦

I think the author might have a wrong understanding of fractional programming as it requires denominator to be positive, but \(a_{j}\)s are URS.

(04 Jan '12, 15:09) Ehsan ♦

@Paul Rubin: Sorry for not posting the full model (with the double +/- constraints): i tried at first but the latex support would not work and it was becoming too confusing. Thanks for confirming that the feasible set is not convex.

(05 Jan '12, 04:59) vak

Your nonlinear constraint is not quadratic, hence, you could not solve your problem using CPLEX or Gurobi.

I recommend using LINGO because of its powerful nonlinear solver and easy interface. Regarding the academic licence option, I think its developer gives 6-month temporary educational research license key with no size limit. I've got one from them recently, however, I could not find any link on their website about this right now. You could ask their sales office if these licence keys are still offered.

link

answered 04 Jan '12, 11:53

Ehsan's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

You may also try Couenne. It is open-source, and works well. It is also available at NEOS (http://www.neos-server.org/neos/solvers/minco:Couenne/AMPL.html), so you don't even have to install anything. Just submit the problem in AMPL or GAMS format.

If you are solving the problem numerically, and if you assume ( a_i geq 0 ) you may want to rewrite the nonlinear constraint as ( sum_i(log a_i) = 0 ). It may work better for the solver.

link

answered 08 Jan '12, 20:22

ashutosh%20mahajan's gravatar image

ashutosh mah...
1506
accept rate: 0%

edited 08 Jan '12, 20:29

thanks for the link (unfortunatly, i can't assume a_i>0....)

(15 Jan '12, 13:47) vak

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231
×127
×79

Asked: 04 Jan '12, 08:38

Seen: 2,220 times

Last updated: 16 Jan '14, 07:14

OR-Exchange! Your site for questions, answers, and announcements about operations research.