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

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|improve this question
add comment

1 Answer

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