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)

-2
votes
1answer
41 views

train cost optimization problem

Fuel cost for operating a train is proportional to the square of the speed, and is Rs.50 per hr when the speed is 20 mph. Other charges, such as labor, for example, put together is Rs.200 per hr. The ...
0
votes
0answers
16 views

Minimizing l2-norm of convolution (Perron-Frobenius theorem)

I need to minimize the $||\mathbf{h}*\mathbf{x}||_2$, where $\mathbf{h}$ is a given non-negative vector, and $\mathbf{x}$ should be a compactly supported non-negative vector. In the matrix form, this ...
3
votes
0answers
139 views

Binary optimization

Let me first make my background clear. I am a PhD student with not much knowledge in optimization but I need to do some optimization as a part of my research work. My problem is as follows: There are ...
-2
votes
2answers
21 views

The optimization problem with max [closed]

Given $(m\times n)$-matrices $A=(a_{ij})$ and $B=(b_{ij})$, and a vector $c=(c_1, c_2, \ldots, c_m)$; and $\underline{x},\overline{x},\underline{y},\overline{y}$ are real numbers such that ...
1
vote
0answers
16 views

How to find optimal subset $I$ such that $(\sum_{i \in I} a_i)^x / \sum_{i \in I} b_i$ is maximized?

Suppose we are given pairs $(a_i,b_i)$ of positive numbers and $x \geq 1$. The goal is find the optimal subset of indices $I$ that maximizes: $$\frac{(\sum_{i \in I} a_i)^x}{\sum_{i \in I} b_i}$$ ...
0
votes
1answer
25 views

Maximization of a function in an interval

I am writing a computer program where I have $x$ real positive varying in the domain $[\sqrt{U}, U]$. I want the value of $x$ which maximizes: $$ (1+ \sqrt{U}) - \frac{\sqrt{U}-1}{U-\sqrt{U}} x - ...
0
votes
0answers
34 views

Optimization on fixed sum

Consider this following scenario. Suppose I have $N$ cents, and I want to dispatch these money to $n$ people, each got $x_i$ cents. In order to simplify this problem, we assume the cents are ...
1
vote
2answers
52 views

Can $\sin (x)$ be represented as difference of two convex functions?

In my optimization homework, I am supposed to prove that every differentiable function with Lipschitz continuous gradients can be represented as difference of two convex functions. I think I have come ...
1
vote
2answers
400 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 ...
0
votes
0answers
21 views

Maximizing profit (dynamic programming)

I'm looking at a dynamic programming question and can't figure out how to solve it. The question is listed at the following website (question number 19, towards the bottom). ...
1
vote
0answers
11 views

Cross-entropy minimization - equivalent unconstrained optimization problem

I'm looking at this paper "An Alternative Method for Estimating and Simulating Maximum Entropy Densities" ...
-3
votes
0answers
19 views

Critical point outside of domain when finding the intervals on which a function is increasing and decreasing.

I have this function: f(x)=x^(1÷3) × (x+8) I'm trying to find the intervals on which the function is increasing and decreasing. Then, I am to find the local extrema. I've done this: f'(x) = ...
-2
votes
0answers
18 views

Maximizing revenue [closed]

A coffee wholesaler sells two types of beans. Arabica beans that sell for $ \$8 $ a pound and Selecto beans that sell for $ \$24 $ a pound. The Arabica beans cost $\$1$ per pound to store and the ...
0
votes
1answer
37 views

Given the set of all polygons with m sides and perimeter 1, why is there an element with maximal area?

The set of all polygons with $m$ sides and perimeter $1$ has an element with maximal area. I read this fact in a book, and the reference was in German. Does anyone here know? I know how to ...
3
votes
1answer
31 views

How can I project a matrix on the set of symmetric positive definite matrices with trace 1?

Given a square matrix $A \in \mathbb{R}^{n \times n}$, I need to compute $$ \min_{X \in \Omega} \lVert A - X\rVert^2$$ where $\Omega = \{X \in \mathbb{R}^{n \times n} |\, tr(X) = 1, X \text{ is ...
0
votes
0answers
52 views

Matrix norm optimization problem : $\min_{\textit{ }x} \| A x B \|_4$, $x$ in the “unit” circle

Bonjour, Let $A$, $B$, $C$ and $D$ complex matrices. Is there a way to find a matrix $x$ (edit: non trivial) as: $\min_{\textit{ }x} \| A x B \|_4^4$ Or, more complicated, $x$ as $\min_{\textit{ ...
0
votes
1answer
38 views

Given $R \in \mathbb R$, choose $a,b,c$ from discrete set so that $a^{-1} + b^{-1} + c^{-1} \approx R^{-1}$

I am working with the following equation (parallel resistors): $\frac{1}{R_g} = \frac{1}{R_1} + \frac{1}{R_2} + \frac{1}{R_3}$ The values of $R_1, R_2$ and $ R_3$ are discrete - lets say 256 steps ...
0
votes
0answers
11 views

Dual norm of quasi norms

The dual norm $\Omega^*$ of the norm $\Omega$ is defined for any vector $\mathbf{z} \in \mathrm{R}^N$ by \begin{equation} \Omega^*:= \underset{\mathbf{x} \in \mathrm{R}^N}{max } \quad \mathbf{z}^{T} ...
1
vote
0answers
16 views

Optimal $A\in \Sigma$ that maximizes an objective

Let $([0,1],\Sigma, \lambda)$ be a probability space. For any given $B\in \Sigma$, $K\in [0,1]$ and $f\in L^2(\lambda)$ with $f(x)\in[0,1]$ for all $x $, $$\max_{A\in \Sigma}\int_A f(x) d\lambda(x)- ...
-1
votes
0answers
38 views

calculus optimization help

Minimum Cost A storage box with a square base must have a volume of 80 cubic centimeters. The top and bottom cost 0.20cents per square centimeter and the sides cost 0.10cents per square centimeter. ...
2
votes
1answer
25 views

Where can I find an algorithm to compute $\min_{x \in \Delta_n} \langle g , x - y \rangle_1 + c\lvert x - y\rvert_1^2$?

I wish to compute the minimizer of $$ \min_{x \in \Delta_n} \langle g , x - y \rangle + \frac{c}{2}\lvert x - y\rvert_1^2$$ where the subindex $1$ indicates that the norm is the $1$-norm and ...
0
votes
0answers
37 views

Non-convex function with global minimum [duplicate]

I am working on a complicated objective function which I suppose is not convex. But when I use a global optimization tool that can find all its local minimums, it will always converge to the same ...
0
votes
0answers
28 views

Multivariate Optimization [closed]

I'm currently in a multivariate optimization course and literally have no idea what I'm doing. If someone could help me with this problem or at least tell me where to start I'd be eternally grateful. ...
0
votes
1answer
26 views

Convex optimization problem: linear equality and inequality constraints

When linear equality constraints can be converted in an inequality constraints for a strongly convex optimization problem? I mean, I got the same solution for both the following problem: 1) $\min_x ...
0
votes
2answers
35 views

Is there a name for this modified newton's method?

I know that Newton's method has the following formula: $$f_{t+1} (x)= f_{t}(x)-f'(x)/f''(x)$$ The source code at the end of the post seems to use the following construction instead: $$f_{t+1} (x)= ...
2
votes
0answers
22 views

Some maximization over stochastic matrix

I am writing some applied assignment which leads me to the following problem. I will be very grateful if anyone can provide a solution or even some thoughts. Thanks a lot! Consider a (row-)stochastic ...
4
votes
1answer
2k views

Linear Programming: Three variable graphical solution

A small bank offers three type of loans: housing loans at $8.50$% interest, education loans at $13.75$% interest rates, and loans to senior citizens at $12.25$% interest. Further, it needs to ...
0
votes
1answer
16 views

Discrete optimization of weighted sum under constraint

Let $\lambda_1, \dots, \lambda_n \geq 0$, $\;\;c_1, \dots, c_n \in \mathbb{R}$ and $\;\;\gamma >0 $. We are looking for the maximum of function $f$ with $$ f(x) = x_1\lambda_1 + \dots + ...
0
votes
1answer
21 views

Prove that $w/w_0$ (no idle over minimum possible) $\le 2-1/n$ for any set of tasks on an n processor system

$w/w_0 $ $\le 2-1/n$ I've noticed this problem in a couple of discrete math and algorithm analysis textbooks. Many of them prove it for n=2, but I want to prove it for all n. The idea is that we ...
0
votes
0answers
21 views

Optimality Conditions and Optimal Solution to minimize f(x)

just wanted to check my working for a homework problem. Any help would be much appreciated. Write the set of optimality conditions and state the optimal solution for the following mathematical ...
1
vote
1answer
37 views

Why is Mergesort $O(n)$ rather than $O(n\log{n})$?

Assume we want a divide-and-conquer algorithm that finds the max and min of a set $S$ with $n = 2^k$ elements, e.g. mergesort. The recurrence for time complexity is $T(n)=2*T(n/2) +2$, for $n>2$, ...
1
vote
1answer
28 views

Question about optimization

I have a question about maximization/minimization problems. I have noticed that for almost all the practice problems that I have had that ask to find the sum of numbers and minimize product or ...
3
votes
3answers
88 views

Why do lagrange multipliers have the form $\nabla G$

I was studying some multivariable Calculus and we were covering the topic of Lagrange multipliers. I didn't understand exactly why the equations take the form: $$ \nabla f = \lambda \nabla G $$ ...
1
vote
0answers
16 views

Maximizing the frobenius norm subject to constraints $\underset{\mathbf{S}}{\text{maximize }} \|\mathbf{S}\|_F^2$

IF $\mathbf{X=AS}$ where $\mathbf{X} \in R_+^{n \times m}$, $\mathbf{A} \in R_+^{n \times r}$ are known variable and $\mathbf{S} \in R_+^{r \times m}$ is unknown variable, How to solve the below ...
0
votes
0answers
15 views

Are there Karnaugh maps over other algebras?

Karnaugh maps are a useful way to minimize or factorize polynomial expressions in Boolean algebra by considering the smallest combinations of logical "subcomponents" of an expression, whose sum is ...
0
votes
0answers
20 views

connections between polar set, polar cone?

Given a set $S$, its polar cone http://en.wikipedia.org/wiki/Dual_cone_and_polar_cone and its polar set http://en.wikipedia.org/wiki/Polar_set are defined. Could some please tell me the ...
0
votes
0answers
27 views

How can I minimize a quadratic on the unit simplex?

How can I compute $$ \min_{x \in \Delta_n} \frac{1}{2}\lVert Bx\rVert^2 + x^tAy$$ with $x \in \mathbb{R}^n, y \in \mathbb{R}^m, A_{m \times n}$, $B_{n \times n}$ where $\Delta_n$ is the unit simplex ...
2
votes
0answers
23 views

How to maximize the minimal amount not payable with the exchange of at most two coins?

Background I've been thinking about payments which you can do using at most two coins. This includes three possible cases: You pay by giving one coin of the value you owe (for example, if you have ...
0
votes
0answers
18 views

KKT Sufficient condition when optimal solution is intuitively at the boundary

My optimization problem is: $\operatorname{arg\,max}_P \sqrt P$ subject to $P \le \upsilon_\tau$ where $P \in \mathbb{R}^+$ and $\upsilon_\tau \in \mathbb{R}^+$ Intuitively, because $\sqrt P$ is ...
4
votes
1answer
46 views

Lagrange's multiplier not working

Given the function $f(x,y):=xy+x-y$. Let $D:=\{(x,y)\in\mathbb{R}^2:x^2+y^2\leq25\wedge x \geq 0\}$. Find the absolute maximum and minimum of $f$ on $D$. My working is as follows: $\begin{array} ...
3
votes
4answers
504 views

The median minimizes the sum of absolute deviations

Suppose we have a set $S$ of real numbers. Show that $$\sum_{s\in S}|s-x| $$ is minimal if $x$ is equal to the median. This is a sample exam question of one of the exams that I need to take and I ...
1
vote
1answer
39 views

How to maximize $a^2 + \delta^2(s-a)^2$ by inspection?

I need to maximize: $a^2 + \delta^2(s-a)^2$ where: $\delta\in(0,1)$ and $0\le a \le s$. The solution in my text simply states: Since $\delta^2 < 1$ , the maximum occurs when $a=s$. I ...
0
votes
0answers
8 views

optimization of formulas involving binomial coefficients

I encountered such a problem. We need to find the min value and max value of $f(x,y)$. $x$ and $y$ are integers $\in[0,n]\times[0,n]$ and $(x,y)\neq (0,0)$ or $(n,n)$. $$ ...
-1
votes
0answers
18 views

Help understanding the specification of constraints for cvxopt

This is an example from the cvxopt documentation and I am trying to understand how the L2 constraints are specified to the solver. The problem is specified as: ...
0
votes
2answers
757 views

Optimal Basic Feasible Solutions

In linear programming, is it true that you can only have at most 2 optimal basic feasible solutions? If so, why?
1
vote
2answers
43 views

maximizing a coordinate of $x^T A^T A x \leq r^2$

Given a vector $\mathbf{x} \in \mathbb{R}^n$, a scalar $r\gt 0$ and an invertible matrix $\mathbf{A} \in \mathbb{R}^{n\times n}$, I'd like to maximize one of the components $x_\alpha$ constrained by ...
0
votes
2answers
22 views

Optimization - Maximizing Profit

I have been struggling with the problem below for quite some time now and no one can seem to figure it out, so I am asking it here. The question is as follows: You own an apartment complex with 50 ...
0
votes
0answers
19 views

How can I solve $\min \{ \langle A(x),y\rangle + f(y) \text{ s.t. } y \in S^n, \operatorname{tr}(y) =1, y \geq 0\}$?

I'm trying to solve the problem $$\min \{ \langle A(x),y\rangle + f(y) \mid y \in S^m, \operatorname{tr}(y) =1, y \geq 0\}$$ where $x \in \mathbb{R}^n$, $y \in S^M$, that is, it's a symmetric $m$ by ...
0
votes
1answer
43 views

How to solve $3y\cos(\theta) - 2x\sin(\theta) = 5 \sin(\theta)\cos(\theta)$?

How to solve $3y\cos(\theta) - 2x\sin(\theta) = 5 \sin(\theta)\cos(\theta)$? I am optimizing a function where I need to solve the above equation for $\theta$. What is the best way to do this? I ...
0
votes
1answer
61 views

Maximise $y$ with respect to $x$ for $y=\prod_{k=1}^{\infty}(1-x^{-k})$

$$y=\prod_{k=1}^{\infty}(1-x^{-k})$$ I want to maximise this function. So far I have: $$\ln(y)=\sum_{k=1}^{\infty}\ln(1-x^{-k})$$ ...