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.
91
questions
4
votes
1answer
136 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
64 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
47 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
54 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
440 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
95 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
81 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
137 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
68 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
275 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
256 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
102 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
217 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
118 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
245 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
80 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
95 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
45 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
154 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
170 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
72 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
51 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
94 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
266 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
25 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
116 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
48 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
451 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
166 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
58 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
99 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
85 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
127 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
92 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
145 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
123 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
100 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
101 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
69 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
184 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
88 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
...
3
votes
1answer
98 views
Find the dual problem of $\min_x\{||x-a_1||+||x-a_2||+||x-a_3||,a_i\in\mathbb{R}^n\}$
Find the dual problem of
$$\min_x\{||x-a_1||+||x-a_2||+||x-a_3||,a_i\in\mathbb{R}^n\}$$
I've tried the following but got stuck
$$\min_x\{||x-a_1||+||x-a_2||+||x-a_3||,a_i\in\mathbb{R}^n\}=\min_{x,z_i}...
2
votes
0answers
53 views
Prove $\sum_{i=1}^{m}\lambda_i^*\leq\frac{f(\hat{x})-f^*}{\underset{i=1,\ldots,m}{\min}(-g_i(\hat{x}))}$
Consider the primal problem \begin{align}f^*=\min&\quad f(x)\\\text{s.t.}&\quad g_i(x)\le0\tag P\end{align} where $f,g_i$ are convex functions. Suppose there exists $\hat{x}$ such that $g_i(\...
5
votes
1answer
94 views
Prove that $x^*$ is an optimal solution where $f_0$ is $C^1$ and convex and $f_i$ are $C^1$ and strictly convex functions
Let $x^*$ be a feasible solution of the following convex optimization problem \begin{align}\min&\quad f_0(x)\\\text{s.t.}&\quad f_i(x)\leq0,i=1,\ldots,m\end{align} where $f_0$ is $C^1$ and ...
1
vote
0answers
93 views
Prove Non-Homogeneous Farkas' Lemma
Let $A\in\mathbb{R}^{m \times n}, c\in\mathbb{R}^{n}, b\in\mathbb{R}^{m}, d\in\mathbb{R}$. Suppose that there exists $y\geq0$ such that $A^Ty=c$.
Question: prove that exactly one of the following is ...
1
vote
0answers
45 views
active set method guaranteed convergence
I'm using Active Set Method to solve a nonlinear optimization function minimizing a convex function over a polyhedron of 2 linear inequalities starting at an interior point $x_o$ At this point is it ...
2
votes
0answers
74 views
How to linearize this multiplicative constraint?
I have a constraint in the form
$\sqrt{|\sum_{c\in C}{h_cw_c}|^2}\ge\sqrt{x}\zeta$
Here, $h_c$ is s row vector (know), $w_c$ is a column vector (variable).
$x$ and $\zeta$ are also optimization ...
3
votes
2answers
95 views
Let $A\in\mathbb{R}^{m\times n},c\in\mathbb{R}^n$. Show that exactly one of the following two systems is feasible:
Let $A\in\mathbb{R}^{m\times n},c\in\mathbb{R}^n$. Show that exactly one of the following two systems is feasible:
$Ax\geq0,x\geq0,c^Tx>0$
$A^Ty\geq c,y\leq0$
Assume that A is feasible meaning $...