6
$\begingroup$

I have to maximize the function $f= \sum_{i=1}^na_ix_i $ subject to the constraints $g = \sum_{i=1}^n x_i = 0 $, $-1\leq x_i \leq 1$ and $a_i>0$. Lagrange multiplier method doesn't work because $\nabla f=\lambda\nabla g$ only yields $\lambda=a_i$ which is incorrect. Any help is appreciated. Also, I am an engineer not a mathematician.

$\endgroup$
3
  • 1
    $\begingroup$ Do you want to solve it analytically with respect to $a \in \mathbb{R}^n$ or do you want to solve it numerically (for some given $a$) on your computer? It's just an LP, so any LP solver should be sufficient. $\endgroup$
    – joni
    Commented Nov 25, 2022 at 13:46
  • $\begingroup$ @joni I am looking for an analytical solution. $\endgroup$
    – Deep
    Commented Nov 26, 2022 at 10:08
  • $\begingroup$ @Deep I hope my answer could help you. $\endgroup$ Commented Nov 12, 2023 at 17:43

4 Answers 4

11
$\begingroup$

You also need to account for Lagrange multipliers for the bound constraints $-1\le x_i \le 1$.

Given all $a_i>0$, the (linear programming) problem is to maximize $\sum_i a_i x_i$ subject to \begin{align} \sum_i x_i &= 0 \\ -x_i &\le 1 &&\text{for all $i$}\\ x_i &\le 1 &&\text{for all $i$} \end{align} The dual linear programming problem is to minimize $\sum_i (\alpha_i + \beta_i)$ subject to \begin{align} \lambda - \alpha_i + \beta_i &= a_i &&\text{for all $i$} \\ \alpha_i &\ge 0 &&\text{for all $i$} \\ \beta_i &\ge 0 &&\text{for all $i$} \end{align} You can interpret this as finding $\lambda$ to minimize the sum of (absolute value) distances from the various $a_i$, and the median is known to achieve that. Then $\alpha_i =\max(\lambda-a_i,0)$ and $\beta_i = \max(a_i-\lambda, 0)$. Now complementary slackness implies that $x_i=-1$ if $\alpha_i>0$ (below the median) and $x_i=1$ if $\beta_i>0$ (above the median). Otherwise, $\lambda=a_i$, and you can take $x_i=0$.

By the way, this result does not depend on the assumption that all $a_i>0$.

$\endgroup$
3
  • $\begingroup$ +1 Can you please define what $\alpha_i$ and $\beta_i$ are? How did the problem get transformed into minimization of $\sum (\alpha_i+\beta_i)$? I can't understand the new constraint equations either. $\endgroup$
    – Deep
    Commented Nov 26, 2022 at 10:19
  • $\begingroup$ Also, any not too difficult references you could point me to? Thanks. $\endgroup$
    – Deep
    Commented Nov 26, 2022 at 10:21
  • $\begingroup$ The $\alpha_i$ and $\beta_i$ are dual variables (Lagrange multipliers) corresponding to $-x_i \le 1$ and $x_i \le 1$, respectively. They play a similar role as $\lambda$ does for the equality constraint $\sum_i x_i = 0$. See en.m.wikipedia.org/wiki/Dual_linear_program $\endgroup$
    – RobPratt
    Commented Nov 26, 2022 at 14:18
2
$\begingroup$

The problem $$ \begin{array}{rcl} \min & \sum_{j=1}^n c_j x_j & \\ \mbox{st} & \sum_{j=1}^n x_j & = & b, \\ & l \leq x \leq u. & & \\ \end{array} $$
can be solved with the primal simplex algorithm in $O(n\ln(n))$ complexity i.e. $c$ has to be sorted with say quicksort.

I am pretty sure somewhere in the literature of linear programming someone must have proved that before me. It should be noted that the @robpratt approach has better complexity than what I suggest.

PS. Proving the above could be a good exercise for students of the primal simplex algorithm.

PPS. Edited to take into account the comment of @robpratt.

$\endgroup$
2
  • $\begingroup$ Note that the median can be computed in $O(n)$ time. $\endgroup$
    – RobPratt
    Commented Nov 13, 2023 at 6:12
  • $\begingroup$ Thanks for pointing that out. $\endgroup$ Commented Nov 13, 2023 at 6:21
1
$\begingroup$

Primal Problem

$$\begin{align} \text{maximize} \quad & \sum_{i=1}^n c_i x_i \\\ \text{subject to} \quad & \sum_{i=1}^n x_i = 0 \\ & x_i \ge -1 \quad \forall i=1,\ldots,n \\ & x_i \le 1 \quad \forall i=1,\ldots,n \end{align}$$

The matrix formulation of the constraints is: $$ \left\{ \begin{array}{l} {\mathbf 1^t} \cdot {\mathbf x} = 0 \\ {-I} {\mathbf x} \leq {\mathbf 1} \\ { I} {\mathbf x} \leq {\mathbf 1} \\ \end{array} \right.$$ where $\mathbf 1$ is the column vector $(1, 1, \ldots, 1)$ and $I$ is the identity matrix of size $n$.

The dual formulation of the primal problem can be obtained by writing the Lagrangian function $\mathcal{L}$ of the primal problem and connecting heuristically such a function to the minimax theorem $$\min_\mathbf y \max_{\mathbf x} \mathcal{L}(\mathbf x,\mathbf y) =\mathcal{L}(\mathbf{x}^{\ast},\mathbf{y}^{\ast})=\max_{\mathbf x} \min_\mathbf y \mathcal{L}(\mathbf x,\mathbf y)$$ proven by John von Neumann.

The Lagrangian function to be considered is:

$$\mathcal{L}(\mathbf x, \mathbf y) = \langle\mathbf c, \mathbf x\rangle - \lambda\langle \mathbf{1}, \mathbf x\rangle + \langle\mathbf{a}, {\mathbf 1} -(- I\mathbf x)\rangle + \langle\mathbf{b}, {\mathbf 1}-I\mathbf x\rangle$$

where the notation $\langle\cdot,\cdot\rangle$ indicates the scalar product between two vectors and $ \lambda$, $ \mathbf{a} = (\alpha_1, \alpha_2, \ldots, \alpha_n)$, $ \mathbf{b} = (\beta_1, \beta_2, \ldots, \beta_n)$ are components of Lagrange multiplier $\mathbf y$ that is $\mathbf y = ( \lambda,\alpha_1, \alpha_2, \ldots, \alpha_n,\beta_1, \beta_2, \ldots, \beta_n)$.

Recall the identity $\langle \mathbf v, A\mathbf w\rangle = \langle A^\top\mathbf v, \mathbf w\rangle$. Taking advantage of the linearity of the dot product, and putting in the evidence variable $\mathbf x$, we get

\begin{align}\mathcal{L}(\mathbf x,\mathbf y) &= \langle\mathbf c,\mathbf x \rangle + \langle-\lambda\mathbf 1,\mathbf x \rangle + \langle\mathbf a,\mathbf 1\rangle + \langle\mathbf a,\mathbf x\rangle + \langle\mathbf b,\mathbf 1\rangle - \langle\mathbf b,\mathbf x\rangle\end{align}

Maximizing $\mathcal{L}(\mathbf x, \mathbf y)$ with respect to variables $\mathbf x$ is equivalent considering the maximum of $\langle \mathbf c -\lambda \mathbf 1 + \mathbf a - \mathbf b,\mathbf x\rangle$. This maximum is finite and equal to $0$ if and only if $ \mathbf c -\lambda \mathbf 1 + \mathbf a - \mathbf b \le 0$ for $\mathbf x\ge 0 $ and $ \mathbf c -\lambda \mathbf 1 + \mathbf a - \mathbf b \ge 0$ for $\mathbf x\le 0$. In conclusion, we get $$\mathbf c -\lambda \mathbf 1 + \mathbf a - \mathbf b = 0$$ The dual problem associated with the Lagrangian is by definition

$$ \min_\mathbf y \max_{\mathbf x} \mathcal{L}(\mathbf x,\mathbf y).$$

In order to obtain an explicit description of the dual problem we maximize $ \max\limits_{\mathbf x} \mathcal{L}(\mathbf x,\mathbf y)$ with respect to $\mathbf x $. Fixing $\mathbf y $, we get

$$\max_{\mathbf x} \mathcal{L}(\mathbf x,\mathbf y)=\langle\mathbf a, \mathbf 1\rangle + \langle\mathbf b, \mathbf 1\rangle + \max_{\mathbf x} [ \langle \mathbf c -\lambda \mathbf 1 + \mathbf a - \mathbf b,\mathbf x\rangle]$$

and therefore

$$\max_{\mathbf x \ge 0,\mathbf x \le 0} \mathcal{L}(\mathbf x,\mathbf y) = \left\{\begin{align} \begin{matrix} \langle\mathbf a, \mathbf 1\rangle + \langle\mathbf b, \mathbf 1\rangle&\mbox{ if } \mathbf c -\lambda \mathbf 1 + \mathbf a - \mathbf b \ge 0 \mbox{ and } \mathbf c -\lambda \mathbf 1 + \mathbf a - \mathbf b \le 0 \\ \infty&\mbox{otherwise} \end{matrix}\end{align} \right.$$

The dual objective function is therefore expressed as

$$\min_{\mathbf y \ge 0} \mathcal{L}(\mathbf x,\mathbf y) = \min [\langle\mathbf a, \mathbf 1\rangle + \langle\mathbf b, \mathbf 1\rangle].$$

Dual Problem

$$\begin{align} \text{minimize} \quad & \sum_{j=1}^n (a_j + b_j) \\\ \text{subject to} \quad & \lambda - \mathbf a + \mathbf b = \mathbf c\\ & \lambda \ge 0 \\ & a_j \ge 0 \quad \forall j=1,\ldots,n \\ & b_j \ge 0 \quad \forall j=1,\ldots,n \\ \end{align}$$

$\endgroup$
0
$\begingroup$

As an engineer if you intend to quickly solve it, you'd need a solver for it. Solvers like Lingo( academic but simple) with its own modeling language, GAMS: both solver and modeling, Gurobi: solver with API for python, c++, java, CPLEX: same as Gurobi, Xpress: solver package and so on. Or the NEOS site hosts solvers that can do the task for free with some limits to capacity. There's a free library- scipy that has optimization package to solve multi variate optimization problems. It has API for python. If you want to know how Lagrangian method can solve constraints optimization with soft and hard constraints, then this link is helpful.

$\endgroup$
1
  • $\begingroup$ Thanks for your answer. I am aware of the numerical solvers. I was looking for an analytical solution. $\endgroup$
    – Deep
    Commented Nov 26, 2022 at 10:20

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.