Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. 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]$.

I know that a convex maximization problem is NP-hard, in general.

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

share|cite|improve this question

Yes, Convex Optimization with equality constraint is NP-Hard in general. However, there exist mature techniques that find very nice approximate solutions to convex optimization problems, like Coordinate Descent.

Suppose you use coordinate descent and the matrix A has rank $k$. You can fix n-k-1 coordinates of your feasible solution $x = (x_1, x_2, x_3, ..., x_n)$ and then the solution vectors in the solution space are uniquely determined by one coordinate, for example $x_i$. In that case, you can just take the derivative of $f(\cdot)$ with respect to $x_i$ to find the maximum in this iteration.

Then we iteratively fix n-k-1 coordinate and improve the solution until a approximately optimal one is found.

share|cite|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.