0
$\begingroup$

Dear Optimization Experts,

Background:

I have a convex optimization problem on hand that can be shown in general form as given below \begin{equation} \begin{aligned} & \underset{x \in \mathbb{R}^N}{\text{minimize}} & & f(x) \\ & \text{subject to} & & g_i(x) - \alpha_i \leq 0 \ \ \forall i = 1,\cdots,K \; , \end{aligned} \end{equation} where both functions $g_i: \mathbb{R}^N \rightarrow\mathbb{R}$ and $f: \mathbb{R}^N \rightarrow\mathbb{R}$ are convex, and $\alpha_i \in \mathbb{R}$ is given.

The Lagrangian is: \begin{align} L\left(x, \left\{\lambda_i\right\}\right) &= f(x) + \sum \limits_{i=1}^{K} \lambda_i \left(g_i(x) - \alpha_i \right) \; . \end{align}

Question:

If $K=1$ then I can obtain the closed-form solution $x$ (and analytical solution of the Lagrange multiplier $\lambda_1$) by following the KKT conditions.

Now, the question arises when $K > 1$ then I can't obtain the closed-form solution, but I can compute $x$ analytically which is dependent on all the $\lambda_i$. So, to compute the Lagrange multiplier say $\lambda_i$, I resort to iterative solution where I fix other Lagrange multipliers ($\lambda_j \ \forall j = 1,\cdots,K$ except $i$). Then repeat the above process for other Lagrange multipliers iteratively.

  • do you have any standard name for such scheme to compute Lagrange multipliers cyclically?
  • If not, can I say that this cyclic/iterative scheme is nothing but Coordinate Descent (or like)?

Thank you so much for your time in advance.

$\endgroup$
  • 1
    $\begingroup$ Depending on how you select $\lambda$, this may be coordinate descent in the dual problem. $\endgroup$ – LinAlg Nov 18 '18 at 13:53
  • $\begingroup$ thank you LinAlg! $\endgroup$ – user550103 Nov 18 '18 at 15:51

Your Answer

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

Browse other questions tagged or ask your own question.