# 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
Filter by
Sorted by
Tagged with
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
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
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
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 &&...
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
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}{...
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
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
46 views

• 151
114 views

• 151
1 vote
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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}}{{\...
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