Stack Exchange Network

Stack Exchange network consists of 175 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
0answers
14 views

General epigraph form of optimization problem whose objective function is a sum of functions

If we have an optimization problem whose objective function is a sum of functions $$\min_x \sum_i f_i(\mathbf{x}) \\ \text{subject to}\quad \left\{ \begin{aligned} h_j(\mathbf{x})&\leq 0 \\ g_k(\...
0
votes
0answers
26 views

Characterizing class of functions from their gradient descent trajectory

Let $f : \mathbb R^d \to \mathbb R$ be a function with at least one minimum. Suppose that $f$ has the property that the gradient descent trajectory from any point of the function is a straight line to ...
2
votes
1answer
53 views

Minimising quadratic objective subject to logarithmic inequality constraints

I need to minimise the following function: $$ (2a_1 + 2a_2 - 1)^2 + (2a_1 + 2a_3 - 1)^2 $$ subject to: $$ \sum a_i \log_2 a_i \geq -1 $$ where all the $i \in \{1,2,3,4\}$ and $a_i \in [0,1]$ and $\sum ...
2
votes
0answers
19 views

Directional Curvature

What is Directional Curvature and how can I achieve it for any function? A common approach with an example would be much appreciated. (Reference: I am reading "The Non-convex Geometry of Low-rank ...
1
vote
1answer
55 views

Duality Theorem for Minimum Distance Problems

The minimization of the one-norm can be stated as: $$ \min_{u\in\ell_1} \|u\|_1 \qquad \text{subject to} \qquad Au=b, $$ where $u\in\mathbb{R}^m = [u_1,u_2,...,u_m]^\intercal$ is the sequence that we ...
0
votes
0answers
10 views

Tree Pruning and Cost-complexity

This is a question in cost complexity pruning that I want to learn about. I am given $A ≥ 0$ to be the tuning parameter, where $t_0$ is the full tree, and $t$ is a subtree. We then have $|t|$ as ...
3
votes
0answers
58 views

$\ell_1$-Norm Minimization

I am trying to solve the following optimal control problem: $$ \min_{u \in \ell_1} \|u\|_1 \qquad \text{subject to} \qquad Cu = x_f $$ with the linear dynamics $$ x_{k+1} = A x_k + B u_k $$ This ...
2
votes
0answers
27 views

Stochastic programming: Is the linear program over the vertices the same as over the simplex?

Suppose we have a random variable $W$ with probability distribution, $\Pr(W = w) = p_w \in [0,1], \quad w \in I = \{1, \ldots n\}$ Consider the maximization problem: $$\max\limits_{w \in I} \...
1
vote
0answers
47 views

A tricky optimization problem: writing the dual (using Lagrangian)

I am trying to find the dual problem of the following:$$\min_{θ_v\in\mathbb R^l,b_v\in\mathbb R,ξ_{i,v}\in\mathbb R,λ_{i,k,j}\in\mathbb R}\frac1n\sum_{i=1}^n\left(\sum_{v=1}^mξ_{i,v}+\sum_{k=1}^m\sum_{...
1
vote
1answer
46 views

min: L2 norm plus a linear term over simplex

Is there a closed-form solution to the following convex problem? $$ \min_{x\in\Delta}\quad x^\top c+\|x\|_2 $$ where $\|\cdot\|_2$ is the $L_2$ norm and $\Delta=\{x|x\ge0,x^\top1=1\}$ is the ...
1
vote
2answers
39 views

Dual of an SDP ${\min}_{X \in \mathcal{S}^n} \quad \ {\rm trace}( W X )$ s.t. $X_{ii} = 1$; $X \succeq 0$

How to obtain the dual of the following semidefinite programming problem (SDP) \begin{align} \text{minimize}_{X \in \mathcal{S}^n} \quad & {\rm trace}( W X ) \\ \text{subject to }\quad & X_{...
0
votes
2answers
84 views
+50

Distance between a cone and a disjoint hyperplane

I seek to prove the following, which I guess is true: Define $A:=\{x \ge 0\} \subset \mathbb{R}^m$ and assume that $U\subset \mathbb{R}^m$ is an affine subspace with $A \cap U=\emptyset$. Show that ...
1
vote
0answers
18 views

Suggestion for choosing (building) optimization function

I would like to build a supervised learning model M satisfying the following conditions: Training data $\{X, Y\}$, where $x \in R^m$ and $y \in R^n$ Assume: $M(x) = p$, then: $0 < p[k] <= y[k]$,...
0
votes
1answer
30 views

What is the difference between optimization on Banach space versus optimization on Hilbert space?

In Chapter 4 of this book, it says, Suppose now that we are interested in the more general situation of optimization in some Banach space $B$. In other words the norm that we use to measure the ...
-1
votes
1answer
44 views

How can I mathematically prove this?

How can I mathematically prove that P1 and P2 will have the same value of $\eta$ at optimality? Although it seems clear from the intuition. I am looking for proof in the language of mathematics, not ...
1
vote
1answer
46 views

Closed form solution of an SDP [on hold]

Given symmetric positive definite matrices $A$, $M_1$ and $M_2$, is there any closed form solution for the following convex problem in $X$? $$\begin{array}{ll} \text{maximize} & \mbox{tr}(AX)\\ \...
0
votes
0answers
22 views

Is it possible to specify optimization algorithm in CVX? [closed]

I am using CVX as a bench mark to debug my MATLAB code for gradient descent algorithm. Although CVX gives me a good reference point, I was wondering if it is possible to ask cvx to solve optimization ...
1
vote
0answers
32 views

Question related to problem 4.6 of Convex Optimization (Boyd & Vandenberghe)

In problem 4.6 of the book they ask under which condition the following problem can be converted into a standard convex optimization problem. $\text{min. } f_0(x)$ $\text{s.t. } f_i(x)\leq 0, ~~ i \...
1
vote
0answers
66 views

Dual of the barrier transformed linear program $\min_{x \in \mathbb{R}^n} \left\{ c^T x - \mu \sum_{j=1}^n \log(x_j) : Ax = b; x \geq 0 \right\}$

Dual of the following linear program \begin{align} \text{minimize}_{x \in \mathbb{R}^n} \quad & c^T x \ -\mu \sum_{j=1}^n \log(x_j) \\ \text{subject to }\quad & Ax = b\\ & x \geq 0 \ , \...
1
vote
1answer
23 views

Question related to exercise 4.4(d) of Convex Optimization (Boyd & Vandenberghe)

The question is as follows: Suppose $G=\{Q_1,\cdots Q_k\}\subset R^{n\times n}$ is a group. We say that the function $f$ is $G$ invariant or symmetric with respect to $G$ if $f(Q_ix)=f(x)$ holds ...
1
vote
1answer
46 views

Maximum of the root of a quadratic functional with inequality constraint

The function $f(x)$ is the larger eigenvalue of sum of two rank-one matrix. My aim is to get the upper bound of the eigenvalue. The problem can be described by $$ \max_{x} f(x)=b^Tx+\sqrt{x^TAx}\\ ...
1
vote
1answer
49 views

How to prove convexity of an optimization problem?

Consider the following optimization problem. Let $d_3, d_2, d_1 > 0$. Maximize $\log(p_1)+\log(p_2)+\log(p_3)$ Subject to: $p_1d_1 + p_2d_2 + p_3d_3= 1$ $p_1 \geq p_2\geq p_3\geq 0$. I ...
0
votes
0answers
41 views

Does a convex set look the same near its face?

Recall that a face of a convex set $X\subseteq\mathbb{R}^n$ is a convex subset $F$ of $X$ such that every line segment with endpoints in $X$ whose relative interior meets $F$ lies entirely in $F$. ...
0
votes
0answers
31 views

Convexity of quadratic forms

I do not understand a basic concept about the convexity of a quadratic form. I read that A quadratic form $q(h)=h^{T}\mathbf{A}h$ is convex if and only if $\mathbf{A}$ is positive semidefinite. ...
1
vote
1answer
38 views

Minimize Von Neumann Entropy in CVX Matlab

My optimization problem looks like: cvx_begin variable x(2, 2) semidefinite; minimize(VNE(x)) subject to trace(x) == 1 cvx_end Where, VNE or Von Neumann ...
1
vote
0answers
43 views

Optimisation under constraint of Wasserstein distance

Let $\mathcal P_n = \{P \in \mathbb R^n_{\geq 0}: P^T \mathbb I = 1 \}$, where $\mathbb I = (1,...,1)^T \in \mathbb R^n$ and $f: \mathcal P_n \to \mathbb R$ a convex and differentiable function (or ...
1
vote
0answers
26 views

Unique solution to arbitrary regression problem

I have a the following regression problem, where I have data points $(x_i, y_i)$ and $f_{\theta}$ is the regression function parametrized by $\theta$. For example, in linear regression, $f$ is just a ...
2
votes
0answers
62 views

Semidefinite optimization

I'm a physicist and I'm working on a problem that can be reduced to a SDP problem. My problem is: is there a theorem that assures that the result of an optimization saturates the constraint instead of ...
0
votes
1answer
26 views

How to estimate subgradient?

consider a general convex function $f$ which is Lipschitz continuous over $X$, i.e., $\exists M > 0$ such that $$\left|f(x)-f(y)\right| \leq M\|x-y\|.$$ Here $X\subseteq R^n $is a closed ...
1
vote
0answers
18 views

Logistic Regression: Are thresholds and non-negative constraints equivalent?

For interpretability, I want to restrict the weights $\beta_i$ in a logisitic regression $$p(x) = \frac{1}{1 + e^{- \beta^Tx}} $$ to be non-negative, i.e. $\beta_i \geq 0$. Since the negative ...
0
votes
0answers
20 views

Optimization with a symmetric matrix constraint

I have a problem where I need to find the optimal $X\in S_{++}^n$ (i.e. $X$ is positive definite) for a strictly convex function $f(X)$. For what I understand, I need to assign a positive ...
1
vote
0answers
46 views

Gradient Descent vs Lagrange Multipliers

I'm bit confused between Gradient descent and convex optimization using Lagrange Multipliers. I know that we use Lagrange multipliers when we have an optimization problem with one or more constraints. ...
0
votes
1answer
38 views

How are these two optimization problems equivalent?

I'm trying to show that the two problems are equivalent Let $\Bbb A = \{A_1, \dots, A_n\}$ where $A_i \in \Bbb R^{m \times n}$ and $b\in \mathbb{R}^m$ Then $$\min_{x\in \mathbb{R}^n} \...
0
votes
0answers
17 views

Prove the second convex conjugate of a function is itself.

First, we define the conjugate $^*$ as $f^*(y)=\sup_{x\in\mathbb{R}^n} \{y^Tx−f(x)\}$, where $f$ is a convex function. The second convex conjugate is defined as $f^{**}:=(f^*)^*$. I know if $f$ is ...
0
votes
1answer
42 views

Does this optimization problem have a unique solution?

I have come across a seemingly simple optimization problem. Let $h\in L^1(0,1)$; consider the optimization problem \begin{equation} \begin{cases} \min \int_0^1\int_0^t h(s)dsdt\\ \text{s.t. } \int_0^...
0
votes
0answers
24 views

How can we check the convexity of the two variables function?

I am working on the problem of KKT conditions with inequality constraints and at the last stage, it needs to check if the point in question satisfies Slater's constraint qualification. According to ...
0
votes
0answers
19 views

Convex Optimization: objective function in minimum cost flow problem

I have a graph $G=(N,V)$ where $|N|=n$ and $|V|=m$. I want to implement a solver (based on a specific algorithm for convex optimization) for a convex quadratic separable Min-Cost Flow Problem. $$min\{...
1
vote
1answer
97 views

How to minimize $\| x \mathrm a - \mathrm b \|_1$ without using linear programming?

The following question is a generalization of a question asked earlier today: Given vectors $\mathrm a, \mathrm b \in \mathbb R^n$, can one solve the following minimization problem in $x \in \...
1
vote
2answers
52 views

If then convex condition in mixed integer linear programming with binary variables

I have a convex polynomial $f(x_1,\dots,x_t)$ where $x_1,\dots,x_t\in\mathbb R$ and constant $a$. If condition $$f(x_1,\dots,x_t)\leq a$$ holds I have to make variables $y_1,\dots,y_n\in\mathbb R$ ($...
5
votes
1answer
80 views

How to minimize $\| c \mathbf{x} - \mathbf{y}\|_1$ without using linear programming?

Is there a closed form solution to the minimization problem $$\min_{c \in \mathbb{R}}\left\lVert c \mathbf{x} - \mathbf{y}\right\rVert_1$$ where $\mathbf{x} = \begin{bmatrix}0 & 1 & \dots &...
1
vote
2answers
60 views

Matrix Minimization

I'd like to minimize the following function, but can't reach a closed form solution with respect to $C$ from the first-order partial derivative. $||A-BCD^T||_F^2 + \frac{1}{2}||C||_F^2$ where A,B,C, ...
0
votes
1answer
39 views

How to find the minimizer of the following problem?

How to find the minimizer of the following optimization problem? $$\min_P \sum_{i,j=1}^{m,n}\frac{r}{2} \|P_{ij}- Z_{ij}\|^2_2 + \frac{\mu}{2} (\|P_{ij}\|_{1}-1)^2$$ Can we take a simple partial ...
-1
votes
0answers
36 views

Linear programming problem with convex combination constraints

Consider the problem of finding a minimum of a linear programming function: $\min_x f(x).$ Where $f(x) = \sum_{i=1}^{N} a_i x_i.$ Subject to two constrains: $\sum_{i=1}^{N} b_i x_i \leq 1$ $\...
0
votes
1answer
45 views

How to linearize this objective funtion?

The objective function I am dealing is $$\underset{{\bf w}_k,x_k }{\max}\sum_{k=1}^K x_k\alpha_k \log_2(1+\gamma_k)$$ subject to $\sum x_k ||{\bf w}_k||_2^2\le P$ and $\sum_{k=1}^Kx_k=L.$...
1
vote
2answers
76 views

How to linearize this IF-THEN Constraint?

I have a nonlinear constraint as below If $x_k=0$, Then $||{\bf w}_k||==0$ If $x_k=1$, Then $||{\bf w}_k||>0$ Here, $x_k\in\{0,1\}$ is a binary variable and $||\bf x||$ is the norm of vector $\...
0
votes
0answers
19 views

Formulation of the dual linear program for the simple linear regression

Objective: Write the dual linear program for the $\ell_\infty$ form of the primal linear program corresponding to simple linear regression. Let the data set $\{x_i, y_i \}_{i=1}^n$ be stacked in a ...
1
vote
0answers
19 views

How to choose a proper $\lambda$ for LASSO or BPDN problem?

When I deal with the compressed sensing problem, which can be written as: $min |x|_0 \;\; s.t. \|Ax-y\|^2\le\epsilon$. And there are some way to solve the problem, such as relaxing it as $min \;\...
3
votes
1answer
46 views

How to linearize these constraints in scheduling optimization problem?

I have a mixed integer programming problem as below $$\underset{{\bf w}_k }{\max}\sum_{k=1}^K x_k\alpha_k \log_2(1+\gamma_k)$$ subject to $$\sum_{k=1}^K x_k||{\bf w}_k||^2_2\le P$$ $$x_k\in\{0,1\}$$ ...
0
votes
1answer
47 views

L1 norm minimization over a matrix for a linear system

Let $\mathbf{A} \in \mathbb{R}^{m \times n}$, where $m<<n$ and $\mathbf{b} \in \mathbb{R}^{m}$. The rank of $\mathbf{A}$ is $m$ and both $\mathbf{A}$ and $\mathbf{b}$ are known. Consider the ...
2
votes
1answer
69 views

Show that minimizing $Tr(Q)$ equals minimizing $x_0^{T}\:Q\:x_0$

In two different textbooks about Kalman Filter, the so-called Estimator Gain Matrix G is obtained as result of two different minimization problems, i would like to show or at least giustify that the ...