Consider the following convex optimization problem in vectors $x$ and $y$

$$\begin{array}{ll} \text{minimize} & f(x,y)\\ \text{subject to} & g_1 (x)\le 0\\ & g_2 (y)\le 0\end{array}$$

where function $f$ is convex and functions $g_1$ and $g_2$ are linear. All three functions are continuous and differentiable.

Noting that the constraints are separate, if the dimensions of $x$ and $y$ are very large (e.g., more than thousand), then how can I handle this type convex optimization problem in a more efficient way?

  • $\begingroup$ Is $f$ differentiable/smooth? $\endgroup$ – David M. Feb 9 at 3:53
  • $\begingroup$ Yes, all functions are continuous and differentiable. $\endgroup$ – Dave Feb 9 at 4:07
  • $\begingroup$ Does $f$ have and additional structure beyond smoothness? You could use the projected gradient method (or an accelerated projected gradient method such as FISTA). At each iteration you will have to perform projections onto the half spaces $\{x \mid g_1(x) \leq 0\}$ and $\{y \mid g_2(y) \leq 0\}$, but that is not difficult. The two projections could be performed in parallel. $\endgroup$ – littleO Feb 9 at 4:18
  • 3
    $\begingroup$ "more than 1,000" isn't very large at all for the dimensions of $x$ and $y$. You've only got two linear inequality constraints, so the constraints are actually very simple. Chances are that a library using a second order method will get highly accurate solutions in a very short time. Have you tried using libraries such as IPOPT? $\endgroup$ – Brian Borchers Feb 9 at 4:31
  • 1
    $\begingroup$ What is the output dimension of $g_1, g_2$? Do they produce scalars, or vectors? $\endgroup$ – Alex Shtof Feb 10 at 8:12

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.