Questions tagged [convex-optimization]

Convex optimization, a subfield of optimization, studies the problem of minimizing convex functions over convex sets. The convexity property can make optimization in some sense "easier" than the general case - for example, any local minimum must be a global minimum.

Filter by
Sorted by
Tagged with
3 votes
1 answer
232 views

Express equality constraint involving exponentials cones

The exponential cone is define such that $(x, y, z) \in \text{ExpCone: if } y \exp(x / y) \leq z \land y > 0.$ The inequality $\exp(a) \leq b$ can be expressed as $[a, 1, b] \in \text{ExpCone}$. ...
user avatar
2 votes
0 answers
46 views

Coordinate descent for constrained least squares

I have a least squares problem of the form \begin{align}\min_{\vec{a}}&\quad\|\vec{y} - X\vec{a}\|^2 \\\text{s.t.}&\quad\|\vec{a}_{I}\|^2 \leq 1,\\&\quad I \in A\end{align} where $\vec{a}_{...
user avatar
8 votes
1 answer
210 views

Maximize correlation subject to nonconvex correlation constraints

Let $r, z$ and each of $u_i$ be a length $n$ vector. I’d like to maximize the correlation between $z$ and $r$ (when that correlation is positive) while keeping $z$ “away” from $u_i$’s. Formally, \...
user avatar
5 votes
3 answers
129 views

What is the go-to practical method for optimizing separable quadratic programs?

I have a quadratic program that looks like this: For fixed vector $b$, and matrices $A_1, ..., A_n$, Find column vectors $x_1, ..., x_n$ that minimize $\sum_{i=1}^n x_i ^T 1 1^T x_i$ subject to $\sum_{...
user avatar
5 votes
2 answers
87 views

Are "polynomial-time" algorithms for convex minimization actually pseudopolynomial time and/or FPTASes?

Motivating example This question concerns continuous convex minimization. However, the motivating example is the classic binary knapsack problem $$\text{maximize}\quad v^T x \qquad \text{subject to}\...
user avatar
  • 346
3 votes
0 answers
52 views

Adequate SDP solvers for large problem instances

I have previously used MOSEK for all my SDP needs. Recently, though, I am having a hard time trying to solve some large problems, due to lack of memory. In similar questions around the forum, SCS has ...
user avatar
  • 39
3 votes
0 answers
35 views

Complexity of the ellipsoid method in general convex problems

The ellipsoid method is often mentioned in relation to the complexity of solving linear programs. Is the method however polynomial in the general non-linear convex cases? Preferably I would like a ...
user avatar
  • 389
2 votes
1 answer
62 views

How to minimize a quasi-convex function in 2 dimensions?

I know that if $f$ is a quasi-convex function in one dimension (that is, $f: \mathbb{R} \to \mathbb{R}$), then we can use the 'golden section' line search to find the optimizer. Now suppose I have a ...
user avatar
5 votes
1 answer
136 views

Constraints like "max(column a + column b) == 2" are not DCP

I am struggling with the following constraint on a minimization problem cvx.max(z[:, i] + z[:, j]) == 2 where z is a Boolean ...
user avatar
  • 533
8 votes
1 answer
229 views

Distributed optimization problem

Consider the following optimization problem: \begin{equation} \label{eq:1} \min_{x\in\mathcal X} \max_{i\in\mathcal I}\sum_{j\in\mathcal J} f_i(x_{(j)}), \end{equation} where $\mathcal{I}$ and $\...
user avatar
4 votes
1 answer
278 views

Why does some solvers can only solve conic optimization problems?

Famous solvers like sedumi, sdpt3, mosek can solve conic optimization, but not more general convex optimization. Why? I know many convex problems can be formulated as conic, but still confused.
user avatar
  • 43
2 votes
2 answers
117 views

Minimizing a KS function

For convex functions $f_i, \ i \in I$, the KS function is defined as the following for any $\rho > 0$: $$KS[\{ f_i \}_{i \in I}](x):= (1/ \rho) \ln \left[ \sum_{i \in I} \exp(\rho f_i(x)) \right].$$...
user avatar
3 votes
1 answer
121 views

Adding CVXPY abs to optimization problem turns out to be non-DCP

I have tried to solve an optimization problem using CVXPY library. This problem aims to minimize the distance between a vector of $n$ variables ($\beta$), which can be positive or negative real ...
user avatar
  • 39
7 votes
5 answers
710 views

Fast way to repeatedly solve many similar LPs/QPs in parallel

I am running a simulation where I need to repeatedly solve a set of LPs or QPs with slightly different input parameters for a Model Predictive Control application. The problem is I need it to be fast, ...
user avatar
  • 131
0 votes
0 answers
116 views

CPLEX returns no solution with deterministic time limit

I'm working with CPLEX using the python API (Docplex). If I set the time limit in seconds with model.set_time_limit(60) the solver returns the best integer feasible ...
user avatar
4 votes
2 answers
158 views

Eliminating Variables in Semidefinite Programs Using Equality Constraints

Suppose I have an SDP \begin{align}\min_{X \in \mathbb{S}^{n}_{+}}&\quad f(X)\\\text{s.t.} &\quad X_{i,j} = c_{i,j} \quad \forall (i,j) \in I,\end{align} where $I \subseteq [n] \times [n]$ and ...
user avatar
6 votes
3 answers
413 views

Are there any parallel methods for solving multiple general nonlinear convex optimization problems?

I want to find a parallel computing method for general nonlinear convex optimization problems with constraints. A parallel method that can solve a bundle of nonlinear convex problems simultaneously, ...
user avatar
  • 169
3 votes
0 answers
39 views

Constructive proof for the Hyperplane Separating Theorem (HST)?

HST is usually proven through the existence of a unique minimum-norm vector in a nonempty closed convex set. I think this is an existential proof. However, to actually apply the result in a real world ...
user avatar
  • 179
2 votes
0 answers
47 views

Regularize for a bang-bang control

I have an optimal control problem with a state vector $\vec x$ and a control vector $\vec u\in[0,1]$. If I were solving the problem without regularization I would write $$ \min \lVert \vec x \rVert $$ ...
user avatar
  • 541
3 votes
1 answer
230 views

What does nonconvex multilinear mean?

I am not a math student so I am sometimes a bit confused when it comes to math lingo. For me non-convex would mean its concave which means functions have local minima in case of a minimization problem....
user avatar
  • 533
3 votes
0 answers
37 views

Estimation of Vandermonde matrix

Cross-posted on Mathematics SE. I would like to discuss how to tackle an optimization problem to learn a Vandermonde matrix. In particular, I have an optimization problem in the following form: \...
user avatar
  • 131
4 votes
1 answer
204 views

Inverse of weighted sum of positive definite matrices

Let us suppose $I_1, \ldots, I_n$ are symmetric and positive definite matrices. Let $\mathbf{u}$ be the vector with $n$ 1s. I'm interested in the following optimization problem: $$\min \; u^T (x_1I_1+...
user avatar
  • 151
1 vote
1 answer
57 views

Convex Optimization with Variable Dependency / no unmet demand carry forward

I'm running into an issue with a Linear Optimization Problem. The ultimate goal is to come back with an optimal production quantity (prod_qty) across several items ...
user avatar
  • 11
4 votes
0 answers
104 views

Weighted nuclear norm minimization

The problem. Let $X,A \in\mathbb{R}^{n\times m}$ and let $W\in\mathbb{R}^{nm\times nm}$ be a positive definite matrix. I want to know if there is a closed-form solution to this problem $$ \min_{X} \...
user avatar
4 votes
1 answer
119 views

DCP formulation of sum of nonconvex and convex functions

I am trying to find a DCP formulation for the following convex objective function (using CVXPY): Let $x$ be the $N$-dimensional vector variable on which we optimize on, $c$ be a known scalar value ...
user avatar
  • 41
4 votes
3 answers
120 views

How to find the point on the exterior of a given set of points?

Suppose we do have a set of points (all on a plane ). How to find the smallest hull containing all these points ? How to find the points (among these given points) that are at the exterior layers of ...
user avatar
5 votes
1 answer
155 views

Practical open source LP solvers for large linear programming problem with $10^7$ parameters

I have an LP problem of the form $\min\ c^Tx$ subject to $Ax\leq b$ where $x$ consists of 30 million parameters and $A$ is a very very sparse matrix of size 30M by 30M (with only 3 ones per row). I ...
user avatar
  • 151
5 votes
1 answer
61 views

Enforce specific mean and standard deviation on data

Suppose I have some dataset $X = \{x_1, x_2, \ldots, x_n\}$ which has a mean $\bar{X}$ and a standard deviation $\sigma_X$. Now, suppose that I want to trim the tails of the dataset such that the new ...
user avatar
  • 193
4 votes
1 answer
146 views

Maximization of a nonconvex bi-variate function

Suppose we have a bi-variate function like $f(x,y)$ which is concave in $x$, $\frac{d^2f(x,y)}{dx^2} = -g(x,y)<0$ (that is $f(x,y)$ can be a function with high order in $x$ ) but convex in $y$, ...
user avatar
  • 2,105
2 votes
1 answer
73 views

Convex function subject to $0\le x_1\le \ldots \le x_n\le 1$ and linear constraint

I am maximizing a convex function (a positive definite quadratic form, if it makes a difference) subject to $0\le x_1\le \ldots \le x_n\le 1$ and a linear constraint $a^\top x+b=0$. Can I conclude ...
user avatar
  • 23
3 votes
0 answers
71 views

Convex Optimization Problem with norm inequality constraint

Consider the following optimization problem: \begin{align} \inf_{x,y}&\quad(x-x_0)^\top A(x-x_0) + (y-y_0)^\top B(y-y_0) \\\text{s.t.}&\quad x^\top a\geq0,\\ & \quad y^\top b\geq0, \\& ...
user avatar
4 votes
1 answer
91 views

Is it always possible to optimize a multivariate function sequentially?

Suppose we have a multivariate function like $f(x,y,z)$ which should be maximized with the constraints $g_i(x,y,z)\le 0 \quad \forall i$. The general rule is to use KKT conditions and derive all KKT ...
user avatar
  • 2,105
9 votes
4 answers
3k views

What is the best open source solver for large scale LP optimization in pyomo?

I have used Gurobi and cplex for solving large scale LP problems with Pyomo. However, I do need to use open source solver. Any advise? glpk and cbc seems to be very slow in solving the problem (with ...
user avatar
1 vote
1 answer
112 views

How to find the optimal solution of a convex program given all KKT points?

Suppose we have a parametric convex program with some constraints. \begin{equation} \begin{split} \max_{x} \: & f(x,\mathbf{a})\\ & g_1(x,\mathbf{a})\le 0 \\ & g_2(x,\mathbf{a}) \le 0 \end{...
user avatar
  • 2,105
1 vote
1 answer
97 views

Dual of quadratic program with linear objective

Let $c$ and $k$ be element-wise positive $n\times 1$ vectors and let $A$ be a element-wise positive and positive-definite matrix. Consider the optimization problem \begin{align} \max_{p\in\mathbb{R}^n}...
user avatar
0 votes
1 answer
144 views

How to simplify the following constraints as I'm using MIP optimization solver in python?

Following is the initial snippet of the code: ...
user avatar
  • 125
2 votes
1 answer
73 views

Subtracting Values from a Positive semidefinite Matrix in a Semidefinite Program

I'm trying to construct an SDP relaxation for a non-convex quadratic program ($x^{\intercal}\mathbf{H}x$) with the following objective function: \begin{equation} x_{11}y_{11} + x_{12}y_{12} + x_{21}y_{...
user avatar
3 votes
1 answer
443 views

Non-symmetric Positive Definite/Semidefinite Matrix in Quadratic Program

A necessary condition in any quadratic programming to be convex is the matrix $\mathbf{Q}$ in the formulation $x^\intercal \mathbf{Q}x$ to be positive definite or positive semidefinite. Positive ...
user avatar
5 votes
1 answer
295 views

Solving Quadratically Constrained Quadratic Program with Cross Product Terms Only

I'm totally new to the world of optimization and I have an optimization problem that I think it can be formulated as Mixed Integer Quadratically Constrained Quadratic Program (QCQP) but I'm not sure ...
user avatar
3 votes
0 answers
106 views

Existence of a transformation to convex optimization

Question Does a transformation of the following problem to convex optimization exist? \begin{aligned} \label{1} \min_{\vec{x}, \vec{y}} \quad & F(\vec{x}, \vec{y}) \\ \textrm{s.t.} \quad ...
user avatar
3 votes
2 answers
239 views

How to make following constraint a convex one?

I would like to write a constraint as follows, where $x,y>0$ are optimization variables, and $a,b,c,d,A$ are positive constants. How to make it a convex constraint? \begin{equation} \frac{{ax}}{{\...
user avatar
5 votes
2 answers
125 views

Black-box optimization of a single parameter function with high cost evaluation

I need to solve a series of single parameter black-box minimization problem. The underlying cost functions are quite simple. They always have the same shape: a global minimum inside a fixed interval (-...
user avatar
  • 175
5 votes
1 answer
319 views

What is a good way to penalise LP relaxation?

I have a binary integer program. It is of a large size and the solver is taking longer time. I am thinking of relaxing the binary integer variable and making it a continuous variable. How can I ...
user avatar
2 votes
3 answers
120 views

Convex optimization on the unit hypercube with gradients and a bounded minimum

I'd like to find the minimum of a smooth, continuous function inside the unit hypercube (the dimensionality of which could go into the hundreds or even thousands). The function is convex (Hessian $\...
user avatar
  • 123
2 votes
1 answer
152 views

Recovering Primal Solution from Dual solution

Consider the problem \begin{align*} &\min f(x)\\ & \ \text{s.t.} \ \ \ Ax = b \end{align*} In this expository paper, Boyd claims (top of page $8$) that if: $\lambda^*$ is a dual optimal ...
user avatar
  • 193
1 vote
0 answers
76 views

Minimum trade size in CVXPY

I'm trying to replicate some of the suggestions of this paper. On page 40-41, it's made the following suggestion when it comes to enforcing a minimum trade size: In this context, ...
user avatar
  • 119
4 votes
2 answers
245 views

Any Solution for $k$-means with minimum and maximum cluster size constraint?

I am looking for an efficient approach to $k$-means clustering with minimum cluster size constraints. The clusters are non overlapping, so, one point can belong to only one cluster. $N$ be the number ...
user avatar
1 vote
1 answer
188 views

How to convexify log(convex) function?

I have the following optimization problem: \begin{align}\max_x&\quad\log_2(1+|a+bx|^2+cx^2)\\\text{s.t.}&\quad0\le x\le1\\&\quad(1-x^2)\ge\text{constant}\end{align} where $a$ and $b$ are ...
user avatar
4 votes
1 answer
79 views

How to prove pseudo-convexity of a discrete function?

Given a general function $f:\Bbb Z\to\Bbb R$ is there a simple way to verify whether $f(x)$ is pseudo-convex or not?
user avatar
  • 43
1 vote
1 answer
86 views

Find an upper bound for an objective function

My objective function is $\log_2(1+{x^2y^2})$ and I found two upper bounds for $x^2$ and $y^2$. For example, assumed that we have the following upper bounds: $x^2\leq\text{constant}_1^2$ and $y^2\leq\...
user avatar