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.
57
questions
1
vote
1answer
68 views
How can I linearise this nonlinear proportional relation constraint?
I have an optimisation problem as follows...
\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{...
0
votes
1answer
103 views
How to prove that the second-stage value function 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
118 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
83 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
64 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
147 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
79 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
93 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
51 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
80 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
91 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
38 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
69 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
35 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
60 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
67 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
24 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
332 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
207 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
123 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
71 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 ...
2
votes
0answers
33 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
62 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
61 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
55 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
131 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
63 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 ...
3
votes
0answers
33 views
Linear functions in Lenstra's algorithm
I had asked this question at MathOverflow and was pointed here.
I'm working on implementing Lenstra's algorithm. At the bottom of p.5 (at "construct $n+1$ linear functions"), he says to ...
6
votes
1answer
129 views
Convexity of the variance of a mixture distribution
$X$ is a random variable that is sampled from the mixture of uniform distributions. In other words:
$$X \sim \sum_{i=1}^N w_i \cdot \mathbb{U}(x_i, x_{i+1}),$$
where $\mathbb{U}(x_i, x_{i+1})$ denotes ...
7
votes
2answers
741 views
Difference between exploration and exploitation in Simulated Annealing algorithm
In evolutionary algorithms, two main abilities maintained which are Exploration and Exploitation.
In Exploration the algorithm searching for new solutions in new regions, while Exploitation means ...
3
votes
2answers
194 views
Can we use reinforcement learning and convex optimization to solve an optimization problem?
For an optimization problem, there are multiple-type variables should be optimized. Can we use the convex optimization method to solve a subproblem of partial variables, and then, with the obtained ...
2
votes
1answer
86 views
Relationship between extreme points and optimal solutions of SDPs
Consider this to be our SDP problem:
Minimize $\langle C, X \rangle$ such that
$\langle A_i, X \rangle \ge b_i$ for all $i \in [m]$ and
$X \succcurlyeq 0$.
For SDPs, is there a relationship between ...
4
votes
1answer
87 views
Conditions required for strong duality to hold for SDPs
According to Wikipedia, strong duality holds when "the primal optimal objective and the dual optimal objective are equal."
What are the necessary conditions for strong duality to hold in ...
2
votes
0answers
65 views
Can every convex problem use Lagrangian dual method?
If not all constraints satisfy equalities, does Lagrangian dual method make sense to a convex problem?
2
votes
1answer
104 views
Is a convex or MILP (without big-M) formulation possible for this problem
Assume we are given a directed acyclic graph (DAG) $G(V, A)$, where $|V| = n, |A| = m$, and the graph contains a source node $\mathbf{s}$ (i.e. every node in $V \backslash \mathbf{s}$ is connected by ...
1
vote
0answers
80 views
Question on quadratically constrained quadratic program
If the constrained optimization problem is a quadratically constrained quadratic program of the form \begin{align}\min&\quad x^HQx-a(x+x^H)+b|z^Hx|^2\\\text{s.t.}&\quad\|x\|^2\le1\end{align} ...
3
votes
2answers
129 views
DCP representation of a convex quotient of affine functions
I am trying to represent the following inequality:
$$\frac{x}{1-x} \leq y \qquad\mathrm{with}\qquad 0<x<1$$
The function on the left is convex (its second derivative is always positive over ...
6
votes
2answers
140 views
Find a point inside non-empty difference of ellipsoids
Given two ellipsoids \begin{align}\mathcal{E}_1 &= \{ X \mid X^\top A_1 X + 2B_1^\top X + C_1 \leq 0\}\\\mathcal{E}_2 &= \{ X \mid X^\top A_2 X + 2 B_2^\top X + C_2 \leq 0\}\end{align} are ...
4
votes
1answer
60 views
How to check for convexity of the inequality constraint $−x^2+y−1\ge0$ for a minimization objective function?
I checked the Hessian which is $\begin{bmatrix}-2&0\\0&0\end{bmatrix}$ which is negative semidefinite but according to the sketch of the function it is convex. What am I missing?
3
votes
1answer
166 views
Approximation methods for a mixed integer convex optimization problem
I have a convex objective function, e.g., minimizing the negative entropy function. My constraints are also linear. The only issue is that I also have binary variables.
I am currently aware of AIMMS'...
5
votes
1answer
114 views
Which solver solves PSD constrained convex non-linear problem
I have a problem with a vector variable $w \in \mathbb{R}^n$ and a symmetric matrix variable $V \in \mathbb{R^{n \times n}}$. I am solving a problem which is roughly like:
\begin{align}
\begin{array}{...
4
votes
1answer
105 views
Minimize a convex function over a sphere
Problem description
Let $\mathcal{C} = \{X \in \mathbb{R}^n \mid g(X) \leq 0\}$ with $g(X)$ a convex function. Suppose I need to solve the feasibility problem, for a given $r>0$
$$ \exists ^?X \...
3
votes
0answers
71 views
Strong Duality and Slater Condition
I am studying the Duality Chapter of Convex Optimization by Boyd. Is it possible that strong duality holds for non-convex optimization? If yes, is there any specific condition? And, what is the ...
6
votes
2answers
151 views
Existence of Optimal Solution
Assume we are solving $\min\{f(x) \ | \ x \in S \}$.
If $f: \mathbb{R}^n \mapsto \mathbb{R}$ is a proper closed convex function, and $S$ is a non-empty closed convex set, does this imply that the ...
4
votes
1answer
151 views
Cutting-planes application procedure for a specific problem
Sort of following up with this question. I reformulated another model to make it convex and possibly solve it with some cut generation method. I would like to double-check whether I am doing it ...
