3
$\begingroup$

I have a constrained convex optimization problem with linear equality and inequality constraints.

\begin{align} \label{eq:costf} \text{minimize}\ \ &f(x_1,\dots,x_m) = \sum_{i=1}^m \frac{1}{x_i}\\ \text{so that}\ \ &\sum_{i=1}^m x_i = ab\\ &x_1 - c \leq 0,\\ &-x_m + d \leq 0,\\ &c+d-b \leq 0\ . \end{align} Note that $x_i>0,\ i=1,...,m$ and $x_1\leq...\leq x_m$. Also $a,b,c,d > 0$. Can this problem be solved analytically?

CONSIDERATIONS: The Lagrangian and its gradient can be easily computed and set to zero \begin{equation} \begin{cases} -\frac{1}{x_1^2} + \lambda_1 + \lambda_2 +\nu &=0\\ - \frac{1}{x_2^2} +\nu &=0\\ &\vdots\\ - \frac{1}{x_{m-1}^2} +\nu &=0\\ - \frac{1}{x_m^2} -\lambda_{3}-\lambda_{4} +\nu &=0 \end{cases} \end{equation} and so the Karush-Kuhn-Tucker (KKT) conditions can be derived and used to find a solution. Solving the dual problem might be also a viable solution.

The fact that $x_1$ and $x_m$ are respectively the smallest and largest variable can be expressed by including $x_1 - \frac{ab}{m} \leq 0$ and $-x_m + \frac{ab}{m} \leq 0$ among the inequality constraints.

$\endgroup$
8
  • $\begingroup$ Welcome to OR SE. Are $a,b,c,d$ all constants? If so, are they all positive/nonnegative, and do we know anything about the value of $a$ (is it related to $b,c,d$ in any way)? $\endgroup$
    – prubin
    Jul 4, 2022 at 16:14
  • $\begingroup$ Hi, thank you for welcoming me and for your interest as well. $a,b,c,d$ are all positive constants. $a$ is not related to the other constants and is $\geq1$. I'll edit $\endgroup$
    – newman_ash
    Jul 4, 2022 at 20:01
  • $\begingroup$ It is unlikely IMO but you can easily reformulate it as an SOCP. Also you are maximizing the harmonic mean which is the inverse of your objective. $\endgroup$ Jul 5, 2022 at 7:56
  • $\begingroup$ @ErlingMOSEK you mean that by reformulating as SOCP it's unlikely to find an analytic solution? Starting from an harmonic mean maximization would help in formulating the SOCP as described here. Is that why you pointed it out? $\endgroup$
    – newman_ash
    Jul 5, 2022 at 13:57
  • $\begingroup$ I'm not sure how $x_1\le \frac{ab}{m}$ implies that $x_1$ is the smallest variable etc. $\endgroup$
    – prubin
    Jul 5, 2022 at 16:01

1 Answer 1

2
$\begingroup$

You are going to be dealing with various cases depending on the values of $c,d,ab$ and $m.$ I think I can get you part way, but I have not dealt with all the cases.

Given that the objective function and the equation constraint treat all variables $x_{i}$ identically, we can ignore the requirement that $x_{1}\le x_{2}\dots\le x_{m}$ and just require that the smallest (largest) variable be at most (at least) $c$ ($d$). Since permuting a candidate solution does not affect the objective or constraint, we can simplify this further to $x_{1}\le c$ and $x_{m}\ge d$, which (assuming $x$ satisfies the equation constraint) are sufficient to ensure that the sorted version of $x$ is feasible.

Let $[m]$ denote the index set $\left\{ 1,\dots,m\right\} .$ For any $S\subseteq[m]$ and any $K>0$ let $$ g(S,K)=\min\left\{ \sum_{i\in S}\frac{1}{x_{i}}:x>0,\sum_{i\in S}x_{i}=K\right\} . $$ Using the convexity of the function $\phi(x)=\frac{1}{x}$, we can show that the minimum occurs at $x_{i}=\frac{K}{\vert S\vert}\ \forall i$ with $g(S,K)=\frac{\vert S\vert^{2}}{K}.$ Thus, in the absence of the requirements that $x_{1}\le c$ and $x_{m}\ge d$, the solution to the original problem would be $\hat{x}=\left(\frac{ab}{m},\dots,\frac{ab}{m}\right)$ with value $g([m],ab)=\frac{m^{2}}{ab}.$

Now suppose that $x_{m}$ has been fixed at some value $h$ with $d\le h<ab.$ The best possible solution with $x_{m}=h$ is found by solving for $g\left([m-1],ab-h\right).$ To avoid division by zero, we need the strict inequality $ab-h-x_{1}>0,$ which we will enforce as $x_{1}\le ab-h-\epsilon$ for some small positive $\epsilon.$ We can express the reduced problem as \begin{align*} \min_{0<x_1\le\gamma} & \frac{1}{x_1}+g\left(\left\{ 2,\dots,m-1\right\} ,ab-h-x_1\right)\\ =\min_{0<x_1\le\gamma} & \frac{1}{x_1}+\frac{(m-2)^{2}}{ab-h-x_1} \end{align*} where $\gamma=\min(c,ab-h-\epsilon).$

In the absence of the requirement that $x_{1}\le c,$ we know from convexity that the optimal solution would be $x_1=\frac{ab-h}{m-1},$ where the partial derivative w.r.t. $x_1$ changes from negative to positive. So the optimal choice of $x_{1}$ is $$ x_{1}=\begin{cases} \frac{ab-h}{m-1} & \gamma\ge\frac{ab-h}{m-1}\\ \gamma & \gamma<\frac{ab-h}{m-1} \end{cases} $$ with corresponding objective values $$ \begin{cases} \frac{(m-1)^{2}}{ab-h} & \gamma\ge\frac{ab-h}{m-1}\\ \frac{1}{\gamma}+\frac{(m-2)^{2}}{ab-h-\gamma} & \gamma<\frac{ab-h}{m-1} \end{cases}. $$ Now you just have to optimize that with respect to the value $h$ for $x_2$, taking into account the requirements that $h\ge d$ and $ab-h > 0.$

$\endgroup$

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.