Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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 at 9:28
add comment

4 Answers

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
add comment

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

The YALMIP Wiki

share|improve this answer
add comment

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
add comment

for convex optimization try out CVX with Matlab or Python (CVXOPT + CVXPY).

http://cvxr.com/cvx/ http://cvxopt.org/

Also check out Stanford U online course on convex optimization.

share|improve this answer
add comment

Your Answer

 
discard

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.