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
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
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 ...