Consider the following optimization problem.

Let $d_3, d_2, d_1 > 0$.

Maximize $\log(p_1)+\log(p_2)+\log(p_3)$

Subject to:

$p_1d_1 + p_2d_2 + p_3d_3= 1$

$p_1 \geq p_2\geq p_3\geq 0$.

I believe this is a convex optimization problem, but how would one prove it?

  • 2
    $\begingroup$ Maximizing a concave function over a standard simplex, thus convex. $\endgroup$ – Rodrigo de Azevedo Apr 14 at 8:45
  • $\begingroup$ @RodrigodeAzevedo Does the form of the constraints (in this case linear in $p_i$), affect whether the problem is convex or not? $\endgroup$ – Anush Apr 14 at 17:47
  • $\begingroup$ If the feasible region is not convex, then the problem is non-convex. $\endgroup$ – Rodrigo de Azevedo Apr 14 at 17:48
  • $\begingroup$ @RodrigodeAzevedo Given that the objective function is linear in $\log(p_i)$ and the constraints are linear in $p_i$, does this change how you consider the convexity of the feasible region? $\endgroup$ – Anush Apr 14 at 17:49
  • $\begingroup$ I don't understand your question. A convex program is either minimizing a convex function or maximizing a concave function over a convex feasible region. Tucker's answers deals with the concavity of the objective function to be maximized, but does not touch the constraints. $\endgroup$ – Rodrigo de Azevedo Apr 14 at 18:00

A few hints:

  • the log function is concave

  • the sum of concave functions is concave

  • a maximization problem is equivalent to a minimization problem with the objective function multiplied by -1

  • $\begingroup$ I am guessing the constraints also need to be of a particular form for the problem to be convex? $\endgroup$ – Anush Apr 14 at 11:26
  • $\begingroup$ Yes, to be a convex problem, the set of solutions that satisfies the constraints should be convex. In this case the constraints are linear so they form a convex set. (Note - in Rodrigo's first comment yesterday, when he says "over a standard simplex," this is referring to the constraints.) If you're interested in learning more, the free Boyd and Vandenberghe book may be helpful (e.g., section 2.1.4) web.stanford.edu/~boyd/cvxbook $\endgroup$ – E. Tucker Apr 15 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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