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.
98
questions
3
votes
1answer
136 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+...
1
vote
1answer
49 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 ...
4
votes
0answers
89 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} \...
4
votes
1answer
107 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 ...
3
votes
3answers
112 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 ...
5
votes
1answer
113 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 ...
5
votes
1answer
55 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 ...
4
votes
1answer
143 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
votes
1answer
70 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 ...
3
votes
0answers
52 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, \\& ...
4
votes
1answer
63 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 ...
8
votes
4answers
819 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
vote
1answer
100 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{...
1
vote
1answer
87 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}...
0
votes
1answer
142 views
How to simplify the following constraints as I'm using MIP optimization solver in python?
Following is the initial snippet of the code:
...
2
votes
1answer
71 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_{...
3
votes
1answer
303 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 ...
5
votes
1answer
265 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 ...
3
votes
0answers
104 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
...
3
votes
2answers
219 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}}{{\...
5
votes
2answers
120 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 (-...
5
votes
1answer
269 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
votes
3answers
85 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 $\...
2
votes
1answer
102 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 ...
1
vote
0answers
49 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, ...
4
votes
2answers
171 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 ...
1
vote
1answer
177 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 ...
4
votes
1answer
76 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?
1
vote
1answer
58 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\...
6
votes
2answers
97 views
Is $\min \ x^3 \ \mathrm{s.t.}\ x \geq 0$ a convex problem?
The problem $$\min \ x^3 \ \mathrm{s.t.} \ x \geq 0$$
is sometimes said to be a convex optimization problem. $f(x) = x^3$ is not a convex function. However, in the domain of $x\geq 0$ it is convex. So ...
0
votes
1answer
272 views
How to mathematically formulate the optimization problem?
I have a system with $S$ service points.
There are also $U$ users in the system.
We have $$U>S>G$$
One group can have maximum $M$ service points, but there is no restrictions on the number of ...
0
votes
0answers
28 views
Correct way to define constraints in Pyomo
Can I know if the constraint below can be defined as follows in Pyomo for convex optimization.
W and G are arrays of dimension M x N.
...
1
vote
1answer
348 views
Can I define constraints in Pyomo as a list?
I would like to define the following constraint in Pyomo $$W^\top{\bf 1}\le\hat w=\begin{bmatrix}\hat{w}_1&\hat{w}_2&\ldots&\hat{w}_N\end{bmatrix}^\top$$ where $W$ is a $2\times4$ matrix. ...
2
votes
1answer
58 views
Hyperbolic constraint as second-order cone
I have a problem which simplifies to:
$$
\begin{align}
\max w &\\
w&\le xy \\
x,y&\le10 \\
x,y&\ge0
\end{align}
$$
Recognizing that $xy$ form a hyperbolic constraint, I can solve by ...
3
votes
2answers
596 views
How can I express this max-min in CPLEX?
Initially, I had the below objective function
$\max \sum_{u=1}^{U}\sum_{c=1}^{C}x_{u,c}d_{u,c}$
where $x_{u,c}$ are optimization variables
I modelled this in CPLEX as
...
3
votes
1answer
169 views
Oscillations with (online) mixed-integer optimization problem
I have the following mixed-integer optimization problem:
\begin{aligned}
\max_{x,y} \quad & \sum_i x_i - \|wx\|_2 \\
\text{s.t.} \quad & \sum_i x_i \leq A \\
\quad & x \leq x_{\max} y \\
...
2
votes
1answer
68 views
Model definition in pyomo to solve online optimization problem
I am trying to model the attached online optmization problem in pyomo. Eventually, I am going to use the octeract solver to find the matrix soluions of W and G.
I would like to ask advice about ...
2
votes
1answer
44 views
How to define a stationary point of the MINLP problem?
As we all know, KKT point and stationary point are well defined when the optimization variables are continuous in the problem.
Now, I want to know whether there exist some special points except for ...
1
vote
1answer
157 views
complexity order of the interior point method
I was wondering why the complexity order of the interior point method is O()^3 or O()^3.5?
Much appreciate your time and consideration.
0
votes
1answer
99 views
How to linearise this nonlinear constraint?
I have a constraint in the form
$\sum_{n=1}^{N}x_{m,n}\omega_{m,n}\ge (t_u-1)\beta_u, \forall u, u=1,2,\cdots, U$
where $x_{m,n}$ is binary variable
$t_u$ and $\beta_u$ are continuous optimization ...
1
vote
1answer
191 views
How to transform this problem with logarithmic objective function into an approximated convex optimization problem?
I have an objective function as follows
$\underset{x_{m,n}}{\max}\hspace{1mm}\hspace{1mm}\sum_{m=1}^{M}\log_2\left(\frac{\sum_{n=1}^{N}(1-x_{m,n})\omega_{m,n}+z}{\sum_{n=1}^{N}x_{m,n}\omega_{m,n}}\...
1
vote
1answer
95 views
How can I linearise this nonlinear proportional relation constraint?
My optimisation problem has a constraint in the form
\begin{equation}
\begin{array}{*{35}{l}}
\text{}\hspace{16.5mm}\text{ C4:} \hspace{2mm}\sum_{u=1}^U d_{u,1}L_{u}:\sum_{u=1}^U d_{u,2}L_{u}:\cdots:\...
-1
votes
1answer
151 views
How to prove that the second-stage value function of a Stochastic Program is convex?
I am wondering to know how it is possible to prove that the second-stage value function in a two-stage stochastic program is convex on $x$ and $\xi$? A two-stage stochastic program can be defined as
\...
0
votes
2answers
125 views
Separating hyperplanes for a convex cone
Let $W$ be a fixed matrix. Define $$\operatorname{pos}W \triangleq \{t \mid Wy =t , y≥ 0\}.$$ It is called the positive hull of $W$. It represents
the set of right-hand sides that can be obtained by a ...
2
votes
2answers
101 views
Should I process the data or add a new constraint to achieve the target?
I have an MILP as below
$\begin{equation}
\begin{array}{*{35}{l}}
\underset{d_{u,c}}{\max}\hspace{1mm}\hspace{1mm}\sum_{u=1}^{U}\sum_{c=1}^{C}d_{u,c}\omega_{u,c}\\
\text{}\text{subject to }\text{ C1:}...
2
votes
1answer
113 views
Recommended python solver for an online optimization problem
I need to implement a load scheduling algorithm that involves solving an online optimisation problem from a research paper for my Real time systems course.
This convex optimisation problem is setup ...
1
vote
0answers
70 views
Decomposition of Polyhedra
There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system
$$ \...
5
votes
2answers
192 views
Piecewise linear and global optimization
I am new to OR, and apologies if my mathematical notation is not clear. I have tried my best to keep it concise and given an explanation with numerical data.
I would like to understand:
Can this ...
3
votes
1answer
104 views
Following code doesn't work in matlab with CVX
Given the following problem \begin{align}\min&\quad x_1+2x_2+3x_3+4x_4+\sum_{i=1}^4x_i\ln(x_i)\\\text{s.t.}&\quad e^\top x=1\\&\quad x\geq0\end{align}
I was asked to solved the dual ...
1
vote
1answer
51 views
Find a dual problem with one dual decision variable to the problem of finding the orthogonal projection of a given vector
Given the set $T_{\alpha}=\{x\in\mathbb{R}^n:\sum x_i=1,0\leq x_i\leq \alpha\}$
For which $\alpha$ the set is non-empty?
Find a dual problem with one dual decision variable to the problem of finding
...