11
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ Have you tried using Lagrange multipliers to see if that transforms it into something more tractable? $\endgroup$
    – N. Virgo
    Mar 5, 2014 at 9:28

4 Answers 4

Reset to default
8
$\begingroup$

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").

Improve this answer
$\endgroup$
2
$\begingroup$

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

The YALMIP Wiki

Improve this answer
$\endgroup$
2
$\begingroup$

This problem can be seen as a difference of convex functions (DC) programming problem. There is an extensive literature on DC programming, you can search related studies there. One of the most well known method is the DCA method, see for example: http://lma.univ-pau.fr/meet/mamern09/en/Lethi-MAMERN09.pdf

Another recent paper that surveys the DC literature to some extent and might be handy is: https://arxiv.org/pdf/1511.01796.pdf

You can also use some more general method for nonsmooth problems, for example the prox-based method given in: http://num.math.uni-goettingen.de/~ssabach/BST2013.pdf

Improve this answer
$\endgroup$
1
  • $\begingroup$ Just to expand on this answer, a typical DC program consists minimizing the objective function $f(x) - g(x)$, where $f$ and $g$ are convex. If we let $f(x) = 0$ for every $x$, then this is equivalent to minimizing the concave function $-g(x)$. More details about this can be found in this paper, and a Python implementation for solving a DC program can be found here. $\endgroup$
    – mhdadk
    Sep 26 at 20:23
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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