Questions tagged [convex-optimization]
Convex minimization, 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.
75
questions
2
votes
0answers
20 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 ...
2
votes
0answers
20 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, ...
3
votes
2answers
126 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 ...
2
votes
1answer
157 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
67 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
48 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\...
5
votes
2answers
88 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 ...
1
vote
1answer
238 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
22 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
37 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. ...
1
vote
1answer
40 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 ...
2
votes
2answers
254 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
152 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 \\
...
1
vote
0answers
21 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
43 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
89 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
79 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
87 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
88 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:\...
0
votes
1answer
140 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
122 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 ...
1
vote
2answers
98 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
88 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
66 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
$$ \...
4
votes
2answers
164 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
81 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
49 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
95 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
52 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
86 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
92 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
39 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
70 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
94 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 $...
0
votes
1answer
36 views
How to convert an element of a variable to a convex constraint using binary variables?
I defined a complex variable in cvx, but I want to restrict the first element of the variable to be larger than the max of the variable, but it doesn't work. Someone told me to transform it using a ...
-2
votes
1answer
63 views
How can I model this Hyperbolic constraint?
In this problem, $\beta_u$, $w_{u,c}$ (a vector of complex elements), $x_u$ are optimization variables.
Now,
$||2\sqrt{\frac{\pi_u}{2}}\beta_u; h_{u,c}^{\rm H}w_{u,c}-\frac{1}{2\pi_u}x_u-1||_2\le h_{u,...
2
votes
1answer
68 views
How to model these constraints correctly
$W$ is a vector of $N$ complex elements.
$D$ is a binary variable
The requirements are:
when $D==1$, $L_{\min}\le ||W||_2^2\le L_{\max}$
and when $D==0$, $||W||_2^2=0$
I have formulated the following ...
3
votes
0answers
26 views
Stationary conditions for intersection
I wondered about this question for sometime.
Definition of Stationarity
(P)
$\mbox{min} f(x)$
s.t
$x\in C$
Let $f$ be $C^1$ function over a closed and convex set $C$ . then $x^*$ is called a ...
2
votes
3answers
334 views
Find the farthest point in hypercube to an exterior point
Let $\mathcal{U} = \{ [x_1, ..., x_n] \in \mathbb{R}^n : 0 \leq x_i \leq 1\}$ be the unit hypercube and $C \in \mathbb{R}^n\setminus\mathcal{U}$ fixed. Let us consider the following problem
$$ \max_{X ...
1
vote
1answer
84 views
How to prove this convex-optimization problem?
I am struggling with the following optimization problems.
Problem 1
\begin{align}\max_{\alpha, s_1, s_2}&\quad s_1 + s_2 - \gamma (s_1 (K_1 +c_1 + s_1) + s_2 (K_2+ c_2 + s_2) + 2\alpha K) +C\\\...
4
votes
2answers
208 views
How to solve this convex problem heuristically?
I have the following problem
$$\max_{X_{i,j},i\in N_{U},j\in N_{B}}\sum_{i=1}^{N_U}\sum_{j=1}^{N_B}R_{i,j}X_{i,j}$$
$$\text{subject to}$$
$$a_{\min}\le\sum_{j=1}^{N_B}X_{i,j}\le a_{\max}, \forall i$$
$...
6
votes
0answers
124 views
Is this a valid strong polynomial algorithm for deciding LP feasibility?
Let
$$A \cdot X + B \preceq 0$$ be a system of linear inequalities with $X \in \mathbb{R}^n$ $A\in \mathbb{R}^{m\times n}$ and $B \in \mathbb{R}^m$ where $m \geq n$. According to Farkas lemma, exactly ...
5
votes
0answers
75 views
Polyhedra to Simplex by using convex combination of vertices
Optimization problems over linear constraints (defining a convex polyhedron) can be written as optimization over a simplex in a higher dimension. Let $\mathcal{P}$ be a bounded polyhedron, and the ...
4
votes
1answer
84 views
Optimization of strongly convex functions with approximate evaluations of gradient and Hessian
Suppose I want to find the minimum of a differentiable, strongly convex function $f:\mathbb{R}^n\to\mathbb{R}$ with constant $\mu>0$. That is, for all $x,y\in\mathbb{R}^n$, I have that:
$$f(y) \geq ...
3
votes
0answers
64 views
Optimizing with a logistic function
I have a system in which I want to maximize the value of some function $f(x_T, y_T)$.
The time evolution of the system is described by some functions:
$$
\begin{align}
\frac{dx}{dt}&=\alpha \frac{...
4
votes
1answer
63 views
How to evaluate the convexity of an optimal control problem?
Can we consider an optimal control problem, a convex optimization problem like static optimization problems? If it is possible, under what conditions, will this problem be a convex problem? For ...
1
vote
0answers
56 views
How to solve this problem by Lagrange duality?
This is a convex problem and although it can be well solved by CVX, I want to know how it can be solved by the Lagrange duality method. The derivations with regard to $L_k$ and $B_k$ are constants, ...
3
votes
1answer
132 views
Can we get the closed-form solution for this problem?
Can we get the closed-form solution for this problem?
\begin{align}
\min&\quad\sum_{i=1}^N\frac{K_i}{x_i\log_2(1+\frac{Q_i}{x_i})}\\
{\rm{s.t.}}&\quad\sum_{i=1}^N x_i\le X
\end{align}
wherein $...
1
vote
0answers
44 views
$\nabla_y\nabla_vf(x^*)\geq0$ for any concave $f$ if and only if $y=-v$
$f:\mathbb R^3\to\mathbb R$ is an arbitrary concave function.
$H$ is a plane. $v$ is a given vector on $H$.
$x^*=\max_{x\in H} f(x)$
Prove that $\nabla_y\nabla_vf(x^*)\geq 0$ if and only if $y=-v$.
I ...
2
votes
1answer
64 views
Quasi-convex function must be “partially monotonic”?
$f(x)$ is quasi-convex,
$$x^*\in\arg\min_{x\in C}f(x).$$
How to prove that, for any $a\in C$, $f(x) $ is weakly monotonic in the direction of $(x^*-a)$?
Is this simple result a part of an ancient ...
