# Maximizing a convex function (minimizing a concave function) with a linear constraint

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?

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

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

The YALMIP Wiki

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

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.