1
$\begingroup$

Is it possible to determine if a Geometric Program (GP) has one, none, or infinite (primal) solutions by its structure (e.g., in terms of the number of variables, constraints, or product terms involved in the problem)?

It is known that the "degree of difficulty" (see e.g. this def.) determines the number of solutions to the dual problem, but how that relates to the number of primal solutions?

I am interested in proving that a GP has a unique solution, i.e. when the set of optimal solutions is a singleton.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

I general, you can't determine infeasibility or unboundedness by the structure.

But, if after change of variables to convex form, the objective is strictly convex, the solution, if it exists, is unique. However, lack of strict convexity does not imply the solution is not unique.

So solve the GP using a numerical optimizer (preferably designed to specially handle Geometric Programs). Assuming no numerical difficulties, it will be determined to be either

a) Infeasible

b) Unbounded

or

c) An optimal solution will be found. If (after the change of variables to convex form) the objective function is strictly convex, the optimal solution is unique. If the objective is not strictly convex, we are left not knowing whether the solution is unique.

Edit: I agree with everything @ErlingMOSEK wrote and added two italicized sentences to make his point explicit.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks. The problem is that determining the strict convexity of all those log sum exp involved is not the easiest thing to prove. $\endgroup$
    – Apprentice
    Oct 20, 2022 at 12:22
  • $\begingroup$ Maybe, instead of using the hessian, it is possible to do that by some properties of log-log convex functions? $\endgroup$
    – Apprentice
    Oct 20, 2022 at 12:23
  • $\begingroup$ On your addition, is there any "iff" condition for unicity of the solution? $\endgroup$
    – Apprentice
    Oct 20, 2022 at 14:14
3
$\begingroup$

This is a follow-up to the post of Mark Stone.

The problem can be formulated in a conic form using

https://docs.mosek.com/modeling-cookbook/expo.html#geometric-programming

and solves quite well on that form. Clearly, on that form the objective is linear, but the problem might still have a unique solution. So the method of Mark is only sufficient.

A reasonable conjecture is that the Hessian of Langrangian should be strictly convex at the optimum. This generalizes the proposal of Mark.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thanks. I have made the lack of sufficiency point explicit. $\endgroup$
    – Mark L. Stone
    Oct 20, 2022 at 12:49
  • 1
    $\begingroup$ Hessian of Lagrangian projected into nullspace of Jacobian of active constraints. I.e., let Let H = Hessian of Lagrangian and Z = nullspace of Jacobian of active constraints. Then $Z^THZ \succ 0$ $\endgroup$
    – Mark L. Stone
    Oct 20, 2022 at 13:45

Your Answer

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

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