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.
126
questions
2
votes
1
answer
109
views
+200
How to solve this generalized set packing problem?
I have a machine mapping problem as depicted in the figure below
There are several machines and several tasks. Tasks are of different types and need different number of machines, such as 2,4 8, etc ...
- 2,029
4
votes
0
answers
70
views
Analytical solution of constrained quadratic program
I'm trying to solve a "simple" (= small) optimization problem often, with only minor changes to the objective function. Therefore it's important to keep the "time per solve" as low ...
- 41
2
votes
1
answer
75
views
Decision Variables becoming Constraints
Consider a convex optimization problem with decision variable x. Though I'm interested in answers for any kind of convex optimization problem, let's say it's an LP, so we have something like:
\begin{...
- 121
4
votes
1
answer
157
views
How to solve this linear program with an exponential number of constraints?
Consider the following convex program:
\begin{align*}
\min g(x) && \text{such that}
\\
f_i(x) &\geq b_1 && \text{ for } i \in 1,\ldots,n;
\\
f_i(x)+f_j(x) &\geq b_1+b_2 &&...
5
votes
1
answer
286
views
Minimize sum of ReLU
I am trying to minimize a function of the following form
$$f(\vec{x}) = \sum_{i = 1}^n\operatorname{ReLU}(\vec{v}_i \cdot \vec{x} + b_i) $$
$x \in \mathbb{R}^m$ with $m$ around $100$ to $1000$ and $n$ ...
- 91
3
votes
1
answer
111
views
Convex optimization with linear constraints. Can I solve it analytically?
I have a constrained convex optimization problem with linear equality and inequality constraints.
\begin{align}
\label{eq:costf}
\text{minimize}\ \
&f(x_1,\dots,x_m) = \sum_{i=1}^m \frac{1}{...
- 39
4
votes
1
answer
261
views
large scale optimization with Python
I am dealing with the following optimization problem:
$$
\underset{x}{\min} q(x)
$$
subject to
$$
l_{x} \leq x \leq u_{x} \,\,\,\, \text{ and } \,\,\,\, l_{a} \leq Ax \leq u_{a}.
$$
where $q(x)$ is a ...
- 43
3
votes
1
answer
255
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}$.
...
- 3,893
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}_{...
- 31
8
votes
1
answer
218
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,
\...
- 81
5
votes
3
answers
137
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_{...
- 151
5
votes
2
answers
114
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}\...
- 454
3
votes
0
answers
94
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 ...
- 39
3
votes
0
answers
37
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 ...
- 469
2
votes
1
answer
89
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 ...
- 131
5
votes
1
answer
144
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 ...
- 605
8
votes
1
answer
245
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 $\...
- 233
4
votes
1
answer
297
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.
- 43
2
votes
2
answers
127
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].$$...
- 3,786
3
votes
1
answer
172
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 ...
- 39
7
votes
5
answers
906
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, ...
- 131
0
votes
0
answers
176
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 ...
- 91
4
votes
2
answers
172
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 ...
- 613
6
votes
3
answers
481
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, ...
- 169
3
votes
0
answers
41
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 ...
- 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
$$
...
- 543
3
votes
1
answer
233
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....
- 543
3
votes
0
answers
39
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:
\...
- 131
4
votes
1
answer
235
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+...
- 151
1
vote
1
answer
61
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 ...
- 11
4
votes
0
answers
106
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} \...
- 233
4
votes
1
answer
126
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 ...
- 41
4
votes
3
answers
124
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 ...
- 1,036
5
votes
1
answer
204
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 ...
- 151
5
votes
1
answer
64
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 ...
- 193
4
votes
1
answer
148
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$, ...
- 2,083
2
votes
1
answer
74
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 ...
- 23
3
votes
0
answers
99
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, \\& ...
- 233
4
votes
1
answer
119
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 ...
- 2,083
10
votes
4
answers
4k
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 ...
- 1,036
1
vote
1
answer
130
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{...
- 2,083
1
vote
1
answer
100
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}...
- 241
0
votes
1
answer
148
views
How to simplify the following constraints as I'm using MIP optimization solver in python?
Following is the initial snippet of the code:
...
- 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_{...
- 207
3
votes
1
answer
596
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 ...
- 207
5
votes
1
answer
325
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 ...
- 207
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
...
- 523
3
votes
2
answers
254
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}}{{\...
- 177
5
votes
2
answers
127
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 (-...
- 175
5
votes
1
answer
359
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 ...
- 2,029