Questions tagged [convex-optimization]

A convex optimization problem consists of either minimizing a convex objective or maximizing a concave objective over a convex feasible region.

Filter by
Sorted by
Tagged with
0
votes
0answers
8 views

Is any relaxation for Max-Cut problem will give same lower bound?

so i need to proposed a relaxation problem for that Max-Cut problem: Then, the next part is to solve the duality problem (Lagrangian). And now comes the tricky question that i'm not sure about it. ...
0
votes
0answers
4 views

Any optimizing constraints available to limit the positon of non-zero elements?

For the model $\mathbf{M} = \mathbf{K_2SK_1^T}$ (data was attached here!),$\mathbf{K_2}\in R^{18000\times 64}$,$\mathbf{K_1}\in R^{21 \times 64}$ and $\mathbf{M} \in R^{18000\times 21}$ were given. ...
0
votes
0answers
13 views

how to solve this convex-linear optimization problem with linear constraints

Consider the following optimization problem with $A > 0, B > 0$ and each $f_i(x_i)$ being convex functions. Is there any good algorithm for solving this problem? min $\sum_i f_i(x_i)y_i$ s.t. $\...
2
votes
0answers
70 views

How to solve the following convex optimization problem to get a closed form solution?

Please, can you help to solve the following convex optimization problem to get a closed-form solution? I tried to solve it using Lagrange multiplier but it's not easy. I can't get the closed-form ...
0
votes
0answers
37 views

Showing that a function is concave

Fix a fixed $0<\lambda<0.5$, consider the function \begin{align} f(p) &= \frac{1}{\sqrt{\frac{1 -\lambda + \lambda (1+p)^2}{(1 + \lambda( 1+2p))^2} + \frac{1 -\lambda + 4\lambda (1+p)^2}{(...
0
votes
0answers
23 views

Linear program with none empty feasible set and bounded objective

It is clear to see that if the feasible region of a linear programming problem is nonempty and bounded, then the objective function attains both a maximum and minimum value and these occur at extreme ...
0
votes
1answer
14 views

Optimality condition for convex problem

Let $P_X$ denote a distribution from $\mathcal{P}(\mathcal{X})$. For each $x \in \mathcal{X}$ let $$f_x:[0,1] \rightarrow \mathbb{R}$$ denote a given decreasing convex function. The goal is to compute:...
2
votes
1answer
33 views

Jensen's inequality tells us variation of $x$ will increase the average value of $f(x)$?

This is from Boyd's convex optimization 6.4.1 stochastic robust approximation (p. 319): "When the matrix $A$ is subject to variation, the vector $Ax$ will have more variation the larger $x$ is, ...
3
votes
3answers
57 views

Derivative of argmin in a constrained problem

Let $f(x,y)$ be a continuously differentiable function from $\mathbb{R}^2$ to $\mathbb{R}$. Suppose that for every $y$ the function $g_y(x)=f(x,y)$ is strictly convex. Define $$ h(y) = \arg\min_{x\...
1
vote
2answers
36 views

Theorem for the Optimization of Linear Function over a Bounded Polyhedron

In optimization theory, I often see people say that the minimum a linear function over a compact convex set is attainable at some extreme point of the feasible set. I have no problem with its proof, ...
0
votes
0answers
26 views

Smoothness (i.e. Lipschitz continuous gradient) of supremum

Define $$ \mathcal{P} = \{p \in \mathbb{R}^n \ | \ \sum_{i=1}^n p_{(i)}=1, \ p_{(i)} \geq 0, \ \sum_{i=1}^n \phi(p_{(i)}) \leq \rho \}, $$ where $p_{(i)}$ is the $i$'th element of the vector $p$, $\...
0
votes
0answers
36 views

Confusion in understanding a simple convex optimization problem's solution

I am learning optimization through a course on Youtube. I have one confusion in solving the following problem. As per my understanding, the objective function is not convex. The problem is a ...
-1
votes
0answers
11 views

Describe the set of all feasible directions at a point. [closed]

Let f(x,y)=-3y+1 and D be the set of all points satisfying y<=x²-3 a)Describe all set of feasible directions at (0,-3). b)Does (0,-3) satisfy the necessary first order conditions? c)Does (0,-3) ...
1
vote
1answer
48 views

How do I transform this problem into a semidefinite program?

$$\begin{array}{ll} \text{minimize} & \dfrac{(c^T x)^2}{(d^Tx)}\\ \text{subject to} & Ax \leq b\\ & d^T x > 0\end{array}$$ I have been stuck on this question for a couple days. I am ...
-2
votes
0answers
32 views

How to check if the following problem is convex or not? [closed]

$\min x_1 + x_2$ subject to $a x_1 + b x_2 + c \sqrt {x_1 x_2} \geq 0$ and $0 < x_1,x_2 \leq d$, where $a,b,c$ and $d$ are integers.
0
votes
2answers
46 views

How to write these function with disciplined convex programming rule to use CVX? x*(2^(y/x)-1)

I have the following functions in an optimization problem. $x\times 2^{(y/x)-1}$ $ x \log (a+b\times 2^{(y/cx)-1} )$ Here, x,y>0, and also a,b,c>0, and b>a. For these conditions, I checked ...
0
votes
2answers
42 views

How to find a matrix whose range is the null space of another matrix?

One solution for eliminating the equality constraint from optimisation problems is employing a typical matrix $F$ which its range space is the null space of the matrix used in equality constraint as ...
0
votes
0answers
18 views

Convexity and NP-hardness

Suppose that we have the following optimization problem: $$Maximize_{x_{j,i}} ~ {{\sum_t \sum_i \sum_j (a_{0,i;t}+\sum_i \sum_j a_{j,i;t} x_{j,i;t})}\over{\sum_t\sum_i\sum_j x_{j,j;t} b_{j,i;t}}}$$ $$...
0
votes
0answers
32 views

Can you always apply the log transform over a positive inequality constraint?

I'm having trouble understanding when can you take the log of a constraint in a general way (is this something you can always do for positive inequalities $\geq 1$, or there are limitations?)...it's ...
2
votes
1answer
30 views

$ f(x)+ \sum \lambda_ig_i(x) \geq f(\bar x), \forall x \in \mathbb{R}^n.$

Suppose that $f,g_i : \mathbb{R}^n \to \mathbb{R}$ $(i=1,\ldots,m)$ are convex functions and $\exists x$ such that $$g_i(x)<0 , \qquad i=1,\ldots,m.$$ Show $\bar x$ is optimized solution of $$\min ...
3
votes
0answers
61 views

show $\nabla f(\bar x) \geq 0$ and $\nabla f(\bar x)\bar x = 0$.

let $f : \mathbb{R}^n \to \mathbb{R} $ be a convex and differentiable function and $\bar x$ is solution of this problem $$\min f(x) $$ $$s.t \qquad x \geq 0 .$$ Then show $\nabla f(\bar x) \geq 0$ and ...
0
votes
1answer
28 views

Minimization with Trace of Hadamard Product

I have the following minimization problem, where I want to find $ X $ $$ \min_{X \succeq 0} \mathrm{tr}(A X) ~~~ \mathrm{s.t.} ~ X \circ I = I $$ Assume that $ A $ is Hermitian positive definite, $ I $...
0
votes
2answers
47 views

Multiplying $A\preceq B$ with a matrix

I have a matrix inequality, $$A\preceq B,$$ where $\preceq$ means that $B-A$ is psd. update: How can I show that if $M$ is a positive definite matrix, then the inequality above is equivalent $$M A M^\...
1
vote
1answer
51 views

Is the $\arg\min$ of a strictly convex function continuous?

Let $X\subset \mathbb{R}^n$ and $Y\subset \mathbb{R}^m$ be compact and convex sets, and let $f:X\times Y\rightarrow \mathbb{R}$ be a continuous function. Suppose that for each $y$, $f(x,y)$ is ...
0
votes
0answers
76 views

Prove that function is convex, first order smoothness,second order smoothness

I have the following function: $$\mathbb{R}^n \ni (x_1, \cdots , x_n) \mapsto \ln( \sum_{k=1}^{n}{exp(x_k)})$$ I know how to prove if a function is convex, but I have trouble with this specific one. ...
0
votes
0answers
20 views

first order condition for quasiconvex functions

I need to prove the following statement. Let $ f:\mathbb{R}^{n}\to \mathbb{R}$ be a differentiable function. If $\forall x,y\in$ dom$(f)$, $f(y)\le f(x)\Rightarrow \nabla f(x)^{T}(y-x)\le 0$, then $f$...
-1
votes
0answers
11 views

quasiconvex functions and their minimum [closed]

Let $f$ be a differentiable quasiconvex function. Show that the condition $\nabla f(x)=0$ implies that $x$ is a local minimum of $f$.
0
votes
0answers
14 views

Find an optimal function with distributed delay

Let $H: \mathbb{R}^2\rightarrow{}\mathbb{R}$ be a function (I can consider that this function has derivatives of some order to solve the problem), and for $q \geq 0$, $w_q$ is a probability desity ...
1
vote
1answer
49 views

Equality for Convex Functions

A function $f$ is convex on $\mathbb{R}$ if for all $x\in \mathbb{R}$ $\lambda \in [0,1]$ $$ f(\lambda x+(1-\lambda) y)\leq \lambda f(x)+(1-\lambda)f(y), $$ Similarly we can define a convex ...
2
votes
2answers
53 views

Minimize $\sum_i w_i^2 x_i^2$ subject to $Ax = b$

I have the following problem in an example test for a course in optimization: $$\begin{array}{ll} \text{minimize} & \sum_{i=1}^n w_i^2 x_i^2\\ \text{subject to} & Ax = b\end{array}$$ where $A \...
0
votes
0answers
43 views

Solving a simple convex optimization problem in low complexity

Given a symmetric positive semidefinite matrix $A \in \mathbb{R}^{n \times n}$, I would like to solve the following maximization problem: $$\begin{array}{ll} \underset{t \in \mathbb{R}, \,\, x \in \...
1
vote
1answer
28 views

Steepest-descent optimization procedure with step size given by harmonic sequence

Here is a minimization procedure I've "dreamed up." I'm hoping to gain a better understanding of its mathematical properties and practical efficiency. Given a (locally) convex function $f(x):...
0
votes
1answer
28 views

Minimizing a non-convex function through its component-wise convex functions

Let $f(x,y)$ be a continuously differentiable function from $\mathbb{R}^2$ to $\mathbb{R}$. I do not know whether $f$ is convex. But I do know that for any fixed $x$, $g_x(y)=f(x,y)$ is strictly ...
0
votes
0answers
16 views

Comparing feasible region of LP

Let's say I have two different systems of convex constraints, A and B. With A an n by 5 matrix and b an m by 5 matrix. I would like to know how much the feasible regions differ. Are there any methods ...
1
vote
0answers
19 views

Fenchel conjugate of $||.||_1$ and dual of logistic regression

I am trying to replicate some results from Koh, K., Kim, S. J., & Boyd, S. (2007). An interior-point method for large-scale l1-regularized logistic regression. Journal of Machine learning research,...
0
votes
1answer
26 views

Optimization on multiplication of function of three variables

I need some suggestions on how to go above solving this problem: Suppose I have $n$ vectors: $X_1, X_2, ..., X_n$, and a known vector $Y$. Each vector has $T$ rows. I want to select only $3$ out of $n$...
0
votes
0answers
17 views

Duality in deterministic stochastic control and convex conjugate

I am currently reading the book "Stochastic Multi-stage Optimization" and trying to solve the Stochastic Optimal Control problem given in this book in the framework of duality. The problem ...
0
votes
0answers
24 views

Constraint linearization

I have the following nonlinear constraint: $$\sum_{i}\frac{x_{i}}{a_i}>b\left(\sum_{i}x_i\right)^{2},$$ where the $x_i\in[0,1]$-s are decision variables, $b$ and $a_i$, are all positive real ...
0
votes
0answers
18 views

Solution to a Quadratic Program

I am trying to solve the following QP : $$ \min_{x} \quad (1/2)\|y - Ax \|^2 _2 + \lambda \|Dx\|_1$$ where $y \in \mathbb{R}^n$, $A \in \mathbb{R}^{n\times m}$, $D \in \mathbb{R}^{l\times m}$. Assume :...
0
votes
1answer
46 views

Sensitivity of least squares solution to a data point change

Consider computing the least squares solution in $x$: $$ \text{min}.~\|Ax - b\|^2, $$ when $A$ is an $m \times n$ matrix, and $b$ is a column vector. Let's suppose we now switch exactly one row of $A$...
0
votes
0answers
14 views

Optimize the sum of utilities for the top-k nearest neighbors

We are given $n$ different $d$-dimensional vectors $ \mathbf{y}_i \in \mathbb{R}^d, i=1\dots n$, and each vector comes with an associated utility score $u_i \in \mathbb{R}$. Moreover, we can define a ...
0
votes
0answers
15 views

component Lipschitz constant

We had the following definition in class: Definition Suppose $f: \mathbb{R}^{n} \to \mathbb{R}$ continuously differentiable and $\nabla f(x)$ Lipschitz-continuously with constant $L > 0$, i.e. \...
1
vote
1answer
42 views

Looking for a function that preserves concavity

Consider the function $$ f(x,y) = g(x) y $$ where $g$ is some other function. We can restrict ourselves to $y\geq 0$ and $0\leq x\leq 1$. I would like to find a function $g$ with the following ...
1
vote
0answers
29 views

Prove convexity (product of two functions)

Is there a way to prove convexity of $$ f\left(\frac{x^{\mathsf T}\sigma}{\sqrt{x^{\mathsf T}\Sigma x }}\right)\sqrt{x^{\mathsf T}\Sigma x}$$ where $\sigma$ is a vector, $\Sigma$ is positive definite, ...
1
vote
0answers
16 views

Guarantees for one concave function greater than the other concave function

Suppose we have two functions $f(x) = a \sqrt{x}+b\cdot x$ and $g(x)$ which can be any concave function, and $x\geq 0$ for both functions $f(x)$ and $g(x)$. Is it possible for us to compute a solution ...
0
votes
2answers
27 views

The uniqueness of global minimum for quadratic programs

I have a question about the uniqueness of the solution for the following quadratic program: $$\begin{array}{ll} \underset{x \in \mathbb{R}^{n}}{\text{minimize}} & Q(x) := X^T B X - X^T b\\ \text{...
0
votes
0answers
55 views

minimizing a concave function

After decoupling a big optimization, the inner one is as follow: $min_X \quad log_2 \left(det(A+BX\right))$ $s.t. norm(X)\leq \gamma,$ where $A\in \mathbb{C}^{n\times n}$ and $B\in \mathbb{C}^{n\times ...
0
votes
0answers
14 views

Computing the dual of online learning of linear classifier

Given a convex loss function $l(\cdot)$, $T$ training examples with their corresponding labels $\{\textbf{x}_i, y_i\}_{i \in [T]}$, regularization parameter $\lambda$, the primal form for the problem ...
0
votes
1answer
29 views

What is the relationship between linear convergence in gradient descent and linear convergence in real analysis?

In undergraduate analysis/calculus courses, we often learn about linear convergence of a sequence: a sequence $x_n\rightarrow x_\infty$ in $\mathbb{R}^n$ linearly if there exists $r\in (0,1)$ such ...
0
votes
1answer
25 views

Convex functions and minimizations [closed]

triyin to solve this exercise, any advices and hints on how to prove it are more than helpful. The problem Let $C \subset \mathbb{R}^n$ be a convex set, and $f: C \rightarrow \mathbb{R}$ is also ...

1
2 3 4 5
109