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.

Filter by
Sorted by
Tagged with
12
votes
2answers
437 views

Convex Maximization with Linear Constraints

I am doing active research in convex maximization w.r.t. linear constraints. There are many cases which can be efficiently approximately solved, e.g., convex quadratic maximization, log-sum-exp ...
8
votes
4answers
339 views

Disciplined convex programming representation of $x\sqrt{1-x}$

Anyone have an idea for a disciplined convex programming (DCP) representation of the concave function $x\sqrt{1-x}$, which is defined over the domain $[0,1]$? The Taylor series about $x=0$ is $$x - \...
8
votes
1answer
243 views

Convexity/Concavity of Average Number of Jobs in M/M/1 Queue?

I am working on a problem involving the average number of jobs $L$ in an M/M/1 queue with arrival rate $\lambda$, service rate $\mu$. For traffic intensity $\rho = \frac{\lambda}{\mu}$, $$ L = \frac{\...
8
votes
2answers
146 views

Convex Optimization: Separation of Cones

I am trying to solve Exercise 2.39 at Boyd and Vandenberghe's Convex Optimization book. In one source, the answer is given as: 2.39 Separation of cones. Let $K$ and $\tilde K$ be two convex cones ...
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 ...
7
votes
1answer
89 views

Ridge Regression lagrange duality

In every machine learning book we see that it is roughly mentioned that the ridge regression: $$p_1^* = \min\limits_{\beta} \ \left( \mathrm{RSS} + \lambda\sum_{j=1}^p \beta_j^2 \right)$$ is ...
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 ...
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 ...
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 ...
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 ...
6
votes
0answers
51 views

Semi-definite Programming, non standard notation

The usual way to define a semi-definite program (SDP), e.g., as given in Boyd and Vandenberghe's convex optimization book, is: $$ \begin{array}{cl} \min & c^\top x \\ \mathrm{s.t.} & 0 \succeq ...
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}{...
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 ...
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 ...
5
votes
0answers
451 views

Convexity of the projection of a convex set

Question: A set $S \subset \mathbb{R}^m \times \mathbb{R}^n$ is convex. Using the fact that affine maps preserves convexity prove that $S(y) = \{x \in \mathbb{R}^m\mid (x,y)\in S \}$ and $\hat{S} = ...
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$$ $...
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?
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 ...
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 ...
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 ...
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 \...
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 ...
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 ...
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'...
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 ...
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 $...
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 ...
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}...
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 $...
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 ...
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{...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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(\...
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 ...
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 ...
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?
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:}...
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{...
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\\\...
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 ...
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 $$ \...
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 ...