8
$\begingroup$

I have a simple (few variables), continuous, twice differentiable convex function that I wish to minimize over the unit simplex. In other words, $\min. f(\mathbf{x})$, $\text{s.t. } \mathbf{0} \preceq x$ and $\mathbf{1}^\top \mathbf{x} = {1}$. This will have to be performed multiple times.

What is a good optimization method to use? Preferably fairly simple to describe and implement?

There are some really fancy methods (such as “Mirror descent and nonlinear projected subgradient methods for convex optimization”, Beck and Teboulle) that specifically have methods for minimizing over the unit simplex. But these methods only use the gradient and not the Hessian.

$\endgroup$
7
  • $\begingroup$ If the function is convex, why wouldn't a simple line search method work? Since the objective function is twice-differentiable, I'd think Newton's method would work fine -- if only once-differentiable, gradient descent should work. Both are extremely well documented online with pseudocode and application-specific code abound. $\endgroup$
    – jedwards
    Dec 6, 2011 at 3:34
  • $\begingroup$ How about the "Karush–Kuhn–Tucker conditions"? en.wikipedia.org/wiki/… $\endgroup$
    – matt
    Dec 6, 2011 at 12:35
  • $\begingroup$ Thanks for the kind reply. I was wondering if there is a specific algorithm for minimization over the unit simplex that uses the Hessian (since it is easily calculated and the problem size is small). (I am still new to convex optimization) In the end I implemented the Interior Point method and it works well. $\endgroup$
    – dcm29
    Dec 12, 2011 at 3:05
  • 2
    $\begingroup$ This answer probably comes to late, but have you already looked into the paper "Projected newton methods for optimization problems with simple constraints" by Bertsekas (SIAM J. Control and Optimization, Vol. 20, No. 2, March 1982)? As the title says, a projected Newton algorithm is introduced together with an Armijo-like linesearch. Also, superlinear convergence is proved for simple constraints. The above problem is listed as an example. $\endgroup$
    – user103342
    Oct 26, 2013 at 11:12
  • $\begingroup$ See the paper... Efficient Projections onto the l1-Ball for Learning in High Dimensions This paper can perfectly solve your objective. $\endgroup$
    – Lia
    Nov 22, 2013 at 13:16

2 Answers 2

Reset to default
3
$\begingroup$

The Exponentiated Gradient Descend algorithm may be another approach simple to implement.

The Lecture Notes from the University of Chicago - Exponentiated Gradient Descent gives a nice overview..

$\endgroup$
1
$\begingroup$

The simplest, yet pretty fast method (In running time, not iteration time), would be Accelerated Projected Gradient Descent method.

All you need is to calculate the Gradient of the function $ f \left( x \right) $ and project each iteration onto the Unit Simplex.

A MATLAB Code would be:

simplexRadius = 1;
stopThr = 1e-5;
vX = vXInit;

for ii = 1:numIterations

    vG = CalcFunGrad(vX); %<! The Gradient
    vX = vX - (stepSize * vG);
    vX = ProjectSimplex(vX, simplexRadius, stopThr);

end

You can have the Simplex Projection function from the link I pasted (Or directly in my Ball Projection GitHub Repository).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .