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.
150
questions
0
votes
2
answers
57
views
Reformulate this constraint optimization problem such that I do not have to divide 2 variables?
I have a constraint optimization problem as follows:
I need to assign $m$ tasks to $n$ days, with $n \geq m$.
Each day can host 0 to $m$ tasks.
Each task either belongs to type $A$ or $B$.
I want to ...
- 21
1
vote
1
answer
97
views
Solver for quadratically constrained mixed-integer linear programs
I have an optimization problem with vectors $x$, $y$, and $z$, where $x$ is an integer vector. My objective function is linear (i.e. $\|y\|_1$), but one of my constraints is quadratic ($x^Ty \leq z$). ...
- 141
2
votes
0
answers
141
views
Distributed optimization with coupled inequality constraints
Consider the optimization problem:
\begin{equation}
\begin{array}{l}
\min_{(x,y)\in \mathbb{R}^2_{+}} \quad x_{1}a_{1} + x_2a_{2}
\\ \text {subject to } \quad\;
y_{2} \ge \frac{1}{{x}_2},
\\ \quad \...
- 215
4
votes
0
answers
82
views
The study of directional derivatives for functions that are minimums of convex functions
Has there been any research on the topic of directional derivatives of functions that are minimums of convex functions?
2
votes
1
answer
65
views
Separation oracle gives optimisation
Suppose I want to minimize a linear function $f$ over a convex set $K$ and I have only access to a separation oracle, that is, given a point, the oracle returns yes if the point is in $K$ and ...
- 121
2
votes
1
answer
60
views
Does this kind of "partition" have a name?
Consider a convex polyhedron $A$. Assume we have subsets $A_1,\ldots,A_n$ of $A$ that are themselves covex polyhedra and are mutually disjoint except maybe sharing an edge, and that their union gives $...
- 123
4
votes
3
answers
469
views
Determining the optimize lambda in Multi-Objective Optimization
I have a convex optimization problem:
Maximize obj1
Minimize obj2
Some constraint
Now to solve this problem, I used lambda to make it one problem:
...
- 143
7
votes
3
answers
1k
views
Solver for convex optimization with exponent in the objective function
My question is related to a previous one: Dedicated solver for convex problems
To minimize a convex function of the form
$~f(x_i) = \left[ C + mx_i + \frac{s}{x_i+t} \right]^p $
with various ...
- 155
3
votes
1
answer
196
views
How to deal this L0 norm of a vector of L2 or L1 norms in objective?
I have an optimization variable denoted as ${\bf A\in\mathbb{C}^{100\times 5}}=[{\bf a}_1\hspace{1mm} {\bf a}_2 \hspace{1mm} {\bf a}_3 \hspace{1mm} {\bf a}_4 \hspace{1mm} {\bf a}_5];$
Here, ${\bf a}_1$...
- 2,179
2
votes
1
answer
82
views
Formulate revenue maximization problem and find an appropriate solver
I am trying to maximize expected revenue over a horizon.
Consider the following function:
\begin{align}
sales(budget_1, budget_2) = \sum_te^{C_1t} * budget_1t^{saturation_1t} + e^{C_2t} * budget_2t^{...
3
votes
2
answers
297
views
Does solver take advantage of the problem structure?
Does Guroib take advantage of the problem structure?
I am working on a large optimization problem with more than 40,000 binary variables and huge number of constraints. below is only one of the ...
- 391
6
votes
1
answer
223
views
Is it possible to express these constraints with basic cones?
I have the following optimization problem:
\begin{align}\min&\quad x\\
\text{s.t.}&\quad x=\max_{i} \{x_{i}\}\\
&\quad x_{i}y_{i}=z_{i}\\
&\quad x_{i}, y_{i}, z_{i}\geqslant0
\end{...
- 61
1
vote
1
answer
93
views
How to model and solve such a 0-1 programming problem
My problem is described in this picture(It's like a Pyramid structure):
The objective function is below: $$\min\sum_{k=1}^\ell\sum_{i=0}^{2^k-1}\sum_{j=0}^{2^k-1}\left(A_{i,j}^k-A_{i,j+1}^k\cdot\frac{...
- 63
4
votes
0
answers
73
views
How to linearize or convexify a constraint with a square root of sum of two variables?
Here is the constraint:
$$\text{Pa} + \text{Pb}=a + b \sqrt{\text{Ir}^2 +\text{Ii}^2} + c (\text{Ir}^2 +\text{Ii}^2)$$
Here $\text{Pa}, \text{Pb}, \text{Ir},$ and $\text{Ii}$ are variables. $a, b, c$ ...
1
vote
2
answers
99
views
Does the cvxpy replace the max function by MIP formulation under the hood?
Does the cvxpy replace the max function, which is convex, by MIP formulation under the hood when shows up in the constraints (for example, $\max(x,y)\le z$) or in the objective function? In gurobipy, ...
- 391
3
votes
1
answer
61
views
Is not the substitution method supposed to reduce the computation cost?
Is the substitution method expected to reduce the computation cost? We know it will reduce the number of variables and constraints.
I mean by substitution method is to eliminate the equality ...
- 391
2
votes
3
answers
496
views
How to find the index of the item, the first time appears?
How to formulate this problem as MIP:
For example, we have the following vector of binary variables:
$$
x= [0, 0, 0, 1, 0, 1, 1]
$$
How to find out when the first "1" is recorded? For ...
- 391
5
votes
1
answer
267
views
How to formulate the inequality constraint $\sqrt{x^2+y^2} \leq z$ using gurobipy?
How to formulate the following constraint using gurobipy
$$ \sqrt{x^2 + y^2} \le z$$
where $x, y, z$ are continuous optimization variables?
I saw how to formulate it using CVXPY:
...
- 391
1
vote
2
answers
178
views
How to solve this mixed integer quadratic program using cvxpy or other method?
My problem is described in this picture:
$$
\begin{array}{l}
\left\{\begin{array}{l}
\text { objective function: } \\
f = \min \sum_\limits{l=1}^2 \sum_\limits{i=0}^{2^l-1} \sum_\limits{j=0}^{2^l-2}\...
- 63
2
votes
1
answer
146
views
Constrained Optimization Closed Form Solution Using KKT Gives Wrong Values
I have a (I guess) simple constrained optimization problem that I'm hoping to find a closed-form solution for using Lagrangian analysis and KKT conditions. I figured out the solution but there is one ...
- 235
3
votes
1
answer
87
views
On a clarification on usage of inequalities in convex programming
The inequality $x^3\leq y$ is not convex. But $0<x$ added to the above provides a convex region.
My question is whether in convex programming it is allowed to use both inequalities together and use ...
- 131
3
votes
1
answer
83
views
Projection to sublevel sets of convex/strongly convex function
Given a convex compact set $K\subset\mathbb{R}^D$ and convex function $f:K\rightarrow \mathbb{R}$, the sublevel set
$$
X_\alpha = \{ x \in K : f(x) \leq \alpha \}
$$
defines a convex closed set (...
- 235
2
votes
1
answer
91
views
Convex Optimization, Non-negativity constraints, Interior-Point or Projected Gradient?
Assume I have the following convex optimization problem, with a convex objective function on conventional non-negativity constraints.
\begin{align}
\min_{x \geq 0} \sum_{i=1}^{I} a_{i}x_{i} - f(...
- 129
1
vote
2
answers
57
views
Number of solutions to geometric program
Is it possible to determine if a Geometric Program (GP) has one, none, or infinite (primal) solutions by its structure (e.g., in terms of the number of variables, constraints, or product terms ...
- 215
3
votes
1
answer
219
views
How to solve this generalized set packing problem?
I have a machine mapping problem.
There are several machines and several tasks. Tasks are of different types and need different number of machines, such as 2,4 8, etc machines.
Due to machines ...
- 2,179
4
votes
0
answers
101
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
85
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
5
votes
1
answer
229
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
303
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
137
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
463
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
276
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,928
2
votes
0
answers
50
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
233
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
143
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
6
votes
2
answers
184
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}\...
- 474
3
votes
0
answers
174
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
42
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 ...
- 499
2
votes
1
answer
138
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
186
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 ...
- 762
8
votes
1
answer
266
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 $\...
- 215
4
votes
1
answer
329
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
142
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,796
3
votes
1
answer
263
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
1k
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
259
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
185
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
582
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
47
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
53
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