Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The problem is $$\max f(\mathbf{x}) \text{ subject to } \mathbf{Ax} = \mathbf{b}$$

where $f(\mathbf{x}) = \sum_{i=1}^N\sqrt{1+\frac{x_i^4}{(\sum_{i=1}^{N}x_i^2)^2}}$,
$\mathbf{x} = [x_1,x_2,...,x_N]^T \in \mathbb{R}^{N\times 1}$, and
$\mathbf{A} \in \mathbb{R}^{M\times N} $

We can see that $f(.)$ is in the form of $\sqrt{1+y^2}$ and is a convex function.
It can be also shown that f(.) is bounded in $[\sqrt{2}, 2]$.

This is a convex minimization problem with a linear constraint.

Which are the standard algorithms used to solve these kind of problems?

Using the specific nature of the problem, is it possible to solve it using any standard optimization software/package?

share|improve this question
Have you tried using Lagrange multipliers to see if that transforms it into something more tractable? – Nathaniel Mar 5 '14 at 9:28

You can take advantage of the structure of the problem, though I know of no prepackaged solver that will do so for you.

Essentially, what you're looking for is minimizing a concave function over a convex polytope (or convex polyhedron). A quick search pulled up a few relevant sources (I vaguely remember one of these being mentioned when I took a class on nonlinear programming over four years ago):

Falk, J. E., and Hoffman, K. L. Concave minimization via collapsing polytopes, Operations Research, 1986, Vol. 34, No. 6, p. 919-929.

Hoffman, K. L. A method for globally minimizing convex functions over convex sets, Mathematical Programming, 1981, Vol. 20, p. 22-31.

Benson, H. P. A finite algorithm for concave minimization over a polyhedron, Naval Research Logistics, 1985, Vol. 32, No. 1, p. 165-177.

A bunch of references on Christophe Meyer's web site.

There are more sources if you Google "minimize concave function over polytope" (or replace "polytope" with "polyhedron").

share|improve this answer

I attended some years ago a lecture on optimisation. Back then we used Matlab in combination with YALMIP.


share|improve this answer

I'd offer the Frank Wolfe algorithm and related methods for your consideration. Basically, you linearize the objective function and solve the resulting LP at each iteration. I do think, however, that you would need to add bounds on $x$ to make this approach effective.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.