Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

1
vote
2answers
22 views

Need a hint on how to solve this inequality

I want to show that, whenever $\frac{u_1^2}{p^2}+\frac{u_2^2}{q^2} \leq 1$ and $\frac{v_1^2}{p^2}+\frac{v_2^2}{q^2} \leq 1$, then $$ \frac{(\lambda \, u_1 + (1 - \lambda) \, v_1)^2}{p^2} + \frac{(\...
0
votes
0answers
21 views

Proof of convexity of linear least squares with convexity properties

I have seen some posts proving the linear least squares convexity using the second derivative (see this) but I was trying to demonstrate its convexity with convex properties. Below is my deduction. ...
1
vote
0answers
17 views

Properties of max norm as a constraint

If I have the following linear optimization problem (convex): $$\min Tr(D^TX) \ \ \ \ \ $$ $$s.t. \sum_{i=1}^{N}x_{ij}= 1 \ \ \ \forall j, \ \ \ \ \ \ x_{i,j} \geq 0 \ \ \ \forall i,j$$ $$$$ $Tr(.)$ ...
0
votes
1answer
20 views

converting SDP in standard form to inequality form

I want to convert semidefinite program min $tr(XY)$ subject to $X \succeq 0$, $tr(XA_i)+c_i = 0$) where matrices $A_i, Y$ and vector $c_i$ are given into the form with matrix inequalities that ...
0
votes
0answers
17 views

Proximal function for logarithm of linear transformation

I would like to calculate the proximal function $Prox_{\lambda f}(\mathbf{x}) = argmin_{x>0} (f(\mathbf{x}) + \frac{1}{2 \lambda}\Vert \mathbf{x} - \mathbf{x}_0 \lVert ^2)$ for function: $$ f(\...
0
votes
2answers
18 views

Is the set $\{a \in \mathbb{R}^k : p(0) = 1, |p(t)| \le 1$ for $0 \le t \le 1 \},$ where $p(t) = a_1 + a_2t + … + a_kt^{k-1}$ convex?

I'm having some trouble with this problem. I tried visualizing the problem first but wasn't sure if I was right. Since $|p(t)| \le 1$, I know that $1 \le p(t) \le 1$. So the function is always between ...
0
votes
1answer
37 views

How to formulate $\min \|X-z^T\mathbf{1}^T\|$ as a least squres problem?

Suppose $X\in \mathbb{R}^{m\times n}$, i.e., there are $n$ columns. Some of columns of $X$ are known, some of columns of $X$ are unknown (variables). Suppose I have $$\min_{x,z} \|X-z\mathbf{1}^T\|^...
0
votes
2answers
18 views

Let $C \subset \mathbb{R}^n$ be a given set. Show that the set $C^o = {\{y \in \mathbb{R}^n : y^Tx \le 0, \forall x \in C\}}$ is convex.

I was wondering if this proof worked for this problem. Let $t, s \in C$ and $\lambda \in [0,1].$ Let $z = \lambda t + (1 - \lambda)s$. Then $$y^Tz = y^T(\lambda t + (1 - \lambda)s$$ $$=\lambda y^Tt +...
0
votes
1answer
21 views

convex conjugate of $f(x) = (max_{i \leq n}x_i)(-\sum logx_i)$

I want to find convex conjugate of $f(x) = (\max_{i \leq n}x_i)(-\sum \log x_i)$ where $x \in \mathbb{R}^n_{++}$. This function looks like the negative entropy function but there is $(\max_{i \leq n}...
1
vote
1answer
34 views

optimal points of $x_1+4x_2+9x_3$

I want to find local and global "max", "min" of $f(x_1,x_,x_3) = x_1+4x_2+9x_3$ subject to $1/x_1+1/x_2+1/x_3=1$ I have found already that there are no global "max" and "min", because by setting $...
1
vote
0answers
30 views

A linear program with unbounded optimal solution

Consider the following $$\max 3x_1+x_2\\ s.t. -x_1+2x_2\le0\\ x_2\le4$$ a) Sketch the feasible region b)Verify that the problem has an unbounded optimal solution value Attempt: a) (Here the ...
0
votes
1answer
29 views

Hessian of negative log-likelihood of logistic regression is positive definite?

I'm trying to show that the Hessian of the negative of the log likelihood with two parameters is positive definite, but I'm not sure how to go about it once I compute the Hessian. The function is: $-...
0
votes
2answers
42 views

Prove the convexity of $f(x) = \sqrt{x^T Qx + 1}$ over $\mathbb R^n$, with $Q \succcurlyeq 0$

As the title says, the problem I'm trying to solve gives that $Q \succcurlyeq 0$, but it doesn't seem to indicate that $Q$ is necessarily symmetric. So far I've tried proving from the definition of ...
0
votes
0answers
34 views

What category does “Mathematical Optimization” and “Convex Optimization” belong to?

The above image is from the book Optimization in Practice with MATLAB® for Engineering Students and Professionals (by Achille Messac, PhD), Page-94. I don't see the terms such as Mathematical ...
0
votes
0answers
15 views

Find all packings of widgets by a set of requirements: is this a linear programming or combinatorial optimization, or bin packing problem??

Can not determine if this is a linear programming problem, or a combinatorial optimization problem, or even a packing problem? Goal is to allocate widgets from the inventory to fulfill all shipping ...
0
votes
1answer
28 views

Showing that the Lasso solution path is linear as $\lambda$ ranges

Consider Lasso problem with the Lasso parameter $\lambda$. Suppose that the set of active predictors is unchanged for $\lambda_0 \geq \lambda \geq \lambda_1$. Show that there is a vector $\gamma_0$ ...
1
vote
1answer
70 views

Gradient Descent and an ascent direction

Consider $f:\mathbb R^n \to \mathbb R$ such that $f$ is quadratic and convex. Meaning, $f(x)=x^TAx+b^Tx$ for $A\succ0$. Conjecture: Consider the Gradient Descent method with exact line search for ...
0
votes
0answers
26 views

How to write this constrain in CVX

I don't know how to describe the following constrain in CVX: $$ M = bb^H $$ here $b$ is a complex column vector, and $b^H$ is the Hermitian transpose vector of $b$. Thanks!
1
vote
0answers
22 views

optimization through matching

I have two sets of events (a, b) taking place at times $a_i$ and $b_j$, |a|=N, |b|=M, $N \geq M$. I now wish to find a subset $ \mathbf{a}^*$ of a consisting of M elements, such that $||a^*-b||$ is ...
0
votes
1answer
11 views

Breakpoints of a piecewise linear function

I'm having trouble with the following : Let $f$ be : $$f(x) = \max a_ix + b_i$$ For i in $[|1,n|]$ such as : $$a_1<a_2<...<n$$ In addition, we suppose that for each k in $[|1,n|]$, there is ...
0
votes
0answers
18 views

How to make this strange constraint convex?

Does anyone know how to make this constraint convex? $$\frac{P_{02}{\gamma_{02}}}{P_{01}\gamma_{02} + P_{U_{2}}\gamma_{22} + 1}> P_{U_{1}}\gamma_{13} + P_{U_{2}}\gamma_{23} + 2\sqrt{\gamma_{13}\...
-1
votes
0answers
17 views

How to derive the dual of a semidefinite program by Lagrange multiplier?

How do I write the dual of the following semidefinite program by Lagrange multiplier? The prime problem is: $\max Tr(\sigma)-1$ $s.t~~~\sigma\geq\rho;$ $\Delta(\sigma)=\sigma$. Where $\rho$ is a ...
0
votes
0answers
27 views

Reason why gradient descent cannot jump between connected components of level sets (when choosing appropriate step size)

Let us assume we have a function that is $l$-strongly convex and $L$-smooth on a connected component of a level set; why can gradient descent not jump from one connected component to another one when ...
1
vote
0answers
13 views

Optimization of communication system sumrate using subgradient method

I am attempting to optimize (maximise) a sumrate objective function for a communications engineering problem involving multiple users sharing a channel. I have objective function: $$ F(x_1,x_2,x_3) = ...
0
votes
1answer
30 views

Optimization of a multivariate polynomial - affine in each variable

I'm trying to maximize a polynomial which has ${n\choose 3}$ variables: For starters I'm planning to do this for $n=7$. $\displaystyle\sum_{1\leq i<j<k<l\le n}x_{ijk}x_{ikl}+x_{ijl}x_{jkl}-...
0
votes
1answer
36 views

Is $z = x^2y^3(1-x-y)$ convex or concave?

Is there some kind of trick to defining the domain of the concavity/convexity (if it exists)? I have no idea how to work with the resultant hessian
0
votes
1answer
34 views

dual relationship $\|x\|_\infty = \max_{\|z\|_1 \le 1} z^T x$

I was reading the answer in the stackexchange question about dual cones of L-1 norm cone It says the key is the dual relationship $\|x\|_\infty = \max_{\|z\|_1 \le 1} z^T x$. I am trying to ...
0
votes
0answers
24 views

optimization problem with only non convex object function as a convex optimization?

Is it possible to rewrite an optimization problem with only non convex object function as a convex optimization? I think it is impossible but am having a hard time proving it. EDIT: What I mean by ...
0
votes
1answer
36 views

What is the general approach for finding the equilibrium of a min-max problem?

I asked this question because I have trouble for taking a straight forward approach to find the equilibrium of a min-max problem. For example, consider the unconstrained optimization problem: $$ \...
0
votes
0answers
13 views

Reference Request: Weights method convex optimization

Let $f_1, f_2 : \mathbb{R}^n \rightarrow \mathbb{R}$ and $S \subset \mathbb{R}^n$ Consider a convex optimisation problem $$ \text{minimize} \quad f_1(x), f_2(x) \\ \text{subject to} \quad x \in S. $$...
1
vote
1answer
40 views

Convergence of subgradients

Let $C$ be a compact, convex subset of a Hilbert space $\mathcal{H}$ and $g:\mathcal{H}\to\mathbb{R}\cup\infty$ an extended valued, proper, lower semicontinuous, convex function. Also, assume that $C\...
1
vote
2answers
42 views

When does the variance of the sum of Bernoulli r.v.s attain a maximum?

Let $Y = X_1 + ... + X_n$, where the $X_i$ are independent Bernoulli random variables taking values in $\{0, 1\}$, with $P(X_i = 1) = p_i$. We can prove that: $$E(Y) = \sum_{i=1}^n p_i \text{ and } \...
1
vote
0answers
41 views

Prove or disprove the following is convex [closed]

Let $p>1$ be fixed Let $f$ and $g$ be functions from $\mathbb{R}^{+}$ to $\mathbb{R}^{+}$. Assume $f(x)^{p}$ and $g(x)^{p}$ are concave. Prove or disprove that $(f(x)+g(x))^{p}$ is concave. ...
1
vote
0answers
28 views

Conjugate function of negative logarithm: fault in my reasoning?

A problem, asked by Boyd and Vandenberghe (3.36f), is: Compute the conjugate function $f^*(y,u) = \sup_{x,t} \{ y^Tx + ut - f(x) \}$ of the negative generalized logarithm for second-order cone: $...
0
votes
2answers
27 views

Find $\min(x^Tx+a||x-c||_2), a>0, x \in \mathbb{R}^n$

Find $\min(x^Tx+a\|x-c\|_2), a>0, x \in \mathbb{R}^n$ My attempt: Expression is convex, so I think that it will attain minimum at the point where gradient is zero. I calculated $\nabla = 2x^T- ...
0
votes
0answers
17 views

Generalized inequality (preservation under limits)

I know this question may seem too broad or primarily opinion based but please bear with me. I have an ambiguity on my exercise context. I'm asked to prove that Generalized Inequality is preserved ...
2
votes
0answers
25 views

Minimum representation of total generalized variation

I need help understanding the proof of Theorem 3.1 from this paper. To make this post self-containded, at first I briefly review the definitions. Let $\Omega \subset\mathbb{R}^d$ be a bounded ...
0
votes
0answers
24 views

Large scale mixed integer (quadratic) programming

Here we have this optimization problem: Given positive semi-definite matrix $A \in \mathbb{R}^{n \times n }$, and matrix $B \in \mathbb{R}^{n \times m} \text{ and vectors } d \in \mathbb{R}^n,e \in ...
0
votes
2answers
39 views

Why is it an ellipsoid?

I am working on problem 2.19 (c) from Convex Optimization by Boyd and Vandenberghe. In solutions they say that $X^TQx+2q^Tx \leq r$ is an ellipsoid where $Q$ and $q$ are matrix and vector ...
5
votes
2answers
118 views

Transform an optimisation problem into a linearly-constrained quadratic program?

I would like your help with a minimisation problem. The minimisation problem would be a linearly-constrained quadratic program if a specific constraint was not included. I would like to know whether ...
0
votes
0answers
36 views

LPP vs Convex optimisation

I am studying for my statistics exam and we have Linear Programming,Simplex and graphical method, Duality Programming and Integer Programming. I have a great interest in Convex optimisation and wanted ...
0
votes
1answer
52 views

prove that hyperbolic cone is affine set (check my solution)

Hyperbolic cone $C_P$ with $P$ positive definite matrix is a set that satisfies the following $C_P = \{x: x^TPx\leq (c^Tx)^2\}$. I need to prove that this set is affine. I know that this set is convex,...
2
votes
0answers
63 views

Is a the argmin of a strictly convex function $g( \boldsymbol{x}) $ subject to linear continuously varying equality constraints continuous?

I have the following problem: $$\begin{array}{ll} & \boldsymbol{x}^*(t) = \arg \min_{ \boldsymbol{x}}\text{ }g( \boldsymbol{x}) \\ \text{subject to} & \boldsymbol{A}(t)\boldsymbol{x }= \...
0
votes
1answer
31 views

How can we show that two different optimization problems have the same minimizer?

It is evident that the two following optimization problems have the same minimizer: $$ \min_{Ax=b} \| x\|_2 $$ That is, $z=\arg\min_{Ax=b} \| x\|_2$ $$ \min_{Ax=b} \| x\|_2^2 $$ That is, $y=\arg\min_{...
0
votes
1answer
32 views

Why is this problem (multiuser transmit beamforming problem) an SOCP?

I am reading this article, in which the authors state that the problem \begin{equation*} \begin{aligned} & \min_{\mathbf w_1 \cdots \mathbf w_K} \sum_{k = 1}^K ||\mathbf w_k||_2^2\\ & \text{s....
0
votes
0answers
19 views

Example of LP Degeneracy with Unique Basis

In standard form LP, a basic solution is degenerate if there are more than $n-m$ zero variables, as defined in Bertsimas and Tsitsiklis. The authors say, in page 60, that there are examples of ...
0
votes
1answer
28 views

Strictly convex function in two variables, do the points where the function is partially optimized in one variable trace out a straight line?

Suppose $f(x,y):\mathbb{R}^2 \rightarrow \mathbb{R}$ is strictly convex in $(x,y)$. It is known that the function: $g(x)=\inf_{y}f(x,y)=\min_{y}f(x,y)$ is convex in $x$, provided $g(x) > -\infty$...
-1
votes
1answer
19 views

How to choose the initial basic variables in simplex method?

Are they always the slack/surplus variables? Another way to put the question is :whether the method always starts at the origin?
1
vote
0answers
19 views

NP-hardness proof of a model with a convex objective

Let $T=(V,E)$ denote a tree. Each node $j \in V$ in the tree has a known attribute $c_j$. From T, construct a bi-directional graph $G' = (V, E')$ where $E' = \{(j,k), (k,j)| (j,k) \in E\}$. Simply, ...
0
votes
1answer
27 views

Linear programming - optimisation

I am being asked to give an explanation what happens if, when pivoting, we chose the right entering variables and the wrong leaving variables if we chose positive pivot element, and why? and what ...