3
$\begingroup$

everyone.

It has been well known that the following minimization problem of a Bregman divergence with linear inequality can be solved by successively projecting the current point to each constraint $\mathbf{a}_i^\top\mathbf{x}\leq b_i$ with a correction step, where $A=\begin{bmatrix} \mathbf{a}_1 & \ldots & \mathbf{a}_n \end{bmatrix}$, $\mathbf{b}=\begin{bmatrix} b_1 & \ldots & b_n \end{bmatrix}^\top$ and $n$ is the number of the constraints. \begin{align} \min_\mathbf{x}&D_\varphi(\mathbf{x},\mathbf{y})\\ \mathrm{s.t.}&A^\top\mathbf{x}\leq\mathbf{b} \end{align}

Since each linear inequality constraint defines a half-space and the intersection of these half-spaces is a polyhedron, it is indeed an optimization problem on a polyhedron.

However, if the polyhedron is given by the convex hull description spanned by a set of vectors $\{\mathbf{v}_i\}_{i=1}^n$, i.e. \begin{align} \min_{\mathbf{x},\alpha}&D_\varphi(\mathbf{x},\mathbf{y})\\ \mathrm{s.t.}&\mathbf{x}=\sum_{i=1}^n{\alpha_i\mathbf{v}_i}\\ &0\leq\alpha_i\leq 1,\;\forall i=1,\ldots,n\\ &\sum_{i=1}^n{\alpha_i}=1 \end{align} how can it be solved?

It seems that the problem can be solved by first converting the convex hull constraint to its half-space description, which is composed of a set of linear inequality constraints, and then applying the successive projection algorithm. However, it is not simple to obtain such a representation except in some special cases. Then, how can I solve this problem?

Any suggestion is welcome and I appreciate your help. Thank you very much!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

I am not aware of this successive projection algorithm: Can you provide a reference for it? In principle, I don't see a problem with what you are doing, because you only have $n$ nonnegativity constraints for the $\alpha$s, and two more for the equality constraint; unless you need a full-dimensional polytope for your successive projection to work.

If you are using Bregman divergence for minimizing a convex function, and your domain can be described as a simplex (of extreme points), you may want to try a non-Euclidean Bregman divergence, such as the entropy, or by \ell^p norms. They give much better complexity estimates, see e.g.

  1. Section 2, in: Nesterov, Nemirovski. On first order algorithms for \ell_1/nuclear norm minimization [2013]. http://www2.isye.gatech.edu/~nemirovs/ActaFinal_2013.pdf

  2. Section 5.7, in: Juditsky, Nemirovski. First Order Methods for Nonsmooth Large-Scale Convex Optimization [2012]. http://www2.isye.gatech.edu/~nemirovs/MLOptChapterI.pdf

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for your comments. The successive projection algorithm for Bregman divergence is proposed in "L. Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Comp. Mathematics and Mathematical Physics, 7:200–217, 1967." and can also be found in many papers, such as "Brian Kulis, Matyas Sustik, & Inderjit Dhillon. Low-Rank Kernel Learning with Bregman Matrix Divergences. JMLR 10:341-376, 2009". $\endgroup$
    – ppyang
    Apr 1, 2014 at 1:13
  • $\begingroup$ Thank you for your references and I will read them to find if they can be used to solve my question. $\endgroup$
    – ppyang
    Apr 1, 2014 at 1:32
  • $\begingroup$ Thank you! As you will see in the references above, when your domain is simple enough (as a simplex) there is no need for iterative methods for obtaining the proximal point (the solution to your problem above): there are closed form solutions from the first-order conditions! Good luck $\endgroup$
    – Cristóbal Guzmán
    Apr 1, 2014 at 17:36
  • $\begingroup$ It sounds fascinating that there are closed form solutions for this kind of problems. I will try it and thank you very much! $\endgroup$
    – ppyang
    Apr 2, 2014 at 0:52
0
$\begingroup$

I have no idea what the Bregman divergence is, but to me the two problem are just equivalent.

You are implicitly assuming that your polyhedron is limited. If this holds, than the two representations are equivalent and you can use the one it suites you the most. They are the two faces of the same coin.

Clearly the first formulation uses half of the variables...and by the way, what is $y$?

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your comments. You can regard $y$ as a parameter of the objective function which is given preliminarily. $\endgroup$
    – ppyang
    Mar 23, 2014 at 23:57
  • $\begingroup$ The two representations are indeed equivalent, but I don't know if there is a way to reformulate a polyhedron with its convex hull representation to its half-space representation. I ask this question because there is an algorithm to solve only the problem with a half-space representation while I want to solve the problem with a convex hull representation. $\endgroup$
    – ppyang
    Mar 24, 2014 at 0:04

Your Answer

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

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