# Tagged Questions

Convex Optimization is a special case of mathematical optimization. It includes Linear Programming and least-squares.

23 views

### Easier way of finding out whether a given linear programming problem has optimal solution or not

I have the linear program $$\begin{array}{ll} \text{minimize} & -2x-5y\\ \text{subject to} & 3x + 4y \geq 5\\ & x, y \geq 0\end{array}$$ I can solve it using Simplex algorithm, but I ...
19 views

### How to minimize objective function involving convolution?

My objective function is \begin{align} \underset{\mathbf{p},\mathbf{q}}{\text{min}}\hspace{4mm} (\mathbf{p*q})^T \mathbf{A}(\mathbf{p*q}) \hspace{4mm} \\ s.t ...
601 views

### Convex Optimization of quadratic function with inequality constraints

How would I solve the following problem? $$\min_{x\in\mathbb{R}^n} x^T A x$$ subject to the constraints $$x_i\geq 1,\,i=1,\dots,n,$$ where A is positive semidefinite and symmetric. Is it possible to ...
46 views

### Optimization problem: $\min \limits_{\mathbf{q}} \sum_{n=1}^N q_n$, s.t. $\frac{c_{nn} q_n }{\sum_{m \ne n} c_{nm} q_m } \ge a$

\begin{array}{rl} \min \limits_{\mathbf{q}} & \sum_{n=1}^N q_n \\ \mbox{s.t.} & \frac{c_{nn} q_n }{\sum_{m \ne n} c_{nm} q_m } \ge a, \forall n \in \{1,\ldots,N\} \end{array} For this ...
16 views

### Can Extragradient method be expressed with proximal steps?

As we know, for solving saddle point problems, forward-backward algorithm is generally not guaranteed to converge. But extragradient method converge Structured Prediction via the Extragradient Method ...
22 views

24 views

### how to minimize huber loss? (SVM related) [closed]

I don't know how to minimize huber loss which is convex and continuous, but how can I minimize that? Can I express it in only one ojective function and obtain its dual problem? My object is to ...
18 views

### Closure of intersection of convex sets

Let $C_i$ be a convex set in $R^n$ for $i\in I$, suppose sets $ri \, C_i$ have at least one point in common, then how to prove this: $cl\bigcap\{C_i\mid i\in I\} = \bigcap\{cl \, C_i \mid i\in I\}$
57 views

### Product of the differences of two pd matrices and their respective inverses is pd

Given two $\textbf{positive definite (pd), Hermitian}$ matrices X and Y, I am trying to determine whether $(X-Y)(Y^{-1}-X^{-1})$ will always be pd as well, and how to prove this. This formulation ...
25 views

### Existence of direction for polyhedral set

I refer to Lemma 4.42 of this lecture notes on linear programming, about the relationship between the boundedness of a polyhedral set and its directions. Let $P$ be a non-empty polyhedral set. ...
25 views

15 views

### subdifferential of $\max_{i=1,\cdots,k} x_i+\frac{1}{2}\|x\|_2^2,\ \ \ x\in \mathbb{R}^n$

How to find the subdifferential of $$f(x) = \max_{i=1,\cdots,k} x_i+\frac{1}{2}\|x\|_2^2,\ \ \ x\in \mathbb{R}^n$$ My derivation is: $\nabla \frac{1}{2}\|x\|_2^2=\nabla \frac{1}{2}x^Tx=x$ ...
37 views

### maximum of a concave function in a minkowski sum

Let: $f(x,y)$ - a strictly-concave function, monotonically increasing in $x$ and $y$; $A,B$ - two compact and convex sets in the positive quadrant; $C$ - their Minkowski sum, $A+B$; $(x_A,y_A)$ - ...
16 views

18 views

### Solving optimization problem where objective function is of type (affine+(affine/affine))

I need to solve a non linear optimization of the form minimize $f(x) +\frac{g(x)}{h(x)}$ subject to $p(x)\leq0$ $q(x)=0$ Here $f,g,h,p,q$ are affine functions of $x$ and they are convex in the ...
7 views

### Deriving a minimizer involving proximal operator

The following are from this thesis http://gpu4vision.icg.tugraz.at/papers/2012/werlberger_phd.pdf I have a difficulty understanding the lines: For example, (4.38) seems very weird to me. I think ...
23 views

### Converges extremely slowly, using Douglas-Rachford splitting, how to improve?

my problem looks like this: $\min _{ E,A }{ { \lambda }_{ 1 }{ \left\| E \right\| }_{ 1 }+{ { \lambda }_{ 2 }\left\| A \right\| }_{ * }+{ \left\| D-ME-A \right\| }_{ 2 }^{ 2 } }$ the M is a ...
35 views

### Proving function is convex argmin

How can I show that the following function is convex in which Z is a random variable? $$\rho(Z)=\frac{2}{3}argmin_{t}\{t+10\mathbf{E}[Z-t]_{+}\}+\frac{1}{3}argmin_{t}\{t+5\mathbf{E}[Z-t]_{+}\}$$ I ...
13 views

### Convex solver returns disordered dual variables, how to re-order?

I have the following convex optimization problem: \begin{align*} \min_{x} &f(x) \\ \text{subject to} \\ x_{k+1} &= x_k+\cdots\qquad k=0,1,2,\ldots,N-1 \end{align*} I managed to solve ...
99 views

### Equivalent characterizations of the dual norm on finite dimensional vector spaces

In their book on Convex Optimization, Boyd and Vandenberghe state that given a norm, $||\cdot||$, defined on $\mathbb{R}^n$, the dual norm is defined as $$||z||_*= \sup \{ z^Tx : ||x|| \leq 1 \}$$ ...
18 views

### How you can model the other players replies in a game theoretic model?

In a game theory field, the payoff function of a player n is basically a function of the other players responses which are considered as constants. I'm trying to solve the maximization of the payoff ...
20 views

### Has $\max\{cx:Ax\le b\}$ an optimal solution $x_1=\sqrt 2$ with $A\in \{-1,0,1\}^{m*n}$ with exactly one $1$ and one $-1$?

Let be $A\in \{-1,0,1\}^{m*n}$ with exactly one $1$ and one $-1$ and zeroes at each line. $c\in\mathbb{Z}^n$ such that $\sum\limits_{j=1}^{j=n}c_j=0$. $b\in\mathbb{Z}^m$ positive. How to start to ...
56 views

### Do corner points optimise a linear function over a bounded convex region?

This proof says if $Z_P \ne Z_Q$... ...then $Z$ is maximised (or minimised, I guess) at one of the $\color{red}{\text{endpoints}}$ -- of what exactly? $\overline{PQ}$? So the maximum value of ...
37 views

### Weights in goal programming

I'm not quite convinced about assigning weights in goal programming. Here is an example formulation problem. What I tried: Let $x_j$ be the number of minutes for ad $j = R, T$ We want to ...
17 views

### Why the dual and the canonical dual may have the same optimal solution?

For instance let be \begin{cases} \max & 3x_1 &+2x_2 &+4x_3 & -x_4\\ &x_1 &+x_2 &-2x_3&&\le4\\ &2x_1&+3x_3&&-4x_4&\ge 5\\ ...
35 views

### Converting generic linear problems into their dual

I'm revising how to do dual problems in linear algebra. I'm very weak in Linear programing but I struggle to cope with the topic during lectures and assignements. I have to convert the following ...
54 views

### Yale College's Housing Draw Problem — Convex optimization techniques on a modified stable marriage problem?

I'd like to run various optimization techniques on this variation of the stable marriage problem I formulated. Ideally, I'd be able to convert the problem I constructed into one that is more ...
36 views

### A Question On Triple Integration

Can anyone construct a nonzero continuous function $f:[0, 1]\times[0, 1]\times [0, 1]\rightarrow [0, \infty)$ such that \begin{equation*} \int_{t_1=0}^1 \int_{t_2=0}^1 \int_{t_3=0}^1 f(t_1, t_2, ...
997 views

### convex hull function in matlab

Is there any way to compute the convex hull of a finite set of points in Matlab and gives the half-space representation as its result? I usually use a toolbox called MPT developed at ETHZ Zurich, but ...
82 views

### Why is the Barycenter operation in Hadamard spaces Lipschitz continuous?

I am looking into exercise 9.2.22 of "A course in metric geometry" by Burago-Burago-Ivanov. For a Hadamard space $H$ (a complete simply connected metric space of nonpositive curvature in the ...
Why is \begin{aligned} & \min\max_{i=1,\ldots,n} & &a_i^Tx+b_i\\ \end{aligned} equivalent to an LP \begin{aligned} & \min & ...