4
$\begingroup$

Given $n$ variables $x_{i}$ where $i\in [0,n)$, denoted as a vector $x$, given a linear objective function that we want to minimize $c^\top x$ with 2 constraints:

  1. $\sum x_{i}^{2} < n+1$
  2. $\sum\log(x_{i}) > 0$.

How can I solve this optimization problem?

The only thing I can think of is to convert the 2nd constraint to be the product of all $x$ bigger than $1$. I cannot think of a way to turn the 2nd constraint into a 'common' quadratic one.

Can anyone share some ideas?

$\endgroup$
4
$\begingroup$

This is a convex optimization problem which can be modeled as a combination of Second Order (SOCP) and Exponential cones.

It is easy to enter into a conic convex optimization tool, such as CVX (MATLAB), CVXPY (Python), CVXR ("R"), or YALMIP (MATLAB), which can call Mosek 9.x, ECOS, or SCS to solve it.

Here is CVX code (note: indices for x run from 1 to n, because MATLAB vector indexing starts at 1 rather than 0)

cvx_begin
variable x(n)
minimize(c'*x)
subject to
x'*x <= n+1-small_positive_number
sum(log(x)) >= 0
cvx_end

where small_positive_numberis a small positive number such as 1e-6. If you want sum(log(x)) to be strictly positive, you can use a small positive number, such as 1e-6, instead of 0, on the right-hand side of that constraint.

$\endgroup$
6
  • 1
    $\begingroup$ I wonder if OP has made a typo with $[0,n)$ as otherwise x would run from $0$ to $n-1$ (or from $1$ to $n$ in your CVX). $\endgroup$
    – TheSimpliFire
    Jan 1 at 20:30
  • 1
    $\begingroup$ @TheSimpliFir You may have a point. I interpreted that as [0,n]. I'll let the OP clarify and/or adjust the details of the solution. $\endgroup$ Jan 1 at 20:46
  • $\begingroup$ Hi, Thanks a lot for the help! I was using c/c++ notation, index starts from 0 and ends with n-1; $\endgroup$
    – user152503
    Jan 1 at 21:17
  • 2
    $\begingroup$ If the $x_i$ are continuous variables, then I think the first constraint should be $x^\prime x \le n + 1 - \epsilon$ for some small $\epsilon > 0$. $\endgroup$
    – prubin
    Jan 1 at 21:40
  • 1
    $\begingroup$ If you want a C/C++ interface then ww.mosek.com has it. $\endgroup$ Jan 27 at 6:07

Your Answer

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

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