Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

1
vote
0answers
11 views

Overconstrained linear system. Minimizing error for “quasi-solutions”.

This is a practice-motivated problem, and I know very little about optimization, so I come here for help. Consider the system $$A\mathbf x=\mathbf b$$ Where $\mathbf x, \,\mathbf b$ are ...
0
votes
0answers
24 views

Are the constrained optimization problem equal to the unconstrained one?

(1) \begin{equation}\label{constrained} \begin{array}{cl} \arg \min \limits_{x} & \|Ax-b\|_2\\ \mathrm{s.t.} & \|x\|_1\le \epsilon \end{array} \end{equation} (2) ...
0
votes
0answers
22 views

Showing how a dot product is less than 0

Considering a function $f\in C^1(\mathbb{R}^N)$ with $g=\nabla f(x)$, I want to prove a result about optimizing it. However the part I am struggling with I think can be reduced to simple matrix dot ...
0
votes
2answers
36 views

Calculus 1: Optimization Word Problem - Right Triangle

Find the maximal area of a right triangle with hypotenuse of length 6. I've labeled my triangle with Z being the hypotenuse and the two sides X and Y. I know $$A = BH/2 = XY/2$$ Using the ...
0
votes
1answer
21 views

A ratio of two convex functions with different minima cannot be monotone. Proof?

Let $\lambda(x)=\frac{f(x)}{g(x)}$ where $f(x)$ is a differentiable function minimized at $x=x_1$ and $g(x)$ is a differentiable function minimized at $x=x_2\neq x_1$. How can I show that $\lambda(x)$ ...
1
vote
0answers
12 views

Show that every extrema of $\phi_a(x)+\phi_b(x)$, sum of angular diameters, is a linear combination of $a,b$

Where $a,b\in \Bbb{R}^n$, $|a|=5,|b|=10$, $a,b$ are linearly independent, define $\phi_a(x)$ to output the angular diameter of a point $x$ with respect to the sphere $S_1(a)=\{x\in ...
1
vote
0answers
21 views

Global minimum of the function 'maximum of absolute values of linear fuctions in two variables'

Let $a=(a_{1},a_{2},\ldots,a_{n})\in\mathbb{R}^{n}$, $b=(b_{1},b_{2},\ldots,b_{n})\in\mathbb{R}^{n}$, $c=(c_{1},c_{2},\ldots,c_{n}) \in\mathbb{R}^{n}$ be given. Let us firstly consider the problem of ...
0
votes
0answers
13 views

How to solve a multiple knapsack problem?

I have the following binary LP max $\sum_{l=1}^{L}\sum_{f=1}^{F}[S_{f} \sum_{k=1}^{K}a_{kl}b_{kf}]x_{lf}$ s.t $\quad 1)\quad \sum_{f=1}^{F}x_{lf}S_{f}\leq C_{l} \quad \forall l$ $\quad 2)\quad ...
2
votes
0answers
25 views

Finding minimum energy graph, subject to constraints

I imagine there's a known algorithm for this, but am not totally sure what to search for, and so my search didn't turn up much. Basically, I have have a set of $N$ nodes $\hat x_i $ in a graph $\hat ...
2
votes
1answer
66 views

Are there any global extrema in this Lagrange Multiplier problem?

I'm trying to find the max and mins of the equation $f(x,y,z) = xy + 3xz + 2yz$ on the constraint, $g(x,y,z)=5x+9y+z-10$. So according to the Lagrange Multiplier procedure, I take the partial ...
0
votes
0answers
15 views

Minimization over a specific set

Suppose we want to find the argmin of a function over a specific set: \begin{equation} \tilde z= \text{arg}\min_{z \in I} \Phi(z), \end{equation} where $z$ is a vector (say, $z \in \mathbb{R}^n$) and ...
1
vote
1answer
46 views

Property of Rayleigh Quotient

I want to know on how do I prove this following statement of the Rayleigh Quotient. If A is symmetric, the optimization values (I) and (II) below have the same optimal value. If A has at least one ...
1
vote
0answers
70 views

What programs or websites solve linear integer or goal programming problems?

I don't think I can use Excel. My solver doesn't work so I can't even use Excel for regular linear programming. Something like this but for integer or goal programming. This seems to allow integer ...
0
votes
0answers
21 views

computational-expensive signal reconstruct - a combination problem

My problem is: I have a time series signal (vibration signal), use BSS algorithm (Blind Source Separation, we can regard it as a black box), separate the source signal into 100 components. Now I ...
2
votes
0answers
25 views

Egyptian fraction with least possible sum

Suppose that $~a~$ and $~b~$ are coprime positive integers. Then there exists representation of $~\frac{a}{b}~$ as egyptian fraction: $$~\frac{a}{b} = \frac{1}{d_1} + \cdots + \frac{1}{d_s} ~$$ There ...
0
votes
1answer
26 views

Minimizing a sum of exponential functions

I want to minimize this function: $$ g_0(\psi)= \sum_{m=0}^{M-1}e^{j(am^2+bm)}e^{jm\psi} $$ where $a$ and $b$ are constants for which I want to minimize the function. Can anyone help me regarding ...
0
votes
0answers
20 views

Expressing $\forall$ in linear programing

I'm doing a linear program to a game and I don't know how to express $\forall$ in linear programing (or if I had the right intuition to do it). Here is the problem: I have several vessels that are ...
0
votes
0answers
28 views

One dimensional obstacle problem - how to determine coincidence set

I was wondering whether someone could comment on my line of reasoning and, if possible, point me to some relevant literature etc. In general any help will be much appreciated! Suppose $\Omega = ...
0
votes
0answers
8 views

Maximize nonlinear nonconvex optimization

Nonlinear nonconvex maximization problem Signal to noise plus interference ratio Please how do I resolve a problem of this nature?
0
votes
0answers
11 views

How to find the Lagrangian dual function (for three variables)?

How to find the Lagrangian dual function: min$-3x_1-2x_2-x_3$ s.t. $2x_1+x_2-x_3-2\le0$ $x_1+2x_2-4\le0$ $x_3-3\le0$ $x_1,x_2,x_2\ge0$ over $X=\lbrace ...
1
vote
1answer
21 views

how to find extreme points for 3 variable linear programming

It is rather easy to find extreme points in 2 variable case. But to find them for higher dimensions, for example in 3 variable case. For instance, min $-3x_1-2x_2-x_3$ st. $2x_1+x_2-x_3\le2$ ...
0
votes
0answers
35 views

Show a dictionary cannot be optimal for given equations

Show that the following dictionary cannot be the optimal dictionary for any linear programming problem in which $w_1$ and $w_2$ are the initial slack variables: $$\begin{align} \zeta&=4-w_1-2x_2 ...
0
votes
0answers
11 views

separability of dynamic programming

I am working on some portfolio selection problem and running into this concept. It is stated that "multiperiod mean–variance formulations cannot be solved using dynamic programming due to their ...
0
votes
0answers
23 views

Applying Minimization algorithm on Rosenbrock function!

Why does rosenbrock function not converge using gradient method? But converges using Newton's method?
1
vote
2answers
57 views

Minimising the length of the vector $r(t) = \sqrt{2}\sin{t}\mathbf{i}+\cos{2t}\mathbf{j}$ for $t \in (0, \pi/2)$

I want to minimise the length of the vector $r(t) = \sqrt{2}\sin{t}\mathbf{i}+\cos{2t}\mathbf{j}$ for $t \in (0, \pi/2)$ I have found that $|r(t)| = \sqrt{\sin^2(t)+1}$ but I can't minimise this for ...
1
vote
0answers
36 views

Two problems related to the Hitchcock transport problem.

I try to solve the following two problems related to the "Hitchcock Transportation Problem" which reads as follows :$$min \sum_{i=1}^N\sum_{j=1}^Mc_{ij}x_{ij}$$subject ...
0
votes
0answers
17 views

How to find extreme directions?

objective:min $−3x_1−2x_2−x_3$ The set is : $X=\lbrace (x_1,x_2,x_3):2x_1+x_2-x_3\le2; x_1,x_2,x_3\ge0 \rbrace$ Attempt: $2d_1+d_2-d_3\le0$ (a) $d_1+d_2+d_3=1$ and $d_1,d_2,d_3\ge0$ Since from ...
2
votes
1answer
51 views

Unique local extremum is absolute extremum for continuous functions

I was wondering if this is true. Let $f:(a,b) \rightarrow \mathbb{R}$ be a continuous real function and suppose $c \in (a,b)$ is the unique local maximum of $f$ and that $f$ has no other local ...
5
votes
2answers
56 views

Finding the integer solution that makes $\lvert x-y \rvert$ the greatest?

I was attempting to solve this problem. Let $x,y$ be non-negative integers which satisfy the equation. $$2^{x} +2^{y} = x^{2} +y^{2}$$ Find the maximum possible value for $\lvert x-y \rvert$? At ...
1
vote
0answers
11 views

regularized least squares (L1 norm)

My objective function that is to be minimized is as follows: $$\|y-Ax\|_2^2 + \alpha\|Lx\|_1$$ where $L$ is the gradient operator. Now this problem seems convex because the first term is quadratic ...
0
votes
1answer
18 views

What varialbes enter the $\min/\max$ in dual problem?

Having the following linear program: \begin{cases} \max & -x_1 & -2 x_2&+x_3\\ & -3 x_1 &+x_2 & &\le -1\\ & x_1 &-x_2 & &\ge 1\\ &-2x_1 & +7 x_2 ...
2
votes
1answer
43 views

Maximum of minimums

Suppose $v_1,\ldots, v_k \in \mathbb{R}^n$ are vector with all coordinates non-negative. How to explicitly calculate: $$ \max_{x\geqslant 0, ||x||_1=1} \min_{1\leqslant i \leqslant k} <x,v_i>$$ ...
0
votes
0answers
20 views

equality constraints and conic constraints in Sedumi (SOCP)

I´m starting playing with Sedumi. I want to solve a problem in the form $$ \min c_0' x $$ s.t. $$ A_1 x = b_1$$ $$ ||A_2 x + b_2|| <= c_2'x+d_2 $$ where $x \in R^n$, $ A_1 \in R^{m_1,n}$, $ ...
1
vote
0answers
30 views

Find minimum model as parameters change

So I have a question, and I'm not even sure what fields might best answer it (so even any hints or keywords to search would be helpful to me). I have a handful of small models, and I want to know ...
2
votes
0answers
51 views

Optimization of English Braille: Using the fewest dots

Background: The English Braille system is laid out in such a way so that the letters can be referenced by their position in the alphabet. Of the six dots available for each character, the top four ...
0
votes
0answers
14 views

nonlinear Poisson equation - finite elements

I am kind of new in finite elements and I am solving simple "Poisson nonlinear" problem. $- \nabla ((1 + u^2) \nabla u) = f$ $u = 0 \ \text{on} \ \Omega $ I am using Newton solver, where I have ...
1
vote
1answer
20 views

Trust-region method

The question has to do with the trust-region method for unconstrained optimization. I came across it on p.~392 of Linear and Nonlinear Optimization, by Griva, Nash and Sofer. Let $p(\lambda)$ be ...
0
votes
1answer
11 views

Relationship between Primal and Dual problems

Considering the following program: \begin{cases} \max & 8x_1 & + 3x_2\\ & x_1 &-6x_2&\ge2\\ & 5x_1 +&7x_2&=-4\\ &x_1&&\le 0\\ && x_2&\ge 0 ...
2
votes
1answer
102 views

Solution for $\min_{x^Tx=1} x^TAx-c^Tx$

$\min_{x^Tx=1} x^TAx-c^Tx$ looks like a simple QPQC problem. If $A$ is positive semi-definite, can I get the solution by first getting $x=A^{-1}c$ and then projecting $x:=\dfrac{x}{||x||}$ to make ...
2
votes
0answers
38 views

Isotonic regression like

I have 2 ordered sets $$X=\{X_1<\dots<X_n\}$$ and $$Y=\{Y_1<\dots<Y_m\}$$ with $X_1<Y_1$ and and $X_n<Y_m$. I wish to approximate an increasing continuous function $g$ by piecewise ...
1
vote
3answers
90 views

Maximum value of $(ab)(a+b)$ given $a^2 + b^2 = 100$

Can anyone help me with finding the maximum value of $$y = {(ab)(a+b)}$$ With that condition that $$ 100 = a^2 + b^2$$ and both $a,b$ are positive numbers. Any help appreciated. Thanks.
2
votes
1answer
46 views

maximum volume of a box inside an ellipsoid

What is the maximum volume of a box that can be placed inside an ellipsoid $\frac{x^2}{16}+\frac{y^2}{9}+\frac{z^2}{25}=1$ The volume of a box is $V=xyz$ so I need to find $x,y,z$ with respect to ...
0
votes
0answers
12 views

Joint convexity through expected value and max operators

I am trying to minimize the following function by choosing $q$ and $z$, where $X$ and $Y$ are random variables, and $r$, $a$, and $b$ are constants. $C(q,z)=E_{X}[a \cdot max(0,X - q)] + E_{Y}[b ...
0
votes
0answers
10 views

Scaling vector-valued objective function for non-linear optimization/minimization

I am trying to minimize a non-linear vector-valued function in MATLAB. As a test case for my code, I try to minimize a function whose solution I know apriori. The problem is that one of the solutions ...
0
votes
0answers
12 views

Convert Quadratically constrained basis pursuit to LASSO

The Quadratically constrained basis pursuit is to solve \begin{align} \hat{\boldsymbol{x}} &= \arg\min \|\boldsymbol{x} \|_1 \\ s.t. & \| \boldsymbol{Ax} - \boldsymbol{y} \|_2^2 < \eta ...
6
votes
0answers
109 views

Find distance to a set (subspace) without computing closest point

General setup: we have a finite-dimensional normed linear space $(V, \| \cdot \|)$, a subspace $U \subset V$, and a fixed vector $v_0 \in V$. We want to find the distance between $v_0$ and $U$. (No ...
0
votes
1answer
26 views

A right triangle with hypotenuse 10 and two sides of variable length are rotated about its hypotenuse.What is the maximum possible area of solid?

The complete question is "A right triangle with hypotenuse 10 and two other sides of variable length is rotated about its longest side.What is the maximum possible area of such a solid? The solid ...
1
vote
1answer
23 views

Max-flow/min-cut to determine densest subgraph

I have been trying to understand how a maximum average degree problem can be solved as a maximum flow problem for my optimization class from this article: ...
0
votes
0answers
34 views

Minimise Mean square error(MMSE) proof procedure

I am awkard to understand the basic things so I have suffered from the procedure of proving the minimize the mean square error. the mean square error is $$ E[(X-g(Y))^{2}]=\int_{-\infty ...
1
vote
0answers
11 views

Does there exist an optimal solution $(x^*,y^*)$ to $\max x^TAy$ such that $x^*=y^*$?

Given two positive integers $n \le m$ and non-negative real constants $a_{ijkl} \ (1\le i,k\le n,1\le j,l\le m)$. Let $M$ be the set of $X\in\mathbb{R}^{n\times m}$ satisfying: $X\ge 0$, The sum ...