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
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$). ...
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 \...
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: ...
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 ...
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 ...
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, ...
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 ...
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 ...
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: ...
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 ...
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(...
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 ...
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 ...
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{...
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}{...
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}$. ...
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}_{...
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, \...
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_{...
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 ...
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 $\...
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 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 ...
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 ...
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