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
418 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 ...
9
votes
1answer
241 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
4answers
321 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
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
720 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
88 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
139 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
125 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
1answer
73 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 ...
6
votes
2answers
146 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
121 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
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 ...
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
0answers
378 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
201 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
59 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
1answer
150 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
2answers
87 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 $...
4
votes
1answer
81 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
103 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
91 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}...
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 ...
4
votes
1answer
130 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
2answers
126 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
158 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
2answers
154 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
0answers
48 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(\...
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
29 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
329 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
66 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
103 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
48 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 ...
2
votes
1answer
58 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
81 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
85 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 ...
2
votes
0answers
36 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
66 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
59 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{...
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
1answer
80 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
0answers
53 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, ...
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 ...
1
vote
0answers
78 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} ...
0
votes
1answer
33 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
59 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,...
-3
votes
0answers
54 views

How can I make the constraint based on logarithm and absolute value linear?

I have two constraints of the form $$\log\left(1+|b_k|^2+\sum_{j=1,j\neq k}^{K}|b_j|^2\right)\ge \log(2)x_k+y_k\quad\forall k, k=1,\cdots,K$$ and $$1+\sum_{j=1,j\neq k}^{K}|b_j|^2 \le e^{y_k^{(0)}}(...