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

accept rate: 0%

closed 16 Jan '14, 07:14

fbahr's gravatar image

fbahr ♦

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.


answered 04 Jan '12, 13:42

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

edited 16 Jan '14, 07:10

fbahr's gravatar image

fbahr ♦

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 ♦

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.


answered 04 Jan '12, 11:53

Ehsan's gravatar image

Ehsan ♦
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.


answered 08 Jan '12, 20:22

ashutosh%20mahajan's gravatar image

ashutosh mah...
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



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



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.